C++如何随机遍历向量

Question

C++如何随机遍历向量

c++multithreadingalgorithmvectorrandom-access

17

我正在编写一个多线程程序，所有线程共享一些向量（只读）。每个线程的目标是遍历整个向量。然而，所有线程必须以不同的方式访问该向量。

由于该向量是const并且在所有线程之间共享，因此我不能使用random_shuffle并仅对其进行迭代。目前我的解决方案是构建一个交叉引用向量，其中包含共享向量上的索引，然后随机打乱该向量，即：

     std::vector<int> crossref(SIZE) ; // SIZE is the size of the shared vector
     std::iota (std::begin(crossref), std::end(crossref), 0); // Fill with indices ref 
     std::mt19937 g(SEED); // each thread has it own seed.
     std::shuffle (crossref_.begin(), crossref_.end(), g); // Shuffle it

然而，这样做会揭示一些问题：(1)效率不高，因为每个线程在访问共享变量之前都需要访问其交叉引用向量，(2)由于所需存储的内存量很大，我遇到了一些性能问题：共享向量非常大，而且我有很多线程和处理器。

有没有人有一些改进的想法，可以避免需要额外的内存？

- Esus

访问std::vector的时间复杂度为O(1)，因为它支持随机访问。同时，并不能保证所有线程都有不同的crossref std::vector，因此可能发生两个线程以相同方式迭代向量的情况。 - Zereges

我会使用一个由所有线程共享的单个洗牌索引堆栈，该堆栈受到并发访问的保护。 - Peter - Reinstate Monica

@Zereges - 当然可以，但问题是共享向量几乎适合缓存，因此每次线程访问crossref向量时都会使缓存失效，这不是高效的做法。 - Esus

我可能也误读了任务。显然，每个向量都必须接触到每个元素，并且每个元素以不同的顺序出现。这必然需要为每个线程创建一些数据结构。可能只需要一个布尔值，但仍然如此。 - Peter - Reinstate Monica

1

@PeterSchneider 那样做会失去多线程的意义，因为每个线程都需要自己的排列。其他所有线程将不得不等待当前线程使用其排列。 - UmNyobe

显示剩余9条评论

5个回答

6

如果我理解正确，您想以增量方式生成随机置换，即您想调用函数f n次，以便它生成从1到n的所有排列数字，因此该函数具有恒定的内存。

如果您希望在排列中获得均匀分布，我怀疑这是不存在的，但您可能会满意于排列集合的子集。

如果是这种情况，您可以通过选择与n互质的数字p，并计算对于[1，n]中的每个i：i.p（mod n）来生成排列。例如，如果n=5且p=7，则7％5=2，14％5=4，21％5=1，28％5=3，35％5=0。您可以组合多个这样的函数以获得令您满意的结果...

- Jean-Baptiste Yunès

你的意思是，如果每个线程都有自己不同的 p 素数与 n 相乘，那么每个线程只需通过执行 for each i in [1,n] : i.p (mod n) 来迭代其排列的整个向量。如果是这样的话，我可以离线预先计算一组 p 集合，我理解得对吗？ - Esus

没错，就是这样。如果你认为这个函数不够强大，那么可以结合偏移起点，或者使用两个不同的质数进行两次计算。你也可以从n到1倒序计算等等。一些不同的组合可能更适合你的需求。 - Jean-Baptiste Yunès

Jean，如果质数p能够整除n，那么这种方法是行不通的。 - UmNyobe

我怀疑这会导致随机性较弱。然而，OP并没有提到随机性的质量，只是要求排列在线程之间必须不同，因此这个答案满足了这一点。 - leemes

是的，它提供了很差的随机性。 - Jean-Baptiste Yunès

@Esus所需的函数不能是良好的随机生成器：每次生成样本时都会失去部分随机性。实际上，最后一个样本的条件概率等于1。 - NicolaSysnet

2

似乎这位博主以一种非常好的方式解决了你的问题。

他在帖子的第一行说：在本文中，我将展示一种方法，制作一个迭代器，以随机顺序访问列表中的项目，只访问每个项目一次，并告诉您何时访问完所有项目并完成。它不需要存储洗牌过的列表，也不必跟踪已经访问过的项目。他利用可变长度块密码算法的强大功能来生成数组中的每个索引。

- NicolaSysnet

确实，似乎排列比以前的答案更好，因为它混合了代数和murmurhash。我是对的吗？ - Esus

