代码之家 › 专栏 › 技术社区 › creyD Ratha Pech

lua表中最大的条目数

lua-table lua

creyD Ratha Pech · 技术社区 · 7 年前

我想建立一个 Sieve of Eratosthenes 在Lua,我尝试了几件事,但我发现自己面临以下问题: 对于这种情况,Lua的表太小了。如果我只想创建一个包含所有数字的表(参见下面的示例),那么即使只有1/8(…),该表也太“小”这个数字(我承认这个数字相当大)。。。

max = 600851475143
numbers = {}

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

如果我在Windows计算机上执行此脚本,则会显示一条错误消息: C:\Program Files (x86)\Lua\5.1\lua.exe: not enough memory . 当Lua5.3在我的Linux机器上运行时,我也试过了,错误只是 killed . 所以很明显,lua无法处理条目的数量。

我真的不知道是不可能在lua表中存储那么多的条目,还是有一个简单的解决方案(也可以使用长字符串进行尝试…)?Lua表中最大的条目数是多少?

更新: 是否可以手动为表分配更多内存?

更新2(第二个问题的解决方案): 第二个问题很简单,我只是通过运行每个数字直到程序中断来测试它: 33.554.432 (2^25)条目适合我的12 GB RAM系统上的一个一维表格。为什么是2^25?因为每个数字64位*2^25=2147483648位,正好是2 GB。这似乎是Lua for Windows 32位编译器的标准内存分配大小。

P、您可能已经注意到,这个数字来自Euler项目问题3。是的,我正在努力做到这一点。请不要给出具体提示(…)。谢谢:)

2 回复 | 直到 7 年前

creyD Ratha Pech 7 年前

Eratosthenes筛每个数字只需要一个比特,表示该数字是否被标记为非素数。

减少内存使用的一种方法是使用逐位数学表示每个表项中的多个位。当前的Lua实现内在地支持按位或,-等。根据底层实现,您应该能够表示每个表条目的32位或64位(数字标志)。

另一种选择是使用一个或多个很长的字符串,而不是表。您只需要一个线性数组,它实际上就是字符串。只要在每个位置都有一个带有“t”或“f”或“0”或“1”的长字符串。

警告:Lua中的字符串操作总是涉及到重复,这很快就会变成n或更糟的性能复杂性。你不希望整个大规模序列都有一个连续的字符串,但你可能会把它分解成1000个块,或者2的幂。这样可以将内存使用量减少到每个数字1字节,同时将开销降至最低。

在注意到其他地方提出的一点后,我意识到您的最大数字太大了,即使每个数字有一个位,您的内存需求也会达到 73 GB ,这是非常不切实际的。我建议按照小猪在回答中给出的建议,看看乔恩·索伦森(JonSorenson)的筛子版本,它适用于空间的各个部分,而不是整个东西。

我会留下我的建议,因为它可能对索伦森的筛子仍然有用,但是的,你有一个比你意识到的更大的问题。

Piglet 7 年前

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

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

内存不足

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

如果你仔细阅读维基百科的链接文章,你会发现以下部分:

正如索伦森所指出的 Eratosthenes筛的问题是 不它执行的操作数 记忆力 要求 .[8] 对于大n,素数的范围可能不适合 记忆力 ; 更糟糕的是,即使对于中等规模的n,其缓存使用率也很高次优。该算法遍历整个阵列A,显示几乎没有参考位置。

哪里一次只筛选部分范围。[9] 这些都是自20世纪70年代以来就已为人所知,其工作如下 ...