lua - 在迭代时安全地从数组表中删除项目

Question

这个问题类似于如何在删除键时安全地迭代 lua 表，但明显不同。

概括

给定一个 Lua 数组（键是从 开始的顺序整数的表1），遍历这个数组并删除一些条目的最佳方法是什么？

现实世界的例子

我在 Lua 数组表中有一组带时间戳的条目。条目总是添加到数组的末尾（使用table.insert）。

local timestampedEvents = {}
function addEvent( data )
  table.insert( timestampedEvents, {getCurrentTime(),data} )
end

我需要偶尔浏览这个表（按顺序）并处理和删除某些条目：

function processEventsBefore( timestamp )
  for i,stamp in ipairs( timestampedEvents ) do
    if stamp[1] <= timestamp then
      processEventData( stamp[2] )
      table.remove( timestampedEvents, i )
    end
  end
end

不幸的是，上述方法的代码中断了迭代，跳过了一些条目。有没有比手动遍历索引更好（打字更少，但仍然安全）的方法：

function processEventsBefore( timestamp )
  local i = 1
  while i <= #timestampedEvents do -- warning: do not cache the table length
    local stamp = timestampedEvents[i]
    if stamp[1] <= timestamp then
      processEventData( stamp[2] )
      table.remove( timestampedEvents, i )
    else
      i = i + 1
    end
  end
end

Answer 1

遍历数组并在继续迭代的同时从中间删除随机项的一般情况

如果您从前到后迭代，当您删除元素 N 时，迭代中的下一个元素 (N+1) 将向下移动到该位置。如果您增加迭代变量（如 ipairs 所做的那样），您将跳过该元素。我们有两种方法可以解决这个问题。

使用此示例数据：

    input = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p' }
    remove = { f=true, g=true, j=true, n=true, o=true, p=true }

我们可以input通过以下方式在迭代期间删除元素：

1. 从后往前迭代。

   for i=#input,1,-1 do
       if remove[input[i]] then
           table.remove(input, i)
       end
   end
   

2. 手动控制循环变量，因此我们可以在删除元素时跳过递增它：

   local i=1
   while i <= #input do
       if remove[input[i]] then
           table.remove(input, i)
       else
           i = i + 1
       end
   end
   

对于非数组表，您使用nextor pairs（根据 实现next）进行迭代，并将要删除的项目设置为nil。

请注意，table.remove每次调用时都会移动所有后续元素，因此 N 删除的性能是指数级的。如果您要删除很多元素，您应该像 LHF 或 Mitch 的回答那样自己移动这些项目。

Answer 2

效率！

警告：不要使用 table.remove()。每次调用该函数以删除数组条目时，该函数都会重新索引所有后续（后续）数组索引。因此，在单次直通 OURSELVES 中“压缩/重新索引”表要快得多！

最好的技术很简单：向上计数 ( i) 通过所有数组条目，同时跟踪我们应该将下一个“保留”值放入 ( j) 的位置。任何未保留的（或从ito移动的j）都设置为nil告诉 Lua 我们已经删除了该值。

我正在分享这个，因为我真的不喜欢这个页面上的其他答案（截至 2018 年 10 月）。它们要么是错误的，要么是错误的，要么是过于简单的，要么是过于复杂的，而且大多数都是超慢的。所以我实现了一种高效、干净、超快速的一次性算法。使用单循环。

这是一个完整注释的示例（本文末尾有一个较短的非教程版本）：

