C++随机迭代 vector

Question

我正在开发一个多线程程序，其中所有线程共享一些 vector (只读)。每个线程的目标是遍历整个 vector 。尽管如此，所有线程都必须以不同的方式访问这个 vector 。

由于 vector 是 const 并且在所有线程之间共享，我不能使用 random_shuffle 并对其进行迭代。现在我的解决方案是构建一个交叉引用 vector ，它将包含共享 vector 上的索引，然后打乱这个 vector ，即

     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)它不是很有效，因为每个线程都需要在访问共享的之前访问其交叉引用 vector ，(2)由于所需的内存量，我有一些性能问题:共享 vector 非常大，我有很多线程和处理器。

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

Answer 1

您可以使用 primitive root modulo n 的代数概念.基本上

If n is a positive integer, the integers between 1 and n − 1 that are coprime to n form the group of primitive classes modulo n. This group is cyclic if and only if n is equal to 2, 4, p^k, or 2p^k where p^k is a power of an odd prime number

Wikipedia 展示了如何使用 3 作为生成器来生成 7 以下的数字。

从这个语句中你可以推导出一个算法。

1. 拿你的号码n
2. 找到下一个大于n
的素数 m
3. 为您的每个线程在 2 和 m
之间选择一个唯一的随机数 F(0)
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 数字都会出现。

复杂性:

• 第 2 步:完成一次，复杂度相当于找到最多 n 个素数，即 sieve of Eratosthenes
• Step 3 : 完成一次，可以选择2、3、4、5等...低至O(thread count)
• 第 4 步:O(m) 时间，每个线程在空间中 O(1)。您不需要存储 F(i)。您只需要知道第一个值和最后一个值。这与增量的属性相同