c - 有效地存储列表列表(筛选)

Question

问题

我正在为 C 语言的项目寻找一种数据结构来存储列表列表。我需要能够访问仅给定 n 的第 n 个列表(这些术语将被乱序访问)。各个列表将包含 1 到 M 之间的整数(为了具体起见，假设 M = 25)；外部列表包含其中的 N 个。平均而言，单个列表比 M 更接近 1:在我的示例中，只有 20% 的元素在 5 到 25 之间。

显而易见的实现是一个长度为 N*M 的数组。但这是空间效率低下的:出于性能原因，该结构不要占用太多内存很重要。执行此操作的好方法是什么？

上下文

我正在写一个因式分解筛。外层数组表示从 Sb + 1 到 S(b+1) 的数，每个数组存储该范围内一个数的质因数。结构越小，可以选择的 S 越大，从而减少(昂贵的)划分的数量。

这也提供了另一个优化途径:只存储大于或等于 L 的素数。好处是每个列表中不需要 floor(log_2(x = largest number in range)) 元素，你只需要 floor( log_L(x))。 (上面的示例对应于 x = 10^12，L = 3。)缺点是要重构因式分解，需要对 L 以下的素数进行试除。

在我的应用程序中，每个因式分解都被重构一次，因此在我的示例中，将 L 增加到下一个主要成本(略多于)10^12 个额外的除法；作为一个数量级，这是每次 24-87 次操作或在 3 GHz K10 上总共 2-8 小时。内存结构越高效，我需要花费的 2 到 8 小时的时间就越少。 (另一方面，占用过多 CPU 工作的内存结构不值得，除非它们提供更好的权衡。)

Answer 1

我想到的一种数据结构是二维数组，其中“内部”数组比 floor(log_L(x)) 小很多。如果剩下质因数，则在最后一个元素中存储一个指针，该指针将指向二级溢出数组。您还可以通过省略最后一个素数来减少所需的存储空间，这可以通过除以其他素数来确定。

我不知道这是否比天真的方法好得多。好处是内存使用量要小得多——可能是 5 个元素而不是 25 个，让您可以在同一空间中装入 4 到 5 倍的数字。缺点是重建数字需要更多工作，内存局部性可能会稍微差一些。

但是还有另一个技巧可能会有所帮助。只要 L > 2，列表中的所有数字都是奇数，因此最后一位未使用。您可以使用它来将指数存储在数字本身中:存储 p * 2^(e-1) 而不是 p。所以“3”代表3，“6”代表3^2，“12”代表3^3，以此类推。如果你使用 64 位数字，你可以将 3^63 表示为 3*2^62，它小于 2^64。 (更大的基数更容易:5^62 是 3^63 的 18 万亿倍，但可以用 64 位以这种格式表示。)32 位将您限制为 3^31，但您已经不能表示素数 2^ 32 + 15，这使得极限略大于 2^64。

实际上，我认为这已经足够了，可以完全跳过辅助阵列。这是一个列表，显示您需要存储多少因素

使用 1 uint32_t 可以存储小于 3*5*7 = 105(7 位)的因式分解数。

使用 2 个 uint32_t 可以存储小于 3*5*7*11 = 1155(11 位)的因数。

使用 3 个 uint32_t 可以存储小于 3*5*7*11*13 = 15015(14 位)的因数。

使用 4 个 uint32_t 可以存储小于 3*...*17 = 255255(18 位)的因数。

使用 5 个 uint32_t 可以存储小于 3*...*19(23 位)的因数。

使用 6 个 uint32_t 可以存储小于 3*...*23(27 位)的因数。

使用 7 个 uint32_t 可以存储小于 3*...*29(32 位)的因数。

使用 8 个 uint32_t 可以存储小于 3*...*31(37 位)的因式分解数。

使用 9 个 uint32_t 可以存储小于 3*...*37(42 位)的因数。

使用 10 个 uint32_t 可以存储小于 3*...*41(48 位)的因数。

使用 11 个 uint32_t 可以存储小于 3*...*43(53 位)的因数。

使用 12 个 uint32_t 可以存储小于 3*...*47(59 位)的因数。

使用 13 个 uint32_t 可以存储小于 3*...*53(64 位)的因数。

使用 14 个 uint32_t 可以存储小于 (2^32 + 15)^2(64 位)的因式分解数。

要超越这个，您可能想要使用我提到的备用数据结构(其中辅助数组使用 uint64_t)，因此您不需要将主数组转换为 uint64_t。但这仅与分段筛分有关；筛除 2^64 以内的所有数字是不可行的——这需要数百年时间。