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++;
        }

    }

score 9 · Accepted Answer

コードを遅くする要因は 2 つあります。

文字列が既に存在するかどうかを線形検索で確認 – O(n)
各反復でのベクトルの並べ替え – O(n log n)

たとえばset、文字列を格納するために a を使用します。自動的にソートされ、存在を確認するのは高速です。

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));
    }
}

score 0 · Accepted Answer

このコードは、一意の乱数を1回だけ生成し、に格納しrandom_once[i]ます。

最初のforループは、乱数を格納する広告を生成します。

2番目のループは、配列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;
}

score 0 · Accepted Answer

フィリップの答えは大丈夫です。もう 1 つのアプローチは、ベクトルの代わりにRed Black Treeのような自己平衡二分探索木を使用することです。検索とインセットを log(n) 時間で実行できます。検索が空の場合、要素を挿入します。

score -1 · Accepted Answer

while ループの外側で変数を定義します - 各反復で変数が再定義されるためです

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

アップデート

多くの書籍で推奨されていますが、実際にはすべての新しいコンパイラで、これによってパフォーマンスが大幅に向上することはありません。

score -2 · Accepted Answer

文字列の代わりに char 配列を使用します (文字列クラスは舞台裏で多くのことを行います)。

c++ - 非常に遅いランダム文字列ジェネレータ

5 に答える 5

Related

Reference