function ArrayShow(t)
    for i=1,#t do
        print('total:'..#t, 'i:'..i, 'v:'..t[i]);
    end
end

function ArrayRemove(t, fnKeep)
    print('before:');
    ArrayShow(t);
    print('---');
    local j, n = 1, #t;
    for i=1,n do
        print('i:'..i, 'j:'..j);
        if (fnKeep(t, i, j)) then
            if (i ~= j) then
                print('keeping:'..i, 'moving to:'..j);
                -- Keep i's value, move it to j's pos.
                t[j] = t[i];
                t[i] = nil;
            else
                -- Keep i's value, already at j's pos.
                print('keeping:'..i, 'already at:'..j);
            end
            j = j + 1;
        else
            t[i] = nil;
        end
    end
    print('---');
    print('after:');
    ArrayShow(t);
    return t;
end

local t = {
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'
};

ArrayRemove(t, function(t, i, j)
    -- Return true to keep the value, or false to discard it.
    local v = t[i];
    return (v == 'a' or v == 'b' or v == 'f' or v == 'h');
end);

输出，沿途显示它的逻辑，它是如何移动事物的，等等......

before:
total:9 i:1 v:a
total:9 i:2 v:b
total:9 i:3 v:c
total:9 i:4 v:d
total:9 i:5 v:e
total:9 i:6 v:f
total:9 i:7 v:g
total:9 i:8 v:h
total:9 i:9 v:i
---
i:1 j:1
keeping:1   already at:1
i:2 j:2
keeping:2   already at:2
i:3 j:3
i:4 j:3
i:5 j:3
i:6 j:3
keeping:6   moving to:3
i:7 j:4
i:8 j:4
keeping:8   moving to:4
i:9 j:5
---
after:
total:4 i:1 v:a
total:4 i:2 v:b
total:4 i:3 v:f
total:4 i:4 v:h

最后，这是在您自己的代码中使用的函数，没有所有的教程打印......并且只有一些最小的注释来解释最终算法：

function ArrayRemove(t, fnKeep)
    local j, n = 1, #t;

    for i=1,n do
        if (fnKeep(t, i, j)) then
            -- Move i's kept value to j's position, if it's not already there.
            if (i ~= j) then
                t[j] = t[i];
                t[i] = nil;
            end
            j = j + 1; -- Increment position of where we'll place the next kept value.
        else
            t[i] = nil;
        end
    end

    return t;
end

就是这样！

如果您不想使用整个“可重用回调/函数”设计，您可以简单地将内部代码复制ArrayRemove()到您的项目中，并将行更改if (fnKeep(t, i, j)) then为if (t[i] == 'deleteme') then... 这样您就可以摆脱函数调用/callback 开销也更大，而且速度更快！

就个人而言，我使用可重复使用的回调系统，因为它的速度仍然大大table.remove()提高了 100-1000 倍以上。

奖励（高级用户）：普通用户可以跳过阅读此奖励部分。它描述了如何同步多个相关表。请注意， 的第三个参数fnKeep(t, i, j),j是一个奖励参数，它允许您的保持函数知道在fnKeep回答时将值存储在哪个索引处true（以保持该值）。

用法示例：假设您有两个“链接”表，其中一个是table['Mitch'] = 1; table['Rick'] = 2;（通过命名字符串快速查找数组索引的哈希表），另一个是 array[{Mitch Data...}, {Rick Data...}]（具有数字索引的数组，其中 Mitch 的数据位于 pos1和 Rick 的数据是在 pos 2，完全按照哈希表中的描述）。现在您决定遍历arrayand remove Mitch Data，从而Rick Data从一个位置移动到另一个2位置1......

然后，您的fnKeep(t, i, j)函数可以轻松地使用该j信息来更新哈希表指针，以确保它们始终指向正确的数组偏移量：

local hData = {['Mitch'] = 1, ['Rick'] = 2};
local aData = {
    {['name'] = 'Mitch', ['age'] = 33}, -- [1]
    {['name'] = 'Rick', ['age'] = 45}, -- [2]
};

ArrayRemove(aData, function(t, i, j)
    local v = t[i];
    if (v['name'] == 'Rick') then -- Keep "Rick".
        if (i ~= j) then -- i and j differing means its data offset will be moved if kept.
            hData[v['name']] = j; -- Point Rick's hash table entry at its new array location.
        end
        return true; -- Keep.
    else
        hData[v['name']] = nil; -- Delete this name from the lookup hash-table.
        return false; -- Remove from array.
    end
end);

从而从查找哈希表和数组中删除“Mitch”，并将“Rick”哈希表条目移动到其数组数据被移动到的位置1（即 的值）（因为 i 和 j 不同，表示正在移动数据）。j

这种算法允许您的相关表保持完美同步，由于j 参数，始终指向正确的数据位置。

对于需要该功能的人来说，这只是一个高级奖励。大多数人可以简单地忽略函数j中的参数 fnKeep()！

嗯，就是这样，伙计们！

享受！:-)

基准（又名“让我们开怀大笑……”）

我决定将此算法与table.remove()99.9% 的 Lua 用户正在使用的标准“向后循环并使用”方法进行基准测试。

为了做这个测试，我使用了下面的 test.lua 文件：https ://pastebin.com/aCAdNXVh

每个被测试的算法都有 10 个测试数组，每个数组包含 200 万个项目（每个算法测试总共 2000 万个项目）。所有数组中的项目都是相同的（以确保测试的完全公平性）：每第 5 个项目是数字“13”（将被删除），所有其他项目都是数字“100”（将保留）。

