最快 "trivial" 洗牌向量的方法

Question

我正在研究国际象棋引擎有一段时间了。为了改进引擎，我编写了一些代码，将国际象棋位置从内存加载到一些调谐器代码中。我的机器上大约有 1.85B fens，总计 40Gb（每个位置 24B）。

加载后，我得到一个位置向量：

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 个位置，理想情况下 none 这些位置来自同一个游戏。因此我在使用数据之前做了一些初步的排序。

我目前的洗牌方式是这样的：

    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

需要做出权衡：在访问 Position 时以间接为代价，改组 std::vector<size_t> 索引比改组 std::vector<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';
}

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

对于 std::list 我不认为按顺序迭代或通过随机迭代器迭代之间有很大区别。另一方面，对于 std::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))]);

另一方面，打乱索引然后重新排列向量只需要 copy/move 每个元素一次（当有额外内存可用时）。

Answer 2

随机性并不能保证采样不会从您想要避免的同一游戏中获得位置。我建议以下伪洗牌确实可以防止从同一游戏中抽样（给定足够大的人口）：

设N为最长游戏的长度+1
设E为迭代器到最后
让我成为随机索引
while E != begin
- 如果 i > E - 开始
  - i %= E - 开始
  - --N
- 交换 i 和 std::prev(E)
- 减少E
- 我+=N

最快 "trivial" 洗牌向量的方法

Fastest "trivial" way of shuffling a vector

c++

shuffle