c++ - 加扰输入算法的效率

Question

我目前正在编写一个程序，它的大部分工作都是在 CPP 中完成的，它接收一个带有编号索引的文件，然后根据初始输入推出一个打乱的测验，因此从理论上讲，没有两个是相同的。 这是代码

   // There has to be a more efficient way of doing this...                      
  for (int tempCounter(inputCounter);
       inputCounter != 0;
       /* Blank on Purpose*/) {
    randInput = (rand() % tempCounter) + 1;

    inputIter = find (scrambledArray.begin(),
                      scrambledArray.end(),
                      randInput);

    // Checks if the value passed in is within the given vector, no duplicates.
    if (inputIter == scrambledArray.end()) {
      --inputCounter;
      scrambledArray.push_back(randInput);
    }
  }

第一条评论说明了我的问题。在正常情况下不会发生这种情况，但如果将其应用于更大的应用程序角度会怎样。这可行，但如果用户想要打乱 10000 个左右的结果，则效率非常低。我觉得在这一点上，这将是非常低效的。 我不是在谈论代码的效率，因为在缩短一些序列并压缩它以使其更漂亮时，我或多或少是在教某人，并且在达到这一点后我得出的结论是这可能是以更好的方式完成，只是不知道它可能是哪种方式......

Answer 1

所以您只想打乱数字 1..N？是的，有一种更有效的方法可以做到这一点。您可以使用 std::iota构造您的 vector :

// first, construct your vector:
std::vector<int> scrambled(N);
std::iota(scrambled.begin(), scrambled.end(), 1);

然后 std::shuffle它:

std::shuffle(scrambled.begin(), scrambled.end(),
             std::mt19937{std::random_device{}()});

如果你没有 C++11，上面的代码看起来像这样:

std::vector<int> scrambled;
scrambled.reserve(N);
for (int i = 1; i <= N; ++i) {
    scrambled.push_back(i);
}
std::random_shuffle(scrambled.begin(), scrambled.end());