c++ - 极慢的随机字符串生成器

Question

我想出了下面的代码来生成 100001 个随机字符串。这些字符串应该是唯一的。但是，下面的代码需要几个小时才能完成这项工作。有人可以让我知道如何优化它，为什么这么慢？

string getRandomString(int length) {     
    static string charset = "abcdefghijklmnopqrstuvwxyz";   
    string result;
    result.resize(length);
    for (int i = 0; i < length; i++) {
        result[i] = charset[rand() % charset.length()];   
    }
    return result; 
} 
void main(){

    srand(time(NULL));
    vector<string> storeUnigrams;
    int numUnigram = 100001; 
    string temp = "";
    int minLen = 3;
    int maxLen = 26;
    int range = maxLen - minLen + 1;
    int i =0;

    while(i < numUnigram){
        int lenOfRanString = rand()%range   + minLen;
        temp = getRandomString(lenOfRanString);
        bool doesithave = false;
        for(int j =0 ; j < storeUnigrams.size() ; j++){
            if(temp.compare(storeUnigrams[j]) == 0){
                doesithave = true;
                break;
            }
            if(temp.compare(storeUnigrams[j]) < 0){
                break;
            }
        }
        if(!doesithave){
            storeUnigrams.push_back(temp);
            sort(storeUnigrams.begin(),storeUnigrams.end());
            i++;
        }

    }

Answer 1

有两个因素会使您的代码变慢：

1. 通过线性搜索检查字符串是否已经存在 - O(n)
2. 在每次迭代中对向量进行排序 - O(n log n)

使用例如 aset来存储字符串——它是自动排序的，并且检查是否存在很快：

int main(){

    srand(time(NULL));
    set<string> storeUnigrams;
    int numUnigram = 100001; 
    int minLen = 3;
    int maxLen = 26;
    int range = maxLen - minLen + 1;

    while(storeUnigrams.size() < numUnigram){
        int lenOfRanString = rand()%range   + minLen;
        storeUnigrams.insert(getRandomString(lenOfRanString));
    }
}

Answer 2

菲利普的回答很好。另一种方法是使用像红黑树这样的自平衡二叉搜索树而不是向量。您可以在 log(n) 时间内执行搜索和插入。如果搜索为空，则插入元素。

Answer 3

此代码仅生成一次唯一的随机数并将其存储在random_once[i].

第一个for循环生成广告存储随机数。

第二个循环用于获取存储在数组for中的预渲染随机数 。random_once[i]

是的，生成100001随机数将需要数小时甚至数天。

#include <ctime>
#include <iostream>
using namespace std;


int main()
{
      int numUnigram = 3001;
      int size=numUnigram;
      int random_once[100001];

      cout<<"Please wait: Generatng "<<numUnigram<<" random numbers   ";
      std::cout << '-' << std::flush;
      srand(time(0));



      for (int i=0;i<size;i++)  

      {

           //This code generates a unique random number only once
           //and stores it in random_once[i]

            random_once[i]=rand() % size;
            for(int j=0;j<i;j++) if (random_once[j]==random_once[i]) i--; 

            //loading animation  
            std::cout << "\b\\" << std::flush;
            std::cout << "\b|" << std::flush;
            std::cout << "\b/" << std::flush;
            std::cout << "\b-" << std::flush;

      }

      cout<<" \n";

      // this code dispays unique random numbers stored in random_once[i]
      for ( i=0;i<size;i++) cout<<" "<<random_once[i]<<"\t";
      cout<<" \n";

  return 0;
}

Answer 4

在 while 循环之外定义变量 - 因为它们在每次迭代中都被重新定义

int lenOfRanString = rand()%range   + minLen; ;
bool doesithave = false;

更新

认为在许多书籍中都建议这样做，在所有新编译器的实践中，这不会显着提高性能

Answer 5

使用 char 数组而不是字符串（字符串类在幕后做了很多事情）