嗯...我ArrayRemove()的算法测试在 2.8 秒内结束（处理 2000 万个项目）。我现在正在等待table.remove()测试完成......到目前为止已经过了几分钟，我越来越无聊............更新：还在等待......更新：我饿了......更新：你好……今天？！更新：Zzz...更新：还在等待...更新：............更新：好的，table.remove()代码（这是大多数 Lua 用户正在使用的方法）将采取几天。我会在它完成的那一天更新。

自我注意：我于 2018 年 11 月 1 日 ~04:55 GMT 开始运行测试。我的ArrayRemove()算法在 2.8 秒内完成......内置的 Luatable.remove()算法目前仍在运行......我会更新这个稍后发布... ;-)

更新：现在是 2018 年 11 月 1 日格林威治标准时间 14:55，table.remove()算法仍未完成。我将中止那部分测试，因为 Lua 在过去10 小时内一直在使用我 100% 的 CPU ，我现在需要我的电脑。它的热度足以在笔记本电脑的铝制外壳上煮咖啡......

结果如下：

• 处理 10 个包含 200 万个项目的数组（总共 2000 万个项目）：
• 我的ArrayRemove()功能：2.8秒。
• 普通 Lua table.remove()：我决定在Lua 使用 100% CPU 10 小时后退出测试。因为我现在需要使用我的笔记本电脑！;-)

这是我按下 Ctrl-C 时的堆栈跟踪......它确认了我的 CPU 在过去 10 小时内一直在处理什么 Lua 函数，哈哈：

[     mitch] elapsed time: 2.802

^Clua: test.lua:4: interrupted!
stack traceback:
    [C]: in function 'table.remove'
    test.lua:4: in function 'test_tableremove'
    test.lua:43: in function 'time_func'
    test.lua:50: in main chunk
    [C]: in ?

如果我让table.remove()测试运行完成，可能需要几天时间......欢迎任何不介意浪费大量电力的人重新运行此测试（文件在 pastebin 上面），让我们大家知道花了多长时间。

为什么table.remove()这么慢？仅仅是因为对该函数的每次调用都必须重复地重新索引 我们告诉它删除之后存在的每个表项！因此，要删除 200 万项数组中的第一项，它必须将所有其他 200 万项的索引向下移动 1 个插槽以填补删除造成的空白。然后......当你删除另一个项目时......它必须再次移动所有其他 200 万个项目......它一遍又一遍地这样做......

你不应该，永远使用table.remove()！它的性能损失迅速增长。这是一个具有较小数组大小的示例，以证明这一点：

• 10 个包含 1,000 个项目的数组（总共 10k 个项目）ArrayRemove()：：0.001 秒，table.remove()：0.018 秒（慢 18 倍）。
• 10 个包含 10,000 个项目的数组（总共 100k 个项目）ArrayRemove()：：0.014 秒，table.remove()：1.573 秒（慢 112.4 倍）。
• 10 个 100,000 项的数组（总共 1m 项）ArrayRemove()：：0.142 秒，table.remove()：3 分 48 秒（慢 1605.6 倍）。
• 10 个包含 2,000,000 项的数组（总共 20m 项）ArrayRemove()：：2.802 秒，table.remove()：我决定在 10 小时后中止测试，所以我们现在可能永远不会花多长时间。;-) 但是在当前时间点（甚至还没有完成），它花费的时间比ArrayRemove()……长 12847.9 倍，但table.remove()如果我让它完成，最终结果可能会慢 30-40000 倍左右。

如您所见，table.remove()的时间增长不是线性的（因为如果是这样，那么我们的 100 万项测试将只花费 10 万（100k）项测试的 10 倍，但我们看到的是 1.573 秒与 3 分 48 秒！ ）。所以我们不能进行较低的测试（例如 10k 个项目）并简单地将其乘以1000 万个项目来知道我中止的测试需要多长时间......所以如果有人真的对最终结果感到好奇，你会必须自己运行测试并在几天后发表评论table.remove()......

但是在这一点上，我们可以做的是，根据我们目前的基准，说这些话：F-ck table.remove()！;-)

没有理由调用该函数。曾经。因为如果要从表中删除项目，只需使用t['something'] = nil;. 如果要从数组（具有数字索引的表）中删除项目，请使用ArrayRemove().

