运行一个循环2900万次,在lua中更快地处理数据

好吧,我写了一个处理数据的程序,但我需要在字符串上运行此函数,有时数据长度超过2900万。如果我像这样运行一个循环:

for x = 1, 29000000, 1 do
end
print("完成")

它会立即完成,现在我并不是要求有人尝试使其立即完成,但是如何使其完成更快,因为它当前需要3小时以上才能完成10%,所以基本上是否有一种方法可以让lua使用更多CPU或使我的功能更高效?

local function interpret(action, input, key)
    local bytechar,decrypt,encrypt,inputoutputsub = string.bytestring.char,key.decrypt,key.encrypt,input''string.sub
    if (action == "解密") then
        for x = 1, (#input), 1 do
            output = (output .. (char(((byte(decrypt[sub(input, x, x)]) - (x + 2)) + 1) % 256)))
            if x % 10000 == 0 then print(x) end
        end
    else
        for x = 1, (#input), 1 do
            output = output .. (encrypt[char(((byte(sub(input, x, x)) + x) + 1) % 256)])
            if x % 10000 == 0 then print(x) end
        end
    end
    return (output);
end
点赞
用户90511
用户90511

当一个程序运行了几个小时,而且看起来不应该是这样的时候,很可能你正在使用一个具有糟糕的演算法渐近时间复杂度算法。运行一些实验,看看运行算法所需的时间如何随着输入字符串长度的变化而变化。

对于这个问题,我们理想情况下希望随着输入规模的增加,时间呈线性增长。将输入字符串大小翻倍应该导致计算时间翻倍。但是,根据评论所示,在您的情况下,我怀疑您的算法是二次的。将输入大小翻倍可能会导致计算时间增加四倍。将输入增大10倍可能会使计算时间增加100倍。

如果您的算法是二次的,则要使其在长输入的合理时间内运行的唯一方法是使用具有更好渐近复杂度的另一个算法来替换它。无论您如何微调程序或使用多么强大的计算机硬件,渐近复杂度都会追上您。例如,即使您微调算法使其运行速度快10000倍,它只能处理比以前大100倍的输入。


在您特定的程序中,问题的源头是使用“..”运算符逐个字符构建大字符串。在Lua中,这需要与你传递给“..”的字符串长度成正比的时间,因为“..”通过将其输入复制到全新的字符串中来工作。

最常见的解决方法是将字符串的各个部分存储在一个表中,并在结尾处使用table.concat将其连接起来。

local result = {}
for i = 1, (#input), 1 do
    result[i] = char(((byte(decrypt[sub(input, i, i)]) - (i + 2)) + 1) % 256)
end
return table.concat(result)
2016-08-09 20:17:15