在Feistel网络迭代中，它使用murmurhash作为舍入函数，但他还指出您可以使用任何其他类型的扩展。那个哈希只是给了他好的结果。 - NicolaSysnet

2

如果内存是您最大的问题，则必须将CPU周期与内存空间交换。

例如，c++的std::vector<bool> (http://en.cppreference.com/w/cpp/container/vector_bool)是一个位数组，因此非常节省内存。

每个线程都可以有自己的vector<bool>来指示它是否已经访问了特定的索引。然后，您需要使用CPU周期来随机选择尚未访问过的索引，并在所有bool都为true时终止。

- emvee

1

搜索未排序的布尔向量中的“false” n 次，即 O(n^2)，而不是 n 个单独的数组访问，这样做会使任何事情更快吗？ - deviantfan

好的，OP明确表示内存是他的主要问题。你不能同时拥有空间效率和CPU效率。 - emvee

请注意OP的问题：“有没有一些改进的想法，可以避免需要额外的内存？” - emvee

好的，你得分了。而且，让它既快又占用更少内存似乎几乎不可能。 - deviantfan

如果每个线程都可以拥有自己的排列，并且只需要一点额外的内存，我愿意牺牲一些CPU效率。 - Esus

1

显然问题出在最后几次迭代上。您可以通过切换到基于索引的版本来提高最后10%迭代的性能。当达到限制时，收集所有false条目的索引，对其进行置换并使用它们作为索引列表。与原始算法相比，这保留了“O(n)”时间但仍降低了内存消耗。然而，时间线将少一些“连续性”；在切换算法时，线程会暂停工作一段时间。这可能是不完美的，具体取决于应用程序。 - leemes

1

这不是完整的答案，但它应该能引导我们找到正确的解决方案。

您已经写了一些假设：

(1) 它不是很高效，因为每个线程在访问共享数据之前都需要访问其交叉引用向量，

这很不可能是真的。我们正在谈论一个间接查找。除非您的参考数据确实是int向量，否则这将代表您执行时间的微不足道的部分。如果您的参考数据是int向量，则只需制作N个副本并对其进行混洗即可...

(2) 由于所需内存的数量很大，我有一些性能问题：共享向量非常大，而且我有很多线程和处理器。

有多大？您测量过吗？向量中有多少个离散对象？每个对象有多大？

有多少线程？

有多少处理器？

您有多少内存？

您是否对代码进行过分析？您确定性能瓶颈在哪里吗？您考虑过更优雅的算法吗？

- Richard Hodges

我使用了128个线程和128个专用核心。我使用一个int向量，它没有填满整个内存，但这是对我的问题的公平简化。我已经使用了分析器，并确信这部分是瓶颈。我还使用了专用内存分配器。“你考虑过更优雅的算法吗？”是的，但算法本身已经很优雅了，问题在于如何高效地编写这个优雅的算法。 - Esus

向量中的值需要是整数吗？它们可以是short类型吗？ - Richard Hodges

不，它们不能... 我也正在研究更详细的范围压缩解决方案，但目前仍处于实验阶段。 - Esus

没有更多关于问题域的了解，很难进一步发表评论。 - Richard Hodges

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- UmNyobe · Accepted Answer

你可以使用模n原根的代数概念。基本上，如果n是正整数，则在1到n-1之间与n互质的整数形成模n的原始类群。当且仅当n等于2、4、p^k或2p^k（其中p^k是奇质数的幂）时，该群是循环群。维基百科显示了如何使用3作为生成器生成小于7的数字。

从这个声明中，您可以得出一个算法。

1. 取您的数字n 2. 找到比n大的下一个质数m 3. 对于每个线程，选择一个唯一的随机数F(0)，介于2和m之间 4. 使用F(i+1)=(F(i)*F(0)) mod m计算下一个索引。如果该索引在[0，n]范围内，则访问该元素。否则，转向下一个索引。 5. 在m-1次迭代（或获得1时）后停止。

因为m是质数，所以2到m-1之间的每个数字都与m互质，因此是序列{1 ... m}的生成器。您保证前m-1步中没有数字重复，并且所有m-1个数字都会出现。

复杂度:

Step 2：完成后，复杂度相当于找到小于n的质数，即埃拉托斯特尼筛法。

Step 3：完成一次后，您可以选择2、3、4、5等。这与O(线程数)同样低。

Step 4：O(m)时间，每个线程O(1)空间。您不需要存储F(i)。您只需要知道第一个值和最后一个值。这与递增具有相同的属性。