I read a long and well-argued rant against lua’s implementation of table.remove(...).
Based on various suggestions from Stack Overflow, I’ve come up with an alternate version that seems to work well. I don’t know how it compares speed-wise, but it does at least seem to work for both arrays and key-value tables.
It relies on this method for checking whether a table is an array or not:
function isarray(tableT)
--has to be a table in the first place of course
if type(tableT) ~= "table" then return false end
--not sure exactly what this does but piFace wrote it and it catches most cases all by itself
local piFaceTest = #tableT > 0 and next(tableT, #tableT) == nil
if piFaceTest == false then return false end
--every numerical key except the last must have a key one greater
for k,v in ipairs(tableT) do
if tonumber(k) ~= nil and k ~= #tableT then
if tableT[k+1] == nil then
return false
end
end
end
--otherwise we probably got ourselves an array
return true
end
And then, using that, this function removes values from any kind of table without having to know their index:
function remove(targetTable, removeMe)
--make a flag for scooting down all the elements an array
local shouldMoveDown = false ;
--loop over elements
for i=1, #targetTable do
--check for thing to remove
if (targetTable[i] == removeMe) then
--check if this is an array
if isarray(targetTable) then
--if it is, flip shouldMoveDown
shouldMoveDown = true
else
--otherwise overwrite current element with last element
targetTable[i] = targetTable[#targetTable]
--and nil out last element and done!
targetTable[#targetTable] = nil
break
end
end
--check if shouldMoveDown (which means it's confirmed as array)
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
return targetTable, removeMe;
end
I’m totally willing to concede I may have missed some cases, and I don’t know if these things will even be useful to anyone else. But apparently there’s lots of reasons to hate table.remove(...), so this could be an alternative.
This is a good implementation but maybe a bit heavy? I already shared it in the other thread but I’ve made this simple Queue data structure that lets you add items to them and remove by name while also providing an array for sequencing-
Queue = class()
function Queue:init()
self.queue = {}
self.map = {}
end
function Queue:enqueue(name, value)
self.queue[#self.queue + 1] = value
self.map[name] = #self.queue
self.map[#self.queue] = name
end
function Queue:unqueue(name)
local index = self.map[name]
for i = index, #self.queue do
self.map[i] = self.map[i + 1]
if self.map[i] then
self.map[self.map[i]] = i
end
self.queue[i] = self.queue[i + 1]
end
self.map[name] = nil
end
I guess in my case you need to have a unique name (which can just be #myQueue.queue+1), while with yours it will work with any table. But keeping track of table array positions can get hairy so I find having a name identifier works best for me.
But in your way you’re also searching by value which can be a problem:
--check for thing to remove
if (targetTable[i] == removeMe) then
What if two different keys have the same removeMe value? How do you know you’re getting rid of the correct one? Also does this kind of equality check work on functions stored as the values or deeply nested tables?
I don’t fully understand metatables, but if I wanted to take this kind of functionality and make it a metatable, so I could add it to any normal lua table at will, would that work?
I don’t really understand metatables yet either. My experience is in JS programming and Lua is really similar. From what I can gather currently, metatables are very similar to js prototypes so in theory I think you are right, you should be able to add methods to the table metatable to handle the queue and unqueue
@UberGoober Why do you hate table.remove(). In your above code, you’re checking for an array. Lua doesn’t have arrays, just tables or strings. In your code where you find a match, you move the last table value to the current position and nil out the last table position. I don’t see any code to check if the last table value would have matched the removeMe value. It would then be skipped. It looks like you’re doing a lot of work but not guaranteeing that everything that should be removed is being removed. I find that using table.remove does exactly what it should.
when i want a table that supports remove, i generally use a hash-style table, which does remove in O(1) time. i’ve started wrapping tables with special properties in a small object that supports whatever special stuff i need.
@skar I took @UberGoober code above, stripped it down and tried it on a 1,000,000 item table. It was a lot faster than the table.remove, but it still had the problem of not checking for a match when moving the last item to the current.
@UberGoober Your code has a “break” command in it which means you’ll exit your code after the first match. If a table contains more than 1 item to be removed, you’ll have to call it again. You’ll have to call it as many times as needed until no more items are removed.
If the “break” command is removed, then you’ll check the whole table in one pass, but if there happens to be an entry to be removed at the end of the table, you’ll replace a matched entry with another entry that should be removed and you’ll miss it because you’ll go on to the next item before rechecking the new current entry.
Just a quick example. Fill a table with all the same values. Then try to remove all the entries that have that value.
Your code will work if a table only has 1 entry to be removed at a time, but that’s not always the case.
@RonJeffries of course that’s great for a lot of cases, but to apply that trick when you have a table that has to keep a consistent sort order requires keeping two different tables, one for the sort order and one for the hash, and cross-referencing them, I think.
I think that’s actually a pretty common approach for lua pros, but it makes my head hurt so I’m glad to avoid it when I can.
@dave1707 I think this now catches that “last element” bug. It actually avoids the swapping altogether—it should have been nilling the value in the first place.
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;
end
As for removing only one value, that’s intended behavior. Modifying a table even once while iterating through it is asking for trouble, if I recall correctly, so I have to break and stop the iteration immediately after doing the removing.
@UberGoober It doesn’t matter if you remove only one match or you get rid of the “break” and you go thru the whole table and remove all the matches. The table still exists full size with nil entries. Using the “pairs” for loop ignores the nil entries, but using a [ ] for loop will read those nil entries. So depending on what you do with the table, you can end up with a table that increases in size and has a lot of nil entries in it.
By putting nil in the table, your not modifying the table size or altering the position of unread entries. So you can go thru the whole table at once. The downside is a table filled with nil.
@RonJeffries The # still works if there are nil values in the table. The # doesn’t work on keyed tables. I use table.remove also, but I always use it going thru a table in reverse order.
I have done tests with sparse arrays and, at least in the conditions I thought to test, it handles nil values fine.
@dave1707 you know more than I do about all this stuff, but I just know from long hours spent searching for bugs that modifying something as you’re iterating through it is a bad idea in general—it might be totally fine if you know what you’re doing to the extent that you seem to, but I’ve personally lost too many hours to that beast to want to go near its cave again.
@RonJeffriestable.remove() requires you to know the index of removal, and of course on hash tables there isn’t an index so you can’t use it at all.
Personally I’d prefer a simple command that works on every kind of table and only requires that I know the thing I want gone and the table I want it gone from—though I’ll admit I’m scared to use what I’ve done here in my actual code because I’m not 100% sure of it.
I tested the table methods vs my queue and the queue is way slower
-- Test
local mathRandom = math.random
local socket = require('socket')
local time = socket.gettime
local limit = 1000000
local remove = 1000
function setup()
startTableFillTime = time()
tableA = fillTable()
endTableFillTime = time()
tableFillTime = endTableFillTime - startTableFillTime
startQueueFillTime = time()
queueA = fillQueue()
endQueueFillTime = time()
queueFillTime = endQueueFillTime - startQueueFillTime
print('tableFillTime: '..tableFillTime)
print('queueFillTime: '..queueFillTime)
end
function draw()
background(40, 40, 50)
end
function touched(touch)
if touch.state == ENDED then
removeFromTable()
removeFromQueue()
end
end
function fillTable()
local t = {}
for i = 1, limit do
table.insert(t, mathRandom(1, limit))
end
return t
end
function removeFromTable()
local uniqueRandoms = getUniqueRandoms(1, limit, remove)
local start = time()
for k, v in pairs(uniqueRandoms) do
table.remove(tableA, v)
end
local endT = time()
print('removeFromTable: '..(endT - start))
end
function fillQueue()
local q = Queue()
for i = 1, limit do
q:enqueue(i, mathRandom(1, limit))
end
return q
end
function removeFromQueue()
local uniqueRandoms = getUniqueRandoms(1, limit, remove)
local start = time()
for k, v in pairs(uniqueRandoms) do
queueA:unqueue(v)
end
local endT = time()
print('removeFromQueue: '..(endT - start))
end
function getUniqueRandoms(from, to, amount)
local results = {}
function recurRandom(f, t)
local n = math.random (f, t)
if results[n] then
recurRandom(f, t)
else
results[n]=n
end
end
for i = 1, (amount or 1) do
recurRandom(from, to)
end
return results
end
Queue = class()
function Queue:init()
self.queue = {}
self.map = {}
end
function Queue:enqueue(name, func)
self.queue[#self.queue + 1] = func
self.map[name] = #self.queue
self.map[#self.queue] = name
end
function Queue:unqueue(name)
local index = self.map[name]
for i = index, #self.queue do
self.map[i] = self.map[i + 1]
if self.map[i] then
self.map[self.map[i]] = i
end
self.queue[i] = self.queue[i + 1]
end
self.map[name] = nil
end
Maybe table.remove is much better now in Lua 5.4 so the old assumption of it being slow is wrong?
This is the SO answer I had come across, not sure if it’s the same one @UberGoober saw: https://stackoverflow.com/a/53038524