顺便说一句，上面的测试都是使用 执行Lua 5.3.4的，因为这是大多数人使用的标准运行时。我决定使用LuaJIT 2.0.5( JIT: ON CMOV SSE2 SSE3 SSE4.1 fold cse dce fwd dse narrow loop abc sink fuse) 快速运行主要的“2000 万项”测试，它比标准 Lua 运行时更快。2000 万个项目的结果ArrayRemove()是：Lua 为 2.802 秒，LuaJIT 为 0.092 秒。这意味着如果您的代码/项目在 LuaJIT 上运行，您可以期待我的算法获得更快的性能！:-)

我还使用 LuaJIT 最后一次重新运行了“100k 项”测试，以便我们可以看到table.remove()在 LuaJIT 中的执行情况，并查看它是否比常规 Lua 更好：

• [LUAJIT] 100,000 项的 10 个数组（总共 1m 项）ArrayRemove()：：0.005 秒，table.remove()：20.783 秒（比 ... 慢 4156.6 倍，但这个LuaJITArrayRemove()结果实际上比普通 Lua 更糟糕，后者“仅”慢 1605.6 倍比我的算法做同样的测试...所以如果你使用的是 LuaJIT，性能比更支持我的算法！）table.remove()

最后，您可能想知道“table.remove()如果我们只想删除一个项目会更快吗，因为它是一个原生函数？”。如果您使用 LuaJIT，该问题的答案是：不。在 LuaJIT 中，甚至ArrayRemove()比table.remove()删除 ONE ITEM 还要快。谁不使用 LuaJIT？使用 LuaJIT，与常规 Lua 相比，所有 Lua 代码的速度都轻松提高了 30 倍左右。结果如下：[mitch] elapsed time (deleting 1 items): 0.008, [table.remove] elapsed time (deleting 1 items): 0.011。这是“仅删除 1-6 项”测试的 pastebin：https ://pastebin.com/wfM7cXtU （文件末尾列出了完整的测试结果）。

TL;DR：无论出于何种原因，请勿table.remove() 在任何地方使用！

希望你们喜欢ArrayRemove()......并且玩得开心，大家！:-)

Answer 3

table.remove一旦设置了不需要的条目，我会避免并遍历数组，nil然后在必要时再次遍历数组以压缩它。

这是我想到的代码，使用 Mud 回答中的示例：

local input = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p' }
local remove = { f=true, g=true, j=true, n=true, o=true, p=true }

local n=#input

for i=1,n do
        if remove[input[i]] then
                input[i]=nil
        end
end

local j=0
for i=1,n do
        if input[i]~=nil then
                j=j+1
                input[j]=input[i]
        end
end
for i=j+1,n do
        input[i]=nil
end

Answer 4

试试这个功能：

function ripairs(t)
    -- Try not to use break when using this function;
    -- it may cause the array to be left with empty slots
    local ci = 0
    local remove = function()
        t[ci] = nil
    end
    return function(t, i)
        --print("I", table.concat(array, ','))
        i = i+1
        ci = i
        local v = t[i]
        if v == nil then
            local rj = 0
            for ri = 1, i-1 do
                if t[ri] ~= nil then
                    rj = rj+1
                    t[rj] = t[ri]
                    --print("R", table.concat(array, ','))
                end
            end
            for ri = rj+1, i do
                t[ri] = nil
            end
            return
        end
        return i, v, remove
    end, t, ci
end

它不使用table.remove，因此它应该具有O(N)复杂性。您可以将remove函数移动到 for 生成器中以消除对上值的需要，但这意味着每个元素都有一个新的闭包......这不是一个实际问题。

示例用法：

function math.isprime(n)
    for i = 2, n^(1/2) do
        if (n % i) == 0 then
            return false
        end
    end
    return true
end

array = {}
for i = 1, 500 do array[i] = i+10 end
print("S", table.concat(array, ','))
for i, v, remove in ripairs(array) do
    if not math.isprime(v) then
        remove()
    end
end
print("E", table.concat(array, ','))

小心不要使用break（或以其他方式过早退出循环），因为它会使数组留下nil元素。

如果你想说break“中止”（如，没有删除任何内容），你可以这样做：

