3

我需要有效地生成随机字符串。在下文中，您将看到我的第一次尝试。我用 gcc 和 -O3 优化级别编译了代码。生成 10^7 个长度为 64 的随机字符串需要18.5 秒：

#include <iostream>
#include <random>
#include <algorithm>

std::string chars {"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()`~-_=+[{]{|;:'\",<.>/?"};
std::random_device rd;
std::mt19937 generator(rd());
  
std::string rand_str (int length) {
  std::string output (chars);
  std::shuffle(output.begin(), output.end(), generator);
  return output.substr(0, length);
}

int main() {
  std::string str;
  for (long i=0; i<10000000; ++i)
      str = rand_str (64);
}

我检查std::sample了c++17，它并不比上述方法快。此外，它不会改变字符的顺序，所以它不是真正的随机。

编辑：这std::shuffle不是一个好的选择，因为它不允许重复。根据评论，我修改了代码。这次 10^7 个随机数需要9 多分钟。

std::string rand_str (size_t length) {
  const size_t char_size = chars.size();
  std::uniform_int_distribution<> random_int (0, char_size - 1);
  std::string output;
  for (size_t i=0; i<length; ++i)
    output.push_back(chars[random_int(generator)]);
  return output;
}

问题

  • 在现代 C++ 中是否有更有效的方法来做到这一点？

我感谢任何改进代码的建议。

4

1 回答 1

1 
#include <iostream>
#include <random>
#include <algorithm>
#include <chrono>

std::string chars {"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()`~-_=+[{]{|;:'\",<.>/?"};
std::random_device rd;
std::mt19937 generator(rd());
  
std::string rand_str(int length) {
  std::string output;
  output.reserve(length);

  while(length>0)
  {
      auto randNumb = generator();
      while(randNumb > 93 && length--)
      {
        output.push_back(chars[randNumb%93]);
        randNumb/=93;
      }
  }
  return output;
}

int main() {
  auto startTP = std::chrono::system_clock::now();
  std::string rand_bytes;
  for (long i=0; i<10000000; ++i)
      rand_bytes = std::move(rand_str(64));
  auto endTP = std::chrono::system_clock::now();

  std::cout << "This took: " << std::chrono::duration_cast<std::chrono::microseconds>(endTP-startTP).count() << std::endl;
}

这在我的机器上大约需要 3 秒。诀窍是尽可能少地调用随机数生成器并且只分配一次内存。

我正在做的是将 randNumber 从基数 10 转换为基数 93（字符的长度）。之后，我使用每个基数 93 位作为不同的随机数。这为每个生成的随机数提供了大约 5 个数字。

于 2020-08-11T13:27:50.410 回答