在迭代数组表时，安全地删除其中的项。
概述
给定一个由 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
迭代数组并在中间删除随机项并继续迭代的一般情况
如果您按顺序从前到后迭代，当您删除第N个元素时，您迭代的下一个元素（N+1）会被移动到该位置。如果您增加迭代变量（如i翻译：这里用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的答案中一样手动移动这些项。
我建议避免使用 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
你可能要考虑使用 优先队列 而非排序数组。 当你按顺序删除条目时，优先队列将高效地自我压缩。
关于优先队列的实现示例，请参阅此邮件列表线程：http://lua-users.org/lists/lua-l/2007-07/msg00482.html
尝试使用此函数：
function ripairs(t)
-- 当使用此函数时，请尽量不要使用 break；
-- 它可能会导致数组中留下空槽
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
这样做的优点是可以取消整个循环并且不会删除任何元素，同时还提供了跳过已标记为“要删除”的元素的选项。缺点是需要一个新的表的开销。
希望这些对你有所帮助。
我建议不要使用 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
注意这很快，但有两个注意点：
- 如果你需要删除相对较少的元素，它会更快。（它实际上不为应保留的元素执行任何工作）。
- 它将使数组保持未排序状态。有时，你不关心有一个排序好的数组，那么这将是一个有用的“捷径”。
如果你想保留元素的顺序，或者不期望保留大多数元素，请参考米奇的解决方案。以下是我的和他的粗略比较。我在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
-- 将i的已保留值移到j的位置，如果它还不在那里。
if (i ~= j) then
mylist[j] = mylist[i];
mylist[i] = nil;
end
j = j + 1; -- 递增下一个已保留值的位置.
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")
你可以使用一个函数对象来检查需要删除的元素。另一个好处是它的时间复杂度是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 -- 删除的元素数量，如果是0就返回nil
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)
简单..
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
简单的代码，用于从values列表中删除特定的值。rem_key列表用于存储需要从values中删除的值的索引。第一个for循环遍历values，并在调用remove_value()函数时检查其是否需要从列表中删除该值。如果需要，则将该值的索引添加到rem_key中。第二个循环使用table.remove函数从values中删除具有特定索引的值。
这基本上是在非函数式风格下重新陈述其他解决方案；我发现这样更容易理解（也更难出错）：
for i = #array, 1, -1 do
local element = array[i]
local remove = false
-- 在此编写您的代码
if remove then
array[i] = array[#array]
array[#array] = nil
end
end
首先，务必阅读@MitchMcCabers的问题详细介绍table.remove()的问题。
虽然我不是Lua专家，但我尝试将他的方法与@MartinRudat的方法相结合，使用@PiFace的答案修改的数组检测方法。
根据我的测试，结果可以成功地从键值表或数组中移除元素。
我希望一切都是正确的，到目前为止，它对我有用！
-- 移除函数的辅助函数
-- 我无法解释，可查看上面的链接
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)
--检查是否为数组
if isarray(targetTable) then
--标记表中是否需要移除值
local shouldMoveDown = false
--按顺序遍历表
for i = 1, #targetTable do
--检查是否存在目标值
if targetTable[i] == removeMe then
--如果是，则将shouldMoveDown标记为true，以便移除值后压缩表
shouldMoveDown = true
end
--如果需要缩小表
if shouldMoveDown then
--检查当前索引是否为表的最后一个索引
if i ~= #targetTable then
--如果不是，将下一个值复制到当前位置
targetTable[i] = targetTable[i+1]
else
--如果是，删除最后一个值
targetTable[#targetTable] = nil
end
end
end
else
--循环遍历元素
for k, v in pairs(targetTable) do
--检查是否为目标值
if (v == removeMe) then
--如果是，将其赋值为nil
targetTable[k] = nil
break
end
end
end
return targetTable, removeMe;
end
效率！变得更加高效！）
关于Mitch的变量。它有一些对nil的浪费分配，这里是具有相同思想的经过优化的版本：
function ArrayRemove(t, fnKeep)
local j, n = 1, #t;
for i=1,n do
if (fnKeep(t, i, j)) then
-- 如果将i保留的值移动到j的位置上，则不会移动为i的值。
if (i ~= j) then
t[j] = t[i];
end
j = j + 1; --增加下一个保留值的位置。
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) 不需要，因为它在第一次删除后执行了很多次，就是“真”的。我认为 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？
作者:
用户405017
- 如何将两个不同的lua文件合成一个 东西有点长 大佬请耐心看完 我是小白研究几天了都没搞定
- 如何在roblox studio中1：1导入真实世界的地形？
- 求解，lua_resume的第二次调用继续执行协程问题。
- 【上海普陀区】内向猫网络招募【Skynet游戏框架Lua后端程序员】
- SF爱好求教：如何用lua实现游戏内调用数据库函数实现账号密码注册？
- Lua实现网站后台开发
- LUA错误显式返回，社区常见的规约是怎么样的
- lua5.3下载库失败
- 请问如何实现文本框内容和某个网页搜索框内容连接，并把网页输出来的结果反馈到另外一个文本框上
- lua lanes多线程使用
- 一个kv数据库
- openresty 有没有比较轻量的 docker 镜像
- 想问一下，有大佬用过luacurl吗
- 在Lua执行过程中使用Load函数出现问题
- 为什么 neovim 里没有显示一些特殊字符?
- Lua比较两个表的值（不考虑键的顺序）
- 有个lua简单的项目，外包，有意者加微信 liuheng600456详谈，最好在成都
- 如何在 Visual Studio 2022 中运行 Lua 代码？
- addEventListener 返回 nil Lua
- Lua中获取用户配置主目录的跨平台方法
我想到一个对于我特殊情况的更简单的方法——我只需从队列的前面移动条目即可，代码如下：
function processEventsBefore( timestamp ) while timestampedEvents[1] and timestampedEvents[1][1] <= timestamp do processEventData( timestampedEvents[1][2] ) table.remove( timestampedEvents, 1 ) end end然而，我不能接受这个方法作为答案，因为它无法处理遍历数组并同时移除中间随机项的一般情况。