function rtipairs(t, skip_marked)
    local ci = 0
    local tbr = {} -- "to be removed"
    local remove = function(i)
        tbr[i or ci] = true
    end
    return function(t, i)
        --print("I", table.concat(array, ','))
        local v
        repeat
            i = i+1
            v = t[i]
        until not v or not (skip_marked and tbr[i])
        ci = i
        if v == nil then
            local rj = 0
            for ri = 1, i-1 do
                if not tbr[ri] then
                    rj = rj+1
                    t[rj] = t[ri]
                    --print("R", table.concat(array, ','))
                end
            end
            for ri = rj+1, i do
                t[ri] = nil
            end
            return
        end
        return i, v, remove
    end, t, ci
end

这样做的好处是能够取消整个循环而不删除任何元素，并提供跳过已标记为“要删除”的元素的选项。缺点是新表的开销。

我希望这些对你有帮助。

Answer 5

table.remove出于性能原因（这可能或多或少与您的特定情况相关），我建议不要使用。

以下是这种类型的循环对我来说通常的样子：

local mylist_size = #mylist
local i = 1
while i <= mylist_size do
    local value = mylist[i]
    if value == 123 then
        mylist[i] = mylist[mylist_size]
        mylist[mylist_size] = nil
        mylist_size = mylist_size - 1
    else
        i = i + 1
    end
end

注意这很快，但有两个警告：

• 如果您需要删除相对较少的元素，它会更快。（它实际上对应该保留的元素不起作用）。
• 它将使数组未排序。有时您并不关心排序数组，在​​这种情况下，这是一个有用的“快捷方式”。

如果您想保留元素的顺序，或者您希望不保留大部分元素，请查看 Mitch 的解决方案。这是我和他的粗略比较。我在https://www.lua.org/cgi-bin/demo上运行它，大多数结果与此类似：

[    srekel] elapsed time: 0.020
[     mitch] elapsed time: 0.040
[    srekel] elapsed time: 0.020
[     mitch] elapsed time: 0.040

当然，请记住，它会因您的特定数据而异。

这是测试的代码：

function test_srekel(mylist)
    local mylist_size = #mylist
    local i = 1
    while i <= mylist_size do
        local value = mylist[i]
        if value == 13 then
            mylist[i] = mylist[mylist_size]
            mylist[mylist_size] = nil
            mylist_size = mylist_size - 1
        else
            i = i + 1
        end
    end

end -- func

function test_mitch(mylist)
    local j, n = 1, #mylist;

    for i=1,n do
        local value = mylist[i]
        if value ~= 13 then
            -- Move i's kept value to j's position, if it's not already there.
            if (i ~= j) then
                mylist[j] = mylist[i];
                mylist[i] = nil;
            end
            j = j + 1; -- Increment position of where we'll place the next kept value.
        else
            mylist[i] = nil;
        end
    end
end

function build_tables()
    local tables = {}
    for i=1, 10 do
      tables[i] = {}
      for j=1, 100000 do
        tables[i][j] = j % 15373
      end
    end

    return tables
end

function time_func(func, name)
    local tables = build_tables()
    time0 = os.clock()
    for i=1, #tables do
        func(tables[i])
    end
    time1 = os.clock()
    print(string.format("[%10s] elapsed time: %.3f\n", name, time1 - time0))
end

time_func(test_srekel, "srekel")
time_func(test_mitch, "mitch")
time_func(test_srekel, "srekel")
time_func(test_mitch, "mitch")

Answer 6

简单的..

values = {'a', 'b', 'c', 'd', 'e', 'f'}
rem_key = {}

for i,v in pairs(values) do
if remove_value() then
table.insert(rem_key, i)
end
end

for i,v in pairs(rem_key) do
table.remove(values, v)
end

Answer 7

这基本上是在以非功能性风格重述其他解决方案；我发现这更容易理解（也更难出错）：

