C++随机迭代向量
C++ iterate vector randomly
我正在开发一个多线程程序，其中所有线程共享一些向量（只读）。每个线程的目标是遍历整个向量。尽管如此，所有线程都必须以不同的方式访问此向量。
由于向量是 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）由于所需的内存量，我遇到了一些性能问题: 共享向量非常大，我有很多线程和处理器。
有没有人有一些可以避免额外内存需求的改进想法？
如果内存是您最大的问题，那么您将不得不交换 CPU 个内存周期 space。
例如c++ 的 std::vector<bool> (http://en.cppreference.com/w/cpp/container/vector_bool) 是一个位数组，因此内存效率很高。
每个线程都可以有自己的 vector<bool> 指示它是否访问了特定索引。然后你必须使用 CPU 循环随机选择一个它还没有访问过的索引，并在所有 bool 都为 true.
时终止
如果我理解你想以增量方式生成随机排列，即你想调用 n 次函数f 以便它生成从 1 到 n 的所有排列数字，因此该函数具有常量内存。
如果您想在排列之间获得均匀分布，我怀疑它是否存在，但您可能对排列集的一个子集感到满意。
如果是这种情况，您可以通过取一个数 p 与 n 的素数来生成排列，并计算每个 i 在 [1,n] 中：i.p (mod n)。
例如，如果您有 n=5 和 p=7，则 7%5=2、14%5=4、21%5=1、28%5=3、35%5=0。您可以组合几个这样的功能来获得令您满意的东西...
您可以使用 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
维基百科显示了如何使用 3 作为生成器生成 7 以下的数字。
从这个陈述你推导出一个算法。
- 取你的号码
n
- 找到下一个大于
n 的质数m
- 为您的每个话题选择一个唯一的随机数
F(0)，介于 2 和 m 之间
- 使用
F(i+1) = (F(i) * F(0)) mod m计算下一个索引。如果该索引在 [0, n] 范围内，则访问该元素。如果不去下一个索引。
- 在
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, etc... 低至
O(thread count)
- 第 4 步：
O(m) 次，每个线程 O(1) space。您不需要存储 F(i)。您只需要知道第一个值和最后一个值。这与 incrementation 的属性相同
这不是一个完整的答案，但它应该引导我们找到正确的解决方案。
您写了一些我们可以假设的东西：
(1) it is not very efficient since every thread needs to access its
crossref vector before accessing the shared one,
这不太可能是真的。我们正在谈论一种间接查找。除非您的参考数据真的是一个整数向量，否则这将代表您执行时间的无穷小部分。如果您的参考数据是一个整数向量，那么只需复制它的 N 个副本并将它们打乱...
(2) i have some performances issue because of the amount of memory
required : the shared vector is very big and i have a lot of thread
and processors.
有多大？你测量了吗？向量中有多少个离散对象？每个有多大？
多少线程？
有多少个处理器？
你有多少内存？
你分析过代码了吗？您确定性能瓶颈在哪里吗？你考虑过更优雅的算法吗？
看来 this 这个人很好地解决了你的问题。
这是他在 post 的第一行中所说的： 在这个 post 中，我将展示一种制作迭代器的方法，该迭代器将访问项目在随机顺序的列表中，只访问每个项目一次，并告诉您何时访问所有项目并完成。它执行此操作时不会存储经过打乱的列表，也不必跟踪它已经访问过的项目。
他利用可变位长度分组密码算法的强大功能来生成数组中的每个索引。
我正在开发一个多线程程序，其中所有线程共享一些向量（只读）。每个线程的目标是遍历整个向量。尽管如此，所有线程都必须以不同的方式访问此向量。
由于向量是 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）由于所需的内存量，我遇到了一些性能问题: 共享向量非常大，我有很多线程和处理器。
有没有人有一些可以避免额外内存需求的改进想法？
如果内存是您最大的问题，那么您将不得不交换 CPU 个内存周期 space。
例如c++ 的 std::vector<bool> (http://en.cppreference.com/w/cpp/container/vector_bool) 是一个位数组，因此内存效率很高。
每个线程都可以有自己的 vector<bool> 指示它是否访问了特定索引。然后你必须使用 CPU 循环随机选择一个它还没有访问过的索引，并在所有 bool 都为 true.
如果我理解你想以增量方式生成随机排列，即你想调用 n 次函数f 以便它生成从 1 到 n 的所有排列数字，因此该函数具有常量内存。
如果您想在排列之间获得均匀分布，我怀疑它是否存在，但您可能对排列集的一个子集感到满意。
如果是这种情况，您可以通过取一个数 p 与 n 的素数来生成排列，并计算每个 i 在 [1,n] 中：i.p (mod n)。
例如，如果您有 n=5 和 p=7，则 7%5=2、14%5=4、21%5=1、28%5=3、35%5=0。您可以组合几个这样的功能来获得令您满意的东西...
您可以使用 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
维基百科显示了如何使用 3 作为生成器生成 7 以下的数字。
从这个陈述你推导出一个算法。
- 取你的号码
n - 找到下一个大于
n的质数 - 为您的每个话题选择一个唯一的随机数
F(0)，介于2和m 之间
- 使用
F(i+1) = (F(i) * F(0)) mod m计算下一个索引。如果该索引在[0, n]范围内，则访问该元素。如果不去下一个索引。 - 在
m - 1次迭代后停止（或者当你获得 1 次时，它是一样的）。
m
因为 m 是质数，所以 2 和 m-1 之间的每个数字都与 m 互质，序列 {1 ... m} 的生成器也是如此。您保证不会在前 m - 1 个步骤中重复任何数字，并且会出现所有 m - 1 个数字。
复杂度：
- 第 2 步：完成一次，复杂度相当于寻找 n 个素数，即 sieve of Eratosthenes
- Step 3 : 完成一次，你可以选择 2, 3 ,4, 5, etc... 低至
O(thread count) - 第 4 步：
O(m)次，每个线程O(1)space。您不需要存储 F(i)。您只需要知道第一个值和最后一个值。这与 incrementation 的属性相同
这不是一个完整的答案，但它应该引导我们找到正确的解决方案。
您写了一些我们可以假设的东西：
(1) it is not very efficient since every thread needs to access its crossref vector before accessing the shared one,
这不太可能是真的。我们正在谈论一种间接查找。除非您的参考数据真的是一个整数向量，否则这将代表您执行时间的无穷小部分。如果您的参考数据是一个整数向量，那么只需复制它的 N 个副本并将它们打乱...
(2) i have some performances issue because of the amount of memory required : the shared vector is very big and i have a lot of thread and processors.
有多大？你测量了吗？向量中有多少个离散对象？每个有多大？
多少线程？
有多少个处理器？
你有多少内存？
你分析过代码了吗？您确定性能瓶颈在哪里吗？你考虑过更优雅的算法吗？
看来 this 这个人很好地解决了你的问题。
这是他在 post 的第一行中所说的： 在这个 post 中，我将展示一种制作迭代器的方法，该迭代器将访问项目在随机顺序的列表中，只访问每个项目一次，并告诉您何时访问所有项目并完成。它执行此操作时不会存储经过打乱的列表，也不必跟踪它已经访问过的项目。
他利用可变位长度分组密码算法的强大功能来生成数组中的每个索引。