5

我必须从“az”、“AZ”和“0-9”中随机生成一大组（10k 甚至更多）字符串，大小为 32 个字符。

到目前为止，我的脑海中有以下代码（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

请注意，您可能会对它的运行速度感到惊讶。引擎盖下发生了很多事情。rand() % n最后，这使用了 C++11 随机库，特别是均匀分布，它消除了传统解决方案中通常遇到的模数偏差n。

于 2013-10-22T11:07:41.350 回答
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)可能不会那么昂贵，因为它可能使用对象的移动分配std::string。std::string对象在其实现中通常也具有“短字符串”优化 (SSO)。

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

你不能做得比O(mn)（m你的字符串的长度（这里= 32）并且n是字符串的数量）更好。

原因是输出大小为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 回答
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 回答