我正在寻找使用分段筛并使用 CPU 的 L1 高速缓存的 Eratosthenes 筛的 python 实现。
我在 github 上有我自己的版本:https://github.com/nick599/PythonMathsAlgorithms/blob/master/segmented_soe_v6.py ，它不使用 CPU 的 L1 缓存大小。
我找到了以下网站 - http://primesieve.org/segmented_sieve.html ，它给出了使用 L1 缓存大小的 C++ 实现。它说它比我的算法快得多(我的算法需要几分钟来创建高达 10^7 的素数，并且由于内存使用而卡在 10^8)。
我正在 Linux Mint v17 上开发，python 版本:2.74。 更新我的 CPU 是 Intel i7。
我是 python 的新手。
我想知道:
- 我如何开始实现此 C++ 算法的 Python 版本？
- 我需要考虑什么？
- C++ 实现中是否有无法在 Python 2.74 中编码的内容？
- 多线程呢？
- 超线程呢？
- python 的 GIL 怎么样？
寻找能够回答我上述所有问题精神的答案。欢迎提供提示和技巧。
最佳答案
我不确定您是否可以对 Python 如何使用内存做出足够的假设以确保它有效地使用 L1 缓存。 此外，10^8 仅为 1/2 Gig，因此您当前的实现在元素分配方面肯定效率很低。 如果您只打算在每个位置存储一个标志，那么您最好创建尽可能大的字符串并将其索引为您的筛选存储，而不是使用整数数组？ 使用字符串作为分段筛选存储当然是可能的，如果幸运的话，它们可能足够小，可以存放在 L1 缓存中。 C 有一些很好的位索引和操作，我确信在 python 中可以使用它们来允许你独立地操作每一位。您可以对字符值进行位操作。
关于使用L1 CPU Cache的c++算法的Python实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47042499/