使用数字索引遍历数组/table 的最快方法是什么？

Question

如果我在 lua 中有一个带有编号索引的数组，并且需要至少遍历每个条目一次，使用数字 for 循环还是通用 for 循环更快？

Answer 1

在这种情况下，使用数字 for 循环会更快。但差别不大，在我的测试中，它更容易在我的系统上出现负载差异。

数字循环

a = {} -- new array
for i = 1, 10000000 do
    a[i] = 10000000 + i
end

local startNumLoop = os.time(os.date("!*t"))

for i = 1, #a, 1 do
    local value = a[i]
end

local stopNumLoop = os.time(os.date("!*t"))

local numloop = stopNumLoop - startNumLoop 

print(os.clock())

结果：1.379 - 1.499

通用循环

a = {} -- new array
for i = 1, 10000000 do
    a[i] = 10000000 + i
end

local startGenLoop = os.time(os.date("!*t"))

for index, value in ipairs(a) do

end

local stopGenLoop = os.time(os.date("!*t"))

local genLoop = stopGenLoop- startGenLoop

print(os.clock())

结果：1.568 - 1.662

使用来自 lua.org

的 lua 5.3.6 win32 二进制文件进行测试

这只是我的一个问题，我没有足够快地找到答案。如果它实际上是重复的，请随意标记它。 :)

Answer 2

语义差异

for i = 1, #t do end

不等于

for i, v in ipairs(t) do end

后者不依赖于 #t 并尊重 __ipairs 元方法（尽管这已被弃用，应该使用 __index 和 __newindex 元方法代替）。

假设没有设置元方法，ipairs 将简单地循环直到它遇到一个 nil 值。因此它大致等同于以下循环：

local i, v = 1, t[v]
while v ~= nil do --[[loop body here]] i = i + 1; v = t[i] end

这意味着它不必做两件事：

不决定长度。如果设置，它不会调用 __len 元方法。这在理论上可能会导致位于散列部分的列表具有更好的性能（其中 Lua 必须通过搜索确定长度）。它还可以在 __len 元方法进行昂贵计数的情况下提高性能。
它不必遍历 nil 个值。另一方面，由于长度运算符的定义方式，数字 for 循环可能会遍历任意多个 nil 值：对于 table {[1] = 1, [1e9] = 1}，1 和 1e9 是长度的有效值。这也意味着不清楚它的作用，因为未指定确切的长度值。

后一点特别意味着在病态情况下，数字 for 循环可能任意慢。它还允许错误，例如循环（可能很长）字符串而不是 tables，并且不会触发错误：

local str = "hello world"
for i = 1, #str do local v = str[i] end

将仅遍历 nil 值（因为它索引字符串元 table）但不会抛出错误。

我还认为 ipairs 更具可读性，因为它使意图清晰。

性能差异

对于 non-pathological 情况（列表位于列表部分，没有“空洞”（零值），没有奇元 tables），数字 for 循环可以预期运行稍快一些，因为它不会产生您将与 ipairs 一起使用的通用循环的调用开销。这应该在不同的 Lua 实现上进行基准测试：

PUC Lua 5.1 到 5.4
LuaJIT 2.1.0

实际上，与在循环体内执行的操作的成本相比，循环的成本通常可以忽略不计。结果可能因操作系统或硬件等其他因素而异。

基本基准

print(jit and jit.version or _VERSION)

-- Fill list with 100 million consecutive integer values
a = {}
for i = 1, 1e8 do a[i] = i end

local function bench(name, func)
    func() -- "warmup"
    local t = os.clock()
    for _ = 1, 10 do func() end
    print(name, os.clock() - t, "s")
end

bench("numeric", function()
    for i = 1, #a do
        local v = a[i]
    end
end)

bench("ipairs", function()
    for i, v in ipairs(a) do end
end)

在 Linux 机器上进行。

Lua 5.1
numeric 54.312082   s
ipairs  63.579478   s
Lua 5.2
numeric 20.482682   s
ipairs  32.757554   s
Lua 5.3
numeric 14.81573    s
ipairs  23.121844   s
Lua 5.4
numeric 11.684143   s
ipairs  24.455616   s

最后，LuaJIT：

LuaJIT 2.1.0-beta3
numeric 0.567874    s
ipairs  0.70047 s

结论：尽可能使用 LuaJIT，不再担心 micro-optimizations，例如 ipairs 与数字 （即使后者可能稍快）。像 assert(i == v) 这样简单的东西已经和循环本身一样昂贵了（即使 assert 是 local）。

Answer 3

特别是对于需要 remove/change 当前 key/value 对的循环，我更喜欢快速倒计时方法...

for i = #tab, 1, -1 do
 if (tab[i].x > x) then
  table.remove(tab, i) -- See comments
 end
end

...例如在 LÖVE [love2d] 中两帧之间。

使用数字索引遍历数组/table 的最快方法是什么？

What is the fastest way to go through an array / table with numeric indices?

lua

语义差异

性能差异

基本基准