当随机化std :: list时提高性能

我有一个std::list，我目前正在使用Fisher-Yates shuffle进行随机化（请参阅http://en.wikipedia.org/wiki/Fisher-Yates_shuffle）。总之，我的代码在列表中执行以下步骤：当随机化std :: list时提高性能

循环遍历list的每个元素。
使用从当前位置开始随机选择的元素（包括其自身）交换元素。

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

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

来源

2012-04-17 JBentley

显示代码本身比描述代码的作用更有帮助。 – Marlon 2012-04-17 14:01:26

交换std :: list元素与std :: vectors相比代价高昂。尝试在交换之前将列表复制到矢量（容易），并查看它是否改善了事情。 – Max 2012-04-17 14:02:11

也许一个德克将是一个选择？它支持列表和向量语义，所以你可以使用STL中的random_shuffle – PeskyGnat 2012-04-17 14:07:05

一个简单的改进就是将数据复制到一个向量中，将向量洗牌并将其复制回列表中。这是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());

该实现速度非常快。但是，它会做三越过矢量，你可以通过实现洗牌自己弄下来到两遍：

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

由于第一个版本是更容易理解和更容易出错，这是几乎总是比较可取的......除非也许这段代码对你的性能至关重要（并且你通过测量证实了这一点）。

编辑：顺便说一句，既然你在看维基百科文章，第二个代码示例使用Fisher-Yates的“内外”变体。

来源

2012-04-17 19:31:45

当随机化std :: list时提高性能

回答

相关问题