lua table 中的最大条目数

Question

我正在尝试在 Lua 中构建一个 Sieve of Eratosthenes，我尝试了几种方法，但我发现自己面临以下问题：对于这种情况，Lua 的 table 太小了。如果我只想创建一个包含所有数字的 table（请参见下面的示例），即使只有数字的 1/8 (...)，table 也太 "small"我承认这个数字很大）...

max = 600851475143
numbers = {}

for i=1, max do
    table.insert(numbers, i)
end

如果我在 Windows 机器上执行此脚本，会出现一条错误消息：C:\Program Files (x86)\Lua.1\lua.exe: not enough memory。在我的 Linux 机器上使用 Lua 5.3 运行我也试过了，错误只是 killed。所以很明显 lua 无法处理条目的数量。

我真的不知道是否不可能在 lua table 中存储那么多的条目，或者对此有一个简单的解决方案（尝试使用长字符串还有……）？ Lua table 中最大的条目数到底是多少？

更新： 是否可以手动为 table 分配更多内存？

更新2（第二题的解答）： 第二题很简单，我只是用运行测试了每个数字，直到程序中断：33.554.432 (2^25) 个条目适合我的 12 GB RAM 系统上的一个一维 table。为什么是 2^25？因为每个数字 64 位 * 2^25 = 2147483648 位正好是 2 GB。对于 Windows 32 位编译器，这似乎是 Lua 的标准内存分配大小。

P.S. You may have noticed that this number is from the Euler Project Problem 3. Yes I am trying to accomplish that. Please don´t give specific hints (..). Thank you :)

Answer 1

Lua 使用双精度浮点数来表示数字。这是每个数字 64 位。 600851475143 个数字产生了将近 4.5 TB 的内存。

所以这不是 Lua 或其表格的错。错误消息甚至说

not enough memory

您只是没有足够的 RAM 来分配那么多。

如果您仔细阅读了链接的维基百科文章，您会发现以下部分：

As Sorenson notes, the problem with the sieve of Eratosthenes is not the number of operations it performs but rather its memory requirements.[8] For large n, the range of primes may not fit in memory; worse, even for moderate n, its cache use is highly suboptimal. The algorithm walks through the entire array A, exhibiting almost no locality of reference.

A solution to these problems is offered by segmented sieves, where only portions of the range are sieved at a time.[9] These have been known since the 1970s, and work as follows ...

Answer 2

Eratosthenes 筛法每个数只需要一位，表示该数是否被标记为非素数。

减少内存使用的一种方法是使用按位数学来表示每个 table 条目中的多个位。当前 Lua 实现具有对按位或、- 等的内在支持。根据底层实现，您应该能够为每个 table 条目表示 32 或 64 位（数字标志）。

另一种选择是使用一个或多个非常长的字符串而不是 table。你只需要一个线性数组，这就是字符串。在每个位置都有一个带有 "t" 或 "f" 或“0”或“1”的长字符串。

警告：Lua 中的字符串操作总是涉及重复，这在性能方面会迅速变成 n² 或更糟的复杂性。您不希望整个大量序列有一个连续的字符串，但您可以将其分成一千个块或 2 的某次方块。这样可以将内存使用量减少到每个数字 1 个字节，同时最大限度地减少开销。

编辑： 在注意到其他地方提出的观点后，我意识到你的最大数字是如此之大，以至于即使每个数字有一位，你的内存需求也将是 73 GB，这是非常不切实际的。我建议遵循 Piglet 在他们的回答中给出的建议，看看 Jon Sorenson 的筛子版本，它适用于 space 的部分而不是整个东西。

我会保留我的建议，因为它可能对 Sorenson 筛法仍然有用，但是，是的，你的问题比你意识到的要大。

lua table 中的最大条目数

Largest amount of entries in lua table

lua

lua-table