C++随机迭代向量

Question

我正在研究一个多线程程序,其中所有线程共享一些向量(只读).每个线程的目标是遍历整个向量.尽管如此,所有线程都必须以不同的方式访问此向量.

由于向量是const并且在所有线程之间共享,我不能使用random_shuffle并且只是迭代它.现在我的解决方案是构建一个crossref向量,它将在共享向量上包含索引,然后对该向量进行混洗,即

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

有没有人有一些改进的想法,将避免额外的内存需求？

Answer 1

您可以使用原始根模数n的代数概念.基本上

如果n是正整数,则1和n - 1之间的整数与n互质,形成以n为模的原始类组.当且仅当n等于2,4,p ^ k或2p ^ k时,该组是循环的,其中p ^ k是奇素数的幂.

维基百科显示如何7使用3as generator 生成以下数字.

从这个陈述中你可以得到一个算法.

1. 记下你的号码 n
2. 找到m大于的下一个素数n
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数字都会出现.

复杂性:

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

Answer 2

如果我理解你想要以增量方式生成随机排列,即你想调用函数f的n次,以便它生成从1到n的所有置换数,这样该函数就具有恒定的内存.

如果你想在排列中获得均匀分布,我怀疑它是否存在,但是你可能对这组排列的一个子集感到满意.

如果是这种情况,您可以通过使用数字p prime和n来生成置换,并计算[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.你可以结合几个这样的功能来获得满足你的东西......