5

「az」、「AZ」、「0-9」からランダムに 32 文字の文字列の大規模なセット (10k 以上)を生成する必要があります。

これまでのところ、次のコード (O(N*32)) が頭に浮かびますが、それを行うためのより良い方法があるかどうか疑問に思います。

int N = 10000;           
vector<string> vecStr;

for (int index=0; index<N; index++)
{
  string str;
  for (int i = 0; i < 32; ++i)
  {
    int randomChar = rand()%(26+26+10);        
    if (randomChar < 26)
      str += 'a' + randomChar;
    else if (randomChar < 26+26)
      str += 'A' + randomChar - 26;
    else
      str += '0' + randomChar - 26 - 26;
  }
  vecStr.push_back(str);
}
4

5 に答える 5

9

O(N*len) よりも優れたソリューションを見つけることはできません。ここで、N は文字列の数であり、len はその中のそれぞれの長さです。そうは言っても、これを行うための最も高密度のコードを書くことで獲得できる変色したステッカーがどこかにあると確信しています。

#include <iostream>
#include <iterator>
#include <vector>
#include <random>
#include <algorithm>

int main()
{
    static const char alphabet[] =
        "abcdefghijklmnopqrstuvwxyz"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "0123456789";

    static const size_t N_STRS = 10000;
    static const size_t S_LEN = 32;

    std::random_device rd;
    std::default_random_engine rng(rd());
    std::uniform_int_distribution<> dist(0,sizeof(alphabet)/sizeof(*alphabet)-2);

    std::vector<std::string> strs;
    strs.reserve(N_STRS);
    std::generate_n(std::back_inserter(strs), strs.capacity(),
        [&] { std::string str; 
              str.reserve(S_LEN); 
              std::generate_n(std::back_inserter(str), S_LEN,
                   [&]() { return alphabet[dist(rng)];}); 
              return str; });
    std::copy(strs.begin(), strs.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
    return 0;
}

出力(簡潔にするために 9990 行を省略 =P)

MRdeOWckfKy8GTFt0YmQMcM6SABJc934
XvdcatVsv6N9c1PzQGFFY6ZP943yIrUY
xpHzxUUyAizB6BfKldQzoePrm82PF1bn
kMUyPbflxk3yj3IToTFqYWnDq6aznKas
Ey0W5SF37VaeEY6PxWsBoxlNZTv9lOUn
iTx7jFRTHHW6TfYl7N3Hne4yu7kgAzp5
0ZamlaopjLyEvJbr6fzJPdXmjLOohtKh
6ZYeqj47nCMYKj0sCGl2IHm28FmvuH8h
oTDYRIA1trN1A2pQjsBwG3j9llzKIMhw
5zlpvSgTeLQ38eFWeSDoSY9IHEMHyzix

そして、これがどれほど速く実行されるかに驚くかもしれません。ボンネットの下でかなり多くのことが起こっています。最後に、これは C++11 ランダム ライブラリ、特に一様分布を使用します。これによりrand() % n、特定のn.

于 2013-10-22T11:07:41.350 に答える
2

(は文字列の長さO(mn)(ここでは = 32) であり、 は文字列の数です)よりも良いことはできません。mn

その理由は、出力サイズがであり、論理的には、出力内の各文字に対してO(mn)少なくとも作業を行う必要があるためです。O(1)

O(mn)文字列の再割り当てが発生する可能性があるため、アルゴリズムは よりも少し遅くなる可能性があることに注意してください。これを防ぐには、次を使用できますstring::reserve。

int M = 32;
...
  string str;
  str.reserve(M);
  for (int i = 0; i < M; ++i)
...

しかしM、それがわずか 32 であることを考えると、大きな違いはありそうにありません。

そして、楽しみのために、コードのバリエーションを次に示します。

int N = 10000, M = 32;
vector<string> vecStr;
string alphabet("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789");
for (int index = 0; index < N; index++)
{
  string str;
  str.reserve(M);
  for (int i = 0; i < M; ++i)
  {
    str += alphabet[rand() % alphabet.length()];
  }
  vecStr.push_back(str);
}

ライブデモ。

于 2013-10-22T10:57:13.303 に答える
2

C++11 で利用できる乱数ジェネレーターと乱数分布を検討することもできます。

例えば、

const char alphanumeric[] = "0 .. 1A .. Za.. z";

std::default_random_engine rng;
std::uniform_int_distribution<> dist (0, sizeof(alphanumeric) - 1);

...

for (int i = 0; i < 32; i++)
    str += alphanumeric[dist(rng)];

オブジェクトの移動割り当てをvecStr.push_back(str)使用する可能性があるため、それほど高価ではない可能性があると付け加えておきます。多くの場合、オブジェクトの実装には「短い文字列」の最適化 (SSO) も含まれています。std::stringstd::string

vector<string> vecStr (N);
...
vecStr[index] = std::move(str);
于 2013-10-22T10:56:15.393 に答える
0

アルゴリズム効率に関してはあまり改善されていませんが、私は提案します

void random_string(char *s, int len=32) {
static const char alphabet[] =
    "0123456789"
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "abcdefghijklmnopqrstuvwxyz";

for (int i = 0; i < len; ++i) {
    s[i] = alphabet[rand() % (sizeof(alphabet) - 1)];
  }

 s[len] = '\0';
}
于 2013-10-22T10:49:45.303 に答える
0

ランダム文字列に事前割り当てバッファを使用することを検討してください。また、いくつかのランダムなチャンクを事前に生成し、それらを並べ替えることもできます。

于 2013-10-22T10:46:34.853 に答える