时间戳

首页 > 解决方案 > 用于筛子的最佳数据结构是什么（即一些被划掉的数字列表）？

c++ - 用于筛子的最佳数据结构是什么（即一些被划掉的数字列表）？

问题描述

我正在实施埃拉托色尼筛。我被困在第一步：决定使用哪种数据结构。简而言之，埃拉托色尼筛法以一系列连续数字（例如 2、3、4、5、...99、100）开始。然后，某些数字被划掉，不再考虑。什么是最好的数据结构？限制（示例中为 100）直到运行时才知道，尽管 2 始终是起始数字。

我已经看到了一些不同的解决方案。限制n是类型mpz_class

其中一些信息来自此代码审查问题。@Jamal 声明“实际上存在与 std::vector 相关的问题”，但没有详细说明。我也在某处红色，unsigned char保证其大小等于或小于使其 bool成为更好的选择。

标签： c++data-structuresstdvectorsieve-of-eratosthenesstd-bitset

解决方案

tl;博士测量是唯一可以确定的方法，但这是我的想法：

一般来说

  1. bool primes[n]- 一个简单的布尔数组 - 问题是，它有一个固定的大小，所以如果n在编译时不知道它是不可用的。请注意，一些编译器将允许 VLA，但这不是标准，应该避免。
  2. bool* primes = new bool[n]- 也是一个简单的数组，只是动态分配。
  3. std::vector<bool> primes- 本质上是一个bool*. 可以实现为节省空间的位集。
  4. std::bitset<n> primes - 节省空间的存储空间，但遗憾的是尺寸固定。
  5. std::vector<int>或std::vector<usigned char>- 与 3) 相同，只是它没有作为 bitset 的优化实现。

如果它是n直到运行时才知道的要求，它归结为一些std::vector或动态分配的数组。如果n有一个合理的上限，仍然可以考虑静态数组。

位集与数组/向量

简而言之：位集针对空间进行了优化，基本上每个字节存储 8 个布尔值，但它们需要按位运算来提取信息，这需要一些数组/向量中不需要的 CPU 周期。另请参阅此问题

但是，我不确定位集的更高信息密度对缓存性能有多大的影响。

bool 向量与 unsigned char 向量

如果std::vector<bool>没有实现为节省空间的位集，它可能会比 a 占用更多的内存std::vector<unsigned char>，因为sizeof bool它可以大于 1 并因此大于sizeof (unsigned char). （另见这里）

如果有一个节省空间的实现std::vector<unsigned char>需要更多的内存，但可能更快。

矢量的表现

sdstd::vector::operator[]不执行绑定检查，因此与bool*. 此外，您还有一些实现在调试模式下（并且仅在调试模式下）进行边界检查的好处。std::vector绝对比数组更舒适。

结论

std::vector<unsigned char>如果有足够的可用内存，可能是最好的方法。但最终，通过优化对不同 的基准进行基准测试将是唯一可以确定的方法。n

推荐阅读