从数字和字母中快速生成大量随机字符串

Question

我需要生成一个大小为32个字符的字符串集合（10k，甚至更多），随机从“a-z”，“A-Z”和“0-9”中选择。

目前，我有以下代码（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);
} 

- pepero

---

我可能会使用std::generate，结合lambda表达式和C++11 PRNG功能。但这只是让代码更C++一些，而不是更有效率。另外，预先分配向量/字符串可能是个好主意。 - Some programmer dude

Answer 1

在这个问题上，最好的解决方案是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。

- WhozCraig

---

我宁愿使用std::vector<std::string> strs{n}的方式，然后使用std::generate直接设置条目，并对字符串执行相同操作。与通过std::back_inserter进行操作相比，可能会节省一些周期。 - Some programmer dude

@JoachimPileborg 这就是我使用reserve()的原因。使用实际实例进行预分配会触发所有构造函数（对于std::string来说并不多，但仍然如此）。最终是移动构造函数与移动赋值函数之间的区别，所以如果有差异，我会感到惊讶。如果能够进行测试，那将非常有趣。 编辑：我刚刚注意到你评论中的“generate”。如果确实有显着差异，那将非常有趣。 - WhozCraig

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

- Brett Hale

Answer 3

您无法做得比 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);
}

在线演示。

- Bernhard Barker

Answer 4

从算法效率上来说没有太大的改进，但我建议

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

- jester

Answer 5

考虑使用预分配的缓冲区来生成随机字符串。 此外，您可以预先生成一些随机块并对它们进行排列。

- Eugene