#include <cmath>
#include <functional>
#include <thread>
#include <vector>
// Invalidates the multiples of the given integer
// in a given boolen vector
template<typename Integer>
void apply_prime(Integer prime, std::vector<bool>& vec)
{
for (Integer i = prime*2u ; i < vec.size() ; i += prime)
{
vec[i] = false;
}
}
template<typename Integer>
auto sieve_eratosthenes(Integer n)
-> std::vector<Integer>
{
std::vector<bool> is_prime(n, true);
std::vector<std::thread> threads;
std::vector<Integer> res;
auto end = static_cast<Integer>(std::sqrt(n));
for (Integer i = 2u ; i <= end ; ++i)
{
// When a prime is found,
// * add it to the res vector
// * spawn a thread to invalidate multiples
if (is_prime[i])
{
res.push_back(i);
threads.emplace_back(apply_prime<Integer>,
i, std::ref(is_prime));
}
}
for (auto& thr: threads)
{
thr.join();
}
// Add the remaining primes to the res vector
for (Integer i = end+1u ; i < is_prime.size() ; ++i)
{
if (is_prime[i])
{
res.push_back(i);
}
}
return res;
}
素数通过两步添加到
res向量中：每个素数\ $ p \ $如\ $ p <\ sqrt {当抛出质数时，在引发相应线程之前添加\ $。其他质数在函数的末尾添加。这是一个示例main：int main()
{
auto primes = sieve_eratosthenes(1000u);
for (auto prime: primes)
{
std::cout << prime << " ";
}
}
我很确定由于并行性我会遇到一些问题，但是由于某种原因，它似乎可以工作。我以正确的顺序得到了预期的结果。可以肯定的是，我想知道我的程序是正确的还是正确的，或者它是否存在一些看不见的线程问题。改进代码并编写了后续问题。
#1 楼
当您正确地假设代码中存在多个与线程相关的问题时，可让您取笑并从常见的可疑之处入手。 。该函数实际上并不需要质数，也不适用于正义。 >
通过执行2步而不是1步，您的循环可以快两倍。
我不是专家，但是我至少可以发现两个问题：
订购：其他线程在主线程到达
apply_prime循环后运行。这会导致错误的结果，因为主线程在没有人说出例如4不是素数之前就将其完全插入strike_out_multiples向量。一点点的情况下，这不再是问题，但至少在旧标准join中是一种专门化，每个值仅使用一位。虽然这为您节省了一些空间，但伴随着仅工作一个位时实际访问8位的成本。这意味着两个线程可能在不同的位上但在同一字节中工作。请考虑以下事项：线程1将false写入位4，而线程2将false写入位6。两者都位于字节0中。 ，true，true，false，true，true，true，true）并存储它们！现在，两个线程之一将比另一个线程晚写入其值，并覆盖另一个线程的错误->更新丢失。仅按字节访问，而仅按字访问（这会导致相同的问题，仅在更大的大小下）。
评论
\ $ \ begingroup \ $
我想将apply_prime设为lambda，但认为不允许多行lambda。实际上，它们是允许的，lambda也可以。
\ $ \ endgroup \ $
–莫文
2014年4月12日19:55在
\ $ \ begingroup \ $
std :: vector
\ $ \ endgroup \ $
– Ben Voigt
14年4月13日在15:11
\ $ \ begingroup \ $
@BenVoigt幸运的是，std :: vector
\ $ \ endgroup \ $
–莫文
14年4月13日在20:46
#2 楼
通常，它是不错的，结构良好的代码，但它依赖于可能无法兑现的承诺。特别地，不能保证同时访问
std::vector<bool>中的不同元素是线程安全的，因为存储字节可能由vector中的多个位共享。考虑另一种方法切东西。每个线程可能负责布尔数组的自己的部分。随着素数的增加，可以将它们分派到每个线程以从相应部分中同时消除。
最好有一个调整参数，使子数组的大小与产生另一个线程的成本保持平衡。
编辑：
我对
main进行了如下修改： br /> int main()
{
auto primes = sieve_eratosthenes(20000000u);
long long s=0;
for (auto prime: primes)
s += prime;
std::cout << s << '\t' << primes.size() << std::endl;
}
所以素数的数量实际上在迭代之间变化（数学家通常认为这是不太可能的！），或者线程争用问题正在显现。正确的数字是：
12273796368896 1270814
12273126258541 1270843
12273106282821 1270780
12272824476679 1270794
编辑2：我浏览了这篇论文，很好地解释了Eratosthenes算法的Sieve并行化的许多可能方法。 >
评论
\ $ \ begingroup \ $
我也只是试图让它计算出高达2000000000的所有素数，并且在线程用完后在我的机器上中止，并抛出一个std :: system_error实例，其中what（）=“资源暂时不可用。 ”
\ $ \ endgroup \ $
–爱德华
2014年4月12日在21:32
\ $ \ begingroup \ $
这可能归结为这个问题：线程在假定的质数上生成。这意味着根据线程的顺序，可以将4视为质数，添加到res并生成线程。虽然为非素数生成线程不是问题（4将false分配给2也会分配false的地方），但将res的push_back可能是向表中添加错误元素的原因。
\ $ \ endgroup \ $
–莫文
2014年4月12日在21:59
\ $ \ begingroup \ $
您能否尝试删除push_back并将最后一个循环从2u转到is_prime.size（）并再次检查？另外，将vector
\ $ \ endgroup \ $
–莫文
2014年4月12日22:00
\ $ \ begingroup \ $
您可能需要阅读本白皮书，以获得有关如何并行化此算法的更多想法。
\ $ \ endgroup \ $
–爱德华
2014年4月12日在22:09
\ $ \ begingroup \ $
也就是说，即使结果现在是一致的，我也可以肯定仍然产生了无用的线程。但是，它们现在仅是无用的且无害。
\ $ \ endgroup \ $
–莫文
2014年4月12日在22:27
#3 楼
忽略高速缓存无效化的内存问题（这会减慢代码速度）。创建线程是相对昂贵的（因为您必须分配堆栈并维护它）。因此，与其创建和销毁线程，不如维护一个线程池并重用这些线程，效果更好。根据经验法则* 1.x（其中x的范围为2 => 5）是您应放入池中的线程数。
评论
\ $ \ begingroup \ $
看来我完全必须了解线程池:)
\ $ \ endgroup \ $
–莫文
2014年4月12日在21:53
\ $ \ begingroup \ $
我通常更喜欢n + 1，其中n是处理器数。在IO重载情况下，可能为n + 2。
\ $ \ endgroup \ $
–艾米莉·L。
15年7月15日在14:26
#4 楼
实际上，线程完全是错误的。到处都有比赛条件。由于这种问题，它没有很多可见的效果，但是仍然是错误的。sieve_eratosthenes中的out循环从2到结束遍历索引，并检查数组元素是否标记为“ prime”。在该循环中，它将启动将数组元素从“素数”更改为“非素数”的线程。无法保证这些线程已经取得了多少进展。因此，当外循环检查4、6、8、9、10、12等是否为质数时，无法保证它们实际上已被标记为非质数。最坏的情况是，外循环为每个i从2开始一个线程，直到这些线程中的任何一个开始运行为止。在不改变正确性的基本筛子的情况下，但是通常该程序不会执行应做的事情。
线程将布尔值设置为false。他们倾向于多次将相同的值设置为false。例如，2和3的线程都将6的倍数设置为false。写入同一变量的两个线程被称为“竞争条件”，并且不仅仅是坏的。在这种情况下，它没有效果，因为两个线程都将相同的布尔值设置为false。通常，它将导致严重的错误。
大多数认真研究素数的人都会使用大量数字并使用位数组来保护空间。当您这样做时，此线程问题将使您丧命，因为如果一个线程试图清除一个存储字中的一位，而另一个线程试图清除另一位，则您很有信心将丢失这些操作之一。
评论
\ $ \ begingroup \ $
我在编写代码时考虑了竞争条件（多个线程在同一位置运行），但是由于已知线程在同一位置执行完全相同的操作，因此我认为这不是问题（希望他们都写错误并且不会触发不确定的行为）。但是，所有其他问题都是真正的问题。
\ $ \ endgroup \ $
–莫文
14年4月13日在8:59
\ $ \ begingroup \ $
@Morwenn：有一个write-> read竞赛以及冗余写入，该读取发生在if（is_prime [i]）中
\ $ \ endgroup \ $
– Ben Voigt
14年4月13日在15:11
\ $ \ begingroup \ $
我今天读了一些有关数据竞赛的内容，而且确实有不确定的行为。我并不认为冗余写入是个问题：如果类型是原子的，它们可能不会比读取慢于写入。
\ $ \ endgroup \ $
–莫文
14年4月13日在15:14
\ $ \ begingroup \ $
未定义的行为是未定义的行为。这意味着您绝对无法预测会发生什么。它可能适用于您当前的编译器。它可能99％的时间在您当前的编译器上工作，这比根本不工作要糟糕。使用多线程，这种方法“很好，它没有正式起作用，但是对我来说已经足够了”，这绝对是一场灾难。任何比“保证工作正常”还差的事情都会对您造成伤害。
\ $ \ endgroup \ $
– gnasher729
14年4月13日在23:24
\ $ \ begingroup \ $
@ gnasher729从昨天开始，我做了更多研究，您完全正确。
\ $ \ endgroup \ $
–莫文
14年4月14日在11:41
#5 楼
没有其他答案提到当传递给筛子的值是质数时实际上存在问题。例如，sieve_eratosthenes(7u)返回包含2 3 5的向量。这是由于向量is_prime太短了一个元素：它考虑\ $ 0 \ $和\ $ n-1 \ $之间的元素，而它应该考虑\ $ 0 \ $和\ $ n \ $之间的元素。它应该声明为：在lambda捕获中通过引用apply_prime也可以删除is_prime和对应的std::ref。这是经过修改的#include <functional>：std::vector<bool> is_prime(n+1u, true);
评论
\ $ \ begingroup \ $
公平地说：您没有指定是否应该测试输入数字，这表明缺少规范（前提条件）。
\ $ \ endgroup \ $
–没人远离SE
2014年4月13日在13:43
\ $ \ begingroup \ $
@Nobody是的，但是我感到数学整数范围通常趋于包容。同样不是维基百科的伪代码说“不超过n”。它似乎具有包容性。
\ $ \ endgroup \ $
–莫文
14年4月13日在13:49
\ $ \ begingroup \ $
您还可以将i = prime * 2u替换为i = prime * prime，因为所有小于\ $ p ^ 2 \ $的复合数字都将作为较小素数的倍数消除。
\ $ \ endgroup \ $
–爱德华
2014年4月13日15:45
\ $ \ begingroup \ $
@Edward但这也意味着，我可以将i + = 2u * prime用于2以外的所有素数。
\ $ \ endgroup \ $
–莫文
14年4月13日在16:13
评论
你定时了吗？如果由于内存争用，并行筛子速度更快，这会让我感到惊讶。从缓存的内存获得的内存比实际的内存提高的速度似乎更有可能提高您的速度（因为您无法对线程进行尽可能多的本地缓存，因为不同的线程可能位于不同的内核上，因此您需要不断地向后推跨缓存和内存转发）。@LokiAstari不，我没有计时。实际上，我根本不关心速度，我只想编写一个多线程程序并对其进行审查，这仅是为了学习。
我的计算机甚至都不是多核的。击败线程友好的缓存友好顺序方法可能会遇到麻烦。
+1;素数搜索中的并行性是一个非常有趣的高级概念，想知道是否在某处对此进行了更科学的分析……是否有人引用？无论如何，请注意，一般来说，素数检测的科学是非常先进的，并且是橡皮擦的理论和筛子，而作为编程练习，则被专家认为基本上是解决该问题的“玩具”算法...我的理解GNFS是领先/典型的算法，想知道是否有人将它并行化了吗？
@LokiAstari实际上，如果将素数预先计算为sqrt（maxp），则可以在处理器之间平均分配筛分空间，而不会发生争用。相同的技巧可以使顺序筛算法的缓存效率更高。