素数低于20亿 - 使用std :: list会影响性能

作者: 石茶
发布时间: 2024-07-10 11:35:25 (6天前)
转自：

3 条回复

0#
回复此人
日耀九洲 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 首先要做的是确保您在启用优化的情况下进行编译。 c ++标准库模板类在未经优化的代码中往往表现很差，因为它们会生成大量函数调用。优化器内联大多数函数调用，这使得它们更便宜。 <code> std::list </code> 是一个链表。在您想要随机插入或删除元素（即不是从末尾）的情况下，它非常有用。 对于仅附加到列表末尾的情况 <code> std::list </code> 有以下问题： <UL> <LI> 迭代列表是相对昂贵的，因为代码必须遵循节点指针然后检索数据 </LI> <LI> 该列表使用了相当多的内存，除了实际数据之外，每个元素都需要指向前一个和下一个节点的指针。在64位系统上，这相当于每个元素20个字节，而不是4个列表 <code> int </code> </LI> <LI> 由于列表中的元素在内存中不连续，因此编译器无法执行尽可能多的SIMD优化，并且您将因CPU缓存未命中而遭受更多损失 </LI> </UL> 一个 <code> std::vector </code> 将解决上述所有问题，因为它的内存是连续的，并且迭代它基本上只是递增数组索引的情况。你需要确保你打电话 <code> reserve </code> 在你的矢量开头有一个足够大的值，以便附加到向量不会导致整个数组被复制到一个新的更大的数组。 比上面更大的优化是使用 <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer"> Eratosthenes的筛子 </A> 计算你的素数。生成此灯需要随机删除（取决于您的确切实现） <code> std::list </code> 可能表现得比 <code> std::vector </code> 虽然在这种情况下即使是开销 <code> std::list </code> 可能不会超过其成本。 </DIV>

编辑
1#
回复此人
撩心 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <H2> <a href="https://ideone.com/VPOnux" rel="nofollow noreferrer"> 在Ideone进行测试 </A> （完全没有表面改动的OP代码）的 相矛盾 </强> 在这个问题中提出的主张： </H2> <pre> <code> /* check_prime__list: time taken No of divisions No of primes 10M: 0.873 seconds 286144936 664579 20M: 2.169 seconds 721544444 1270607 */ 2B: projected time: at least 16 minutes but likely much more (*) /* check_prime__nums: time taken No of divisions No of primes 10M: 4.650 seconds 1746210131 664579 20M: 12.585 seconds 4677014576 1270607 */ 2B: projected time: at least 3 hours but likely much more (*) </code> </pre> 我还改变了与之对应的分割数量的类型 <code> long int </code> 因为它围绕数据类型限制。所以他们 可以 一直在曲解 那 。 但的 运行时间 </强> 没有受到影响。挂钟是挂钟。 最可能的解释似乎是OP的一个草率测试，错误地在每个测试用例中使用了不同的值。 <HR /> （*）时间投影是由 <a href="http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth" rel="nofollow noreferrer"> 经验增长的顺序 </A> 分析： <pre> <code> 100**1.32 * 2.169 / 60 = 15.8 100**1.45 * 12.585 / 3600 = 2.8 </code> </pre> 对于列表算法，在给定的大小范围内测量的经验增长顺序明显更好， ñ 1.32 的与...相对 ñ 1.45 的所有数字的测试。这完全是从理论上的复杂性来预期的，因为素数比所有数字都要少 ñ ，因数 登录 ，总的复杂性 上 1.5 / log n） 的与 上 1.5 ） 的。任何实现差异也不太可能超过实际的算法优势。 </DIV>

编辑

登录后才能参与评论