Lua中对于一个大矩阵来说,1D数组和2D数组哪个更加高效?

Lua中,哪个计算成本更小:一个矩阵中,一个位于(row, column)的项目是 matrix [row] [column] 还是 matrix [row + numberOfRows * column]

假设这些项目将被频繁读写,并且假设矩阵很,约为1000 x 2000个项目。

我主要关心当前的效率,而不是开销。

点赞
用户107090
用户107090

如下所示,matrix[row][column] 使用的 VM 指令比 matrix[row + numberOfRows * column] 少一个。但是,目前不清楚 GETTABLE 是否比 MUL+ADD 更快。

唯一真正的答案是:测量两种方案。

$ cat 1
local matrix,row,numberOfRows,column
return matrix[row][column]

$ luac -l 1
main <1:0,0> (5 instructions at 0x7f9459c03d40)
0+ params, 5 slots, 1 upvalue, 4 locals, 0 constants, 0 functions
    1   [1] LOADNIL     0 3
    2   [2] GETTABLE    4 0 1
    3   [2] GETTABLE    4 4 3
    4   [2] RETURN      4 2
    5   [2] RETURN      0 1

$ cat 2
local matrix,row,numberOfRows,column
return matrix[row + numberOfRows * column]

$ luac -l 2
main <2:0,0> (6 instructions at 0x7ff339c03d40)
0+ params, 5 slots, 1 upvalue, 4 locals, 0 constants, 0 functions
    1   [1] LOADNIL     0 3
    2   [2] MUL         4 2 3
    3   [2] ADD         4 1 4
    4   [2] GETTABLE    4 0 4
    5   [2] RETURN      4 2
    6   [2] RETURN      0 1

然而,像这样的循环

for row=1,numberOfRows do
    for column=1,numberOfColumns do
        matrix[row][column]=f(row,column)
    end
end

可能比这个更慢

for row=1,numberOfRows do
    local r=matrix[row]
    for column=1,numberOfColumns do
        r[column]=f(row,column)
    end
end

同样,测量两种方案。

2018-09-04 15:50:58