这个问题类似于如何在删除键但是明显不同的情况下安全地迭代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
Mud*_*Mud 41
迭代数组并从中间删除随机项同时继续迭代的一般情况
如果你是从前到后迭代,当你删除元素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在迭代期间删除元素:
从后到前迭代.
for i=#input,1,-1 do
if remove[input[i]] then
table.remove(input, i)
end
end
手动控制循环变量,因此我们可以在删除元素时跳过增加它:
local i=1
while i <= #input do
if remove[input[i]] then
table.remove(input, i)
else
i = i + 1
end
end
对于非数组表,您可以使用next或pairs(根据其实现next)进行迭代,并设置要删除的项目nil.
请注意,table.remove每次调用时都会移动所有后续元素,因此N次删除的性能是指数级的.如果您要删除大量元素,则应自行移动项目,如LHF或Mitch的答案.
lhf*_*lhf 21
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
Mit*_*ers 10
警告：请勿使用table.remove（）。每次您调用该函数以删除数组条目时，该函数都会使所有后续（以下）数组索引重新索引。因此，仅在单个直通OURSELVES中“压缩/重新编制索引”表要快得多！
最好的技术很简单：i在所有数组条目中向上计数（），同时跟踪位置，我们应将下一个“保留”值放入（j）。任何未保留的内容（或从i移到的内容j）都被设置为nil告诉Lua我们已经删除了该值。
我分享了这个信息，因为我真的不喜欢本页上的其他答案（截至2018年10月）。它们要么是错误的，bug缠身的，过于简单的或过于复杂的，而且大多数都是超慢的。因此，我改为实现了一种高效，干净，超快速的单遍算法。单循环。
这是一个经过充分注释的示例（本文结尾处有一个简短的非教程版本）：
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
最后，这是在您自己的代码中使用的函数，而没有所有的教程印刷内容……，并且只带有一些用于解释最终算法的最少注释：
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
而已！
而且，如果您不想使用整个“可重复使用的回调/函数”设计，则只需将内部代码复制ArrayRemove()到项目中，然后将行更改if (fnKeep(t, i, j)) then为if (t[i] == 'deleteme') then...，这样就可以摆脱函数调用/ callback开销也可以加快速度！
就我个人而言，我使用可重复使用的回调系统，因为它仍然table.remove()比100-1000 +倍的速度大得多。
奖励（高级用户）：普通用户可以跳过阅读此奖励部分。它描述了如何同步多个相关表。请注意，的第3个参数
fnKeep(t, i, j)，是j，是一个奖励参数，它使您的keep-function可以知道每次fnKeep回答时该值将存储在哪个索引处true（以保持该值）。用法示例：假设您有两个“链接”表，其中一个是
table['Mitch'] = 1; table['Rick'] = 2;（用于通过命名字符串快速查找数组索引的哈希表），另一个是array[{Mitch Data...}, {Rick Data...}]（具有数字索引的数组，其中Mitch的数据位于pos1且Rick的数据2完全位于哈希表中所描述的pos处）。现在，您决定遍历array和Mitch Data，从而Rick Data从一个位置移动到另一个2位置1...
fnKeep(t, i, j)然后，您的函数可以轻松地使用j信息来更新哈希表指针，以确保它们始终指向正确的数组偏移量：Run Code Online (Sandbox Code Playgroud)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从而从查找哈希表和数组中删除“ Mitch”，并将“ Rick”哈希表项移至指向其数组数据要移至的
1（即的值j）（由于i和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开始运行测试。我的ArrayRemove()算法在2.8秒内完成...内置的Lua table.remove()算法到目前为止仍在运行...我将对其进行更新稍后发布... ;-)
更新：现在是格林尼治标准时间2018年11月1日14:55，该table.remove()算法仍未完成。我将中止该部分测试，因为Lua在过去10个小时中一直在使用100％的CPU ，并且现在需要我的计算机。而且它的温度足以在笔记本电脑的铝制外壳上煮咖啡...
结果如下：
ArrayRemove()功能：2.8秒。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万个项目...反复执行此操作...
你不应该，EVER使用table.remove()！它的性能损失迅速增长。这是一个具有较小数组大小的示例，以证明这一点：
ArrayRemove()：: 0.001秒，table.remove()：0.018秒（慢18倍）。ArrayRemove()：: 0.014秒，table.remove()：1.573秒（慢112.4倍）。ArrayRemove()0.142秒；table.remove()：3分钟48秒（慢1605.6倍）。ArrayRemove()2.802秒，table.remove()：我决定在10小时后中止测试，因此我们可能永远不会花多长时间。;-)但是，在当前时间点（甚至还没有完成），它花费的时间比12847.9倍长ArrayRemove()。但是table.remove()，如果我让它完成，最终结果可能会慢30到40千倍。如您所见，table.remove()时间的增长不是线性的（因为如果是这样，那么我们的100万项测试只需要10万（10万）测试的10倍，而相反，我们看到的是1.573s对3m48s！） ）。因此，我们不能接受较低的测试（例如1万个项目），而只能将其乘以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更好：
ArrayRemove()0.005秒，table.remove()：20.783秒（比ArrayRemove()... 慢4156.6倍……但是，这个LuaJIT结果实际上比常规Lua 的WORSE比率低，后者table.remove()仅为“ 慢 ” 1605.6倍比我的算法在同一个测试中要好...因此，如果您使用LuaJIT，则性能比甚至更支持我的算法！）最后，您可能想知道“ table.remove()如果只删除一项，因为它是本机函数，会更快吗？”。如果使用LuaJIT，则该问题的答案是：否。在LuaJIT中，ArrayRemove()它table.remove()甚至比删除一个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()...并玩得开心！:-)
试试这个功能：
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-generator 中以消除对 upvalue 的需要，但这意味着每个元素都有一个新的闭包……这不是一个实际问题。
用法示例：
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
这具有能够取消整个循环而不删除任何元素的优点，以及提供跳过已标记为“要删除”的元素的选项。缺点是新表的开销。
我希望这些对你有帮助。