1

我有一个std::list我目前正在使用 Fisher-Yates shuffle 随机化（参见http://en.wikipedia.org/wiki/Fisher-Yates_shuffle）。总而言之，我的代码在列表中执行了以下步骤：

  1. 循环遍历list.
  2. 从当前位置开始用随机选择的元素交换元素，包括它自己。

因为列表不提供随机访问，这意味着我在第 1 步中迭代整个列表，并且对于每个元素我再次迭代，从那时起平均超过一半的剩余元素。这是我的程序性能的一个主要瓶颈，所以我正在寻求改进它。由于其他原因，我需要继续list用作我的容器，但我正在考虑vector在我的 randomize 函数开始时转换为 a ，然后在最后转换回list。我的列表通常包含 300 - 400 个项目，所以我猜想容器之间的转换成本是值得的，以避免按顺序遍历这些项目。

我的问题是：这似乎是优化代码的最佳方式吗？有没有更好的办法？

4

1 回答 1

4

一个简单的改进是将数据复制到向量中，将向量打乱，然后将其复制回列表中。这就是 Max 和 PeskyGnat 在评论中所建议的：

vector<int> myVector(myList.size());
copy(myList.begin(), myList.end(), myVector.begin());
random_shuffle(myVector.begin(), myVector.end());
list<int> myListShuffled(myVector.begin(), myVector.end());

这个实现非常快。但是，它将在向量上执行三遍，您可以通过自己实现 shuffle 将其减少到两遍：

vector<int> myVector(myList.size());
int lastPos = 0;
for(list<int>::iterator it = myList.begin(); it != myList.end(); it++, lastPos++) {
    int insertPos = rand() % (lastPos + 1);
    if (insertPos < lastPos) {
        myVector[lastPos] = myVector[insertPos]; 
    }

    myVector[insertPos] = *it;
}

list<int> myListShuffled(myVector.begin(), myVector.end());

由于第一个版本更容易理解且不易出错，因此几乎总是更可取...除非这段代码可能对您的性能至关重要（并且您通过测量确认了这一点。）

编辑：顺便说一句，由于您正在查看 Wikipedia 文章，因此第二个代码示例使用了 Fisher-Yates 的“由内而外”变体。

于 2012-04-17T19:31:45.323 回答