c++ - 最快的 "trivial"洗牌 vector 的方式

Question

我在国际象棋引擎上工作了一段时间。为了改进引擎，我编写了一些代码，将国际象棋位置从内存加载到一些调谐器代码中。我的机器上大约有 1.85B fens，加起来达到 40Gb(每个位置 24B)。

加载后，我得到一个位置 vector :

struct Position{
   std::bitset<8*24> bits{};
}

void main(){
    std::vector<Position> positions{};
   
    // mimic some data loading
    for(int i = 0; i < 1.85e9; i++){
        positions.push_back(Position{})
    }    

    // ...
}

数据按以下方式组织:

The positions are taken from games where the positions are seperated by just a few moves. Usually about 40-50 consecutive moves come the same game / line and are therefor somewhat equal.

最终我会在一个批处理中读取 16384 个位置，理想情况下这些位置都不是来自同一个游戏。因此，我在使用数据之前进行了一些初步排序。

我目前的洗牌方法是这样的:

    auto rng = std::default_random_engine {};
    std::shuffle(std::begin(positions), std::end(positions), rng);

不幸的是，这需要一些时间(大约 1-2 分钟)。由于我不需要完美的洗牌，我假设存在一些更简单的洗牌。

我的第二个方法是:

    for(int i = 0; i < positions.size(); i++){
        std::swap(positions[i], positions[(i*16384) % positions.size()]);
    }

这将确保在一个批处理中不会有来自同一游戏的位置，并且由 16384 个条目均匀分布。

我想知道是否有更简单、更快的解决方案。特别是考虑到模运算符需要安静的一些时钟周期。

我很高兴任何“微不足道”的解决方案。

问候语芬恩

Answer 1

需要做出权衡:将 a a std::vector<size_t> 洗牌的指数预计比改组 std::vector<Position> 更便宜在访问 Position 时以间接为代价s 通过打乱索引。实际上 std::iota 的 cppreference 示例正在沿着这条线做一些事情(它使用迭代器):

#include <algorithm>
#include <iostream>
#include <list>
#include <numeric>
#include <random>
#include <vector>
 
int main()
{
    std::list<int> l(10);
    std::iota(l.begin(), l.end(), -4);
 
    std::vector<std::list<int>::iterator> v(l.size());
    std::iota(v.begin(), v.end(), l.begin());
 
    std::shuffle(v.begin(), v.end(), std::mt19937{std::random_device{}()});
 
    std::cout << "Contents of the list: ";
    for(auto n: l) std::cout << n << ' ';
    std::cout << '\n';
 
    std::cout << "Contents of the list, shuffled: ";
    for(auto i: v) std::cout << *i << ' ';
    std::cout << '\n';
}

不是直接打乱列表，而是打乱一个迭代器 vector (带有 std::vector 索引也可以)并且 std::shuffle只需要交换迭代器 (/indices) 而不是成本更高的实际元素(在示例中，“交换成本高”的元素只是 int s)。

对于 std::list我不认为按顺序迭代或通过混洗迭代器迭代之间有很大区别。另一方面，对于 std::vector我确实希望产生重大影响。因此，我会打乱索引，然后重新排列 vector 一次，然后进行分析以查看哪个表现更好。

---

PS:如评论中所述，std::shuffle已经是洗牌一系列元素的最佳算法。但是，请注意它平均将每个元素交换两次(可能来自 cppreference 的实现):

for (diff_t i = n-1; i > 0; --i) {
        using std::swap;
        swap(first[i], first[D(g, param_t(0, i))]);

另一方面，打乱索引然后重新排列 vector 只需要复制/移动每个元素一次(当有额外内存可用时)。