for i=#array,1,-1 do
  local element=array[i]
  local remove = false
  -- your code here
  if remove then
    array[i] = array[#array]
    array[#array] = nil
  end
end

Answer 8

您可能会考虑使用优先级队列而不是排序数组。当您按顺序删除条目时，优先级队列将有效地压缩自身。

有关优先队列实现的示例，请参阅此邮件列表线程： http: //lua-users.org/lists/lua-l/2007-07/msg00482.html

Answer 9

我突然想到——对于我的特殊情况，我只从队列的前面移动条目——我可以通过以下方式更简单地做到这一点：

function processEventsBefore( timestamp )
  while timestampedEvents[1] and timestampedEvents[1][1] <= timestamp do
    processEventData( timestampedEvents[1][2] )
    table.remove( timestampedEvents, 1 )
  end
end

但是，我不会接受这个作为答案，因为它不能处理迭代数组并在继续迭代时从中间删除随机项的一般情况。

Answer 10

您可以使用仿函数来检查需要删除的元素。额外的收获是它在 O(n) 中完成，因为它不使用 table.remove

function table.iremove_if(t, f)
    local j = 0
    local i = 0
    while (i <= #f) do
        if (f(i, t[i])) then
            j = j + 1
        else
            i = i + 1
        end
        if (j > 0) then
            local ij = i + j
            if (ij > #f) then
                t[i] = nil
            else
                t[i] = t[ij]
            end
        end
    end
    return j > 0 and j or nil -- The number of deleted items, nil if 0
end

用法：

table.iremove_if(myList, function(i,v) return v.name == name end)

在你的情况下：

table.iremove_if(timestampedEvents, function(_,stamp)
    if (stamp[1] <= timestamp) then
        processEventData(stamp[2])
        return true
    end
end)

Answer 11

首先，一定要阅读@MitchMcCabers 的帖子，详细说明table.remove().

现在我不是 lua 高手，但我尝试将他的方法与@MartinRudat 的方法结合起来，使用从@PiFace 的答案修改而来的数组检测方法的辅助。

根据我的测试，结果成功地从键值表或数组中删除了一个元素。

我希望它是正确的，到目前为止它对我有用！

--helper function needed for remove(...)
--I’m not super able to explain it, check the link above
function isarray(tableT)
    for k, v in pairs(tableT) do
        if tonumber(k) ~= nil and k ~= #tableT then
            if tableT[k+1] ~= k+1 then
                return false
            end
        end
    end
    return #tableT > 0 and next(tableT, #tableT) == nil
 end

function remove(targetTable, removeMe)
--check if this is an array
if isarray(targetTable) then
    --flag for when a table needs to squish in to fill cleared space
    local shouldMoveDown = false
    --iterate over table in order
    for i = 1, #targetTable do
        --check if the value is found
        if targetTable[i] == removeMe then
            --if so, set flag to start collapsing the table to write over it
            shouldMoveDown = true
        end
        --if collapsing needs to happen...
        if shouldMoveDown then
            --check if we're not at the end
            if i ~= #targetTable then
                --if not, copy the next value over this one
                targetTable[i] = targetTable[i+1]
            else
                --if so, delete the last value
                targetTable[#targetTable] = nil
            end 
        end
    end
else
    --loop over elements
    for k, v in pairs(targetTable) do
        --check for thing to remove
        if (v == removeMe) then
            --if found, nil it
            targetTable[k] = nil
            break
        end
    end
end
return targetTable, removeMe;

结尾

Answer 12

效率！更！)

关于米奇的变种。它对 nil 有一些浪费分配，这里是具有相同想法的优化版本：

function ArrayRemove(t, fnKeep)
    local j, n = 1, #t;
    for i=1,n do
        if (fnKeep(t, i, j)) then
            -- Move i's kept value to j's position, if it's not already there.
            if (i ~= j) then
                t[j] = t[i];
            end
            j = j + 1; -- Increment position of where we'll place the next kept value.
        end
    end
    table.move(t,n+1,n+n-j+1,j);
    --for i=j,n do t[i]=nil end
    return t;
end

这是更优化的版本，带有块移动

对于更大的数组和更大的保留块

function ArrayRemove(t, fnKeep)
    local i, j, n = 1, 1, #t;
    while i <= n do
        if (fnKeep(t, i, j)) then
            local k = i
            repeat
                i = i + 1;
            until i>n or not fnKeep(t, i, j+i-k)
            --if (k ~= j) then
                table.move(t,k,i-1,j);
            --end
            j = j + i - k;
        end
        i = i + 1;
    end
    table.move(t,n+1,n+n-j+1,j);
    return t;
end

if (k ~= j) 不需要，因为它执行了很多次，但在第一次删除后为“true”。我认为 table.move() 无论如何都会处理索引检查。
table.move(t,n+1,n+n-j+1,j) 等价于“for i=j,n do t[i]=nil end”。
我是 lua 新手，不知道有效的价值复制功能在哪里。在这里，我们将复制 nil n-j+1 次。

关于 table.remove()。我认为它应该利用 table.move() 在一个操作中移动元素。C中的一种memcpy。所以也许它毕竟不是那么糟糕。
@MitchMcMabers，你能更新你的基准吗？你使用 lua >= 5.3 吗？