Lua 中的递归合并排序显示错误行为；虽然几乎相同的 python 代码运行良好

Question

对不起，如果我的英语不好，我的母语是韩语。

我尝试使用下面的伪代码 Lua 实现递归归并排序：

void merge(int h, int m, const keytype U[], const keytype V[], keytype S[]) {
    index i, j, k;
    i = 1; j = 1; k = 1;
    while (i <= h && j <= m) {
        if (U[i] < V[j]) {
            S[k] = U[i];
            i++;
        } else {
            S[k] = V[j];
            j++;
        }
        k++;
    }
    if (i > h) {
        copy V[j] through V[m] to S[k] through S[h+m];
    } else {
        copy U[i] through U[h] to S[k] through S[h+m];
    }
}
void mergesort(int n, keytype S[]) {
  if (n > 1) {
    const int h = ⌊n/2⌋, m= n - h;
    keytype U[1..h], v[1..m];
    copy S[1] through S[h] to U[1] through U[h];
    copy S[h+1] through S[n] to V[1] through V[m];
    mergesort(h,U);
    mergesort(m,V);
    merge(h,m,U,V,S);
  }
}

我写了 Lua:

function merge(h, m, U, V, S)
    print(S[1], S[h+m])
    i, j, k = 1, 1, 1
    while i<=h and j<=m do
        if U[i] < V[j] then
            S[k] = U[i]
            i = i+1
        else
            S[k] = V[j]
            j = j+1
        end
        k = k+1
    end
    if i>h then
        while j<=m do
            S[k] = V[j]
            j, k = j+1, k+1
        end
    else
        while i<=h do
            S[k] = U[i]
            i, k = i+1, k+1
        end
    end
end

function mergeSort(n, S)
    if n>1 then
        h = math.floor(n/2)
        m = n - h
        local U = {}
        local V = {}
        i = 1
        while i<=h do
            U[i] = S[i]
            i = i + 1
        end
        while i<=n do
            V[i-h] = S[i]
            i = i + 1
        end
        print(h, m)
        mergeSort(h, U)
        mergeSort(m, V)
        merge(h, m, U, V, S)
    end
end

s = {52, 33, 14, 27, 8, 31, 24, 11, 5, 36, 44, 47, 20}
mergeSort(#s, s)
for k, v in ipairs(s) do
    print(v)
end

但结果是 14, 33, 14, 27, 8, 31, 24, 11, 5, 36, 44, 47, 20，未排序且元素重复。但是，我尝试将此 Lua 代码转换为 python 代码：

import math

def merge(h, m, U, V, S):
    print(S[1], S[h+m])
    i, j, k = 1, 1, 1
    while i<=h and j<=m:
        if U[i] < V[j]:
            S[k] = U[i]
            i = i+1
        else:
            S[k] = V[j]
            j = j+1
        k = k+1
    
    if i>h:
        while j<=m:
            S[k] = V[j]
            j, k = j+1, k+1
    else:
        while i<=h:
            S[k] = U[i]
            i, k = i+1, k+1

    
def mergeSort(n, S):
    if n>1:
        h = math.floor(n/2)
        m = n - h
        U = {}
        V = {}
        i = 1
        while i<=h:
            U[i] = S[i]
            i = i + 1
        while i<=n:
            V[i-h] = S[i]
            i = i + 1
        print(h, m)
        mergeSort(h, U)
        mergeSort(m, V)
        merge(h, m, U, V, S)

a = [52, 33, 14, 27, 8, 31, 24, 11, 5, 36, 44, 47, 20]
s = dict(enumerate(a, 1))
mergeSort(len(s), s)
print([s[i] for i in range(1, len(s)+1)])

我认为这与 pythonic 代码相去甚远，但无论如何，这段代码毕竟对序列进行了很好的排序，结果是 [5, 8, 11, 14, 20, 24, 27, 31, 33, 36, 44, 47, 52]。所以我发现这个错误与 Lua table 有关，但是通过 print() 调试给出的信息很少，我找不到任何与此相关的 lua 参考。我的 lua 代码会有什么问题？另外，如何让我的 python 代码更 pythonic?

Answer 1

问题源于您使用全局变量而不是局部变量。函数调用将以这种方式改变调用“父”函数的值。如果将函数内声明的所有全局变量本地化，它既可以修复错误又可以提高性能。考虑使用 linter 来发现此类全局变量错误。

固定代码：

function merge(h, m, U, V, S)
    print(S[1], S[h+m])
    local i, j, k = 1, 1, 1
    while i<=h and j<=m do
        if U[i] < V[j] then
            S[k] = U[i]
            i = i+1
        else
            S[k] = V[j]
            j = j+1
        end
        k = k+1
    end
    if i>h then
        while j<=m do
            S[k] = V[j]
            j, k = j+1, k+1
        end
    else
        while i<=h do
            S[k] = U[i]
            i, k = i+1, k+1
        end
    end
end

function mergeSort(n, S)
    if n>1 then
        local h = math.floor(n/2)
        local m = n - h
        local U = {}
        local V = {}
        local i = 1
        while i<=h do
            U[i] = S[i]
            i = i + 1
        end
        while i<=n do
            V[i-h] = S[i]
            i = i + 1
        end
        print(h, m)
        mergeSort(h, U)
        mergeSort(m, V)
        merge(h, m, U, V, S)
    end
end

local s = {52, 33, 14, 27, 8, 31, 24, 11, 5, 36, 44, 47, 20}
mergeSort(#s, s)
for k, v in ipairs(s) do
    print(v)
end

Lua 中的递归合并排序显示错误行为；虽然几乎相同的 python 代码运行良好

recursive merge sort in Lua showing wrong behavior; while almost same python code works well

python

recursion

lua

mergesort

lua-table