I'm by no means an expert in performance (If anything, I am the contrary), but I have some remarks.
I never use
table.remove or
table.insert. If I am going to be doing frequent insertions and deletions, what I try to do first is using the items as keys, like this:
Code: Select all
t[new_item]=1 -- insertion
t[old_item]=nil -- deletion
if t[some_item] then ... -- checking for existence
for v in pairs(t) do ... -- parsing
Insertion and deletion is super fast. Checking for existence is super fast too. The only problem is parsing: pairs is slower than a numerical loop, and the items will be parsed in random order. In a scenario where addition/deletion happens more often than parsing, this can be quite fast.
If I need to keep the order for some reason, I rely heavily on the fact that just popping the last element is really fast, and so is adding an element at the end:
Code: Select all
t[#t]=nil -- remove
t[#t + 1]=new_item -- add new
(I also cache the "len" of the array in a variable and increment it before each insert, not re-calculating #t each time).
When I need to remove some non-last value, I can replace that value by the last one, and then remove the last one. Like this:
Code: Select all
t[i]=t[#t] -- replace by last element
t[#t]=nil -- remove last element
(Again, assume that #t is cached in a variable). I think that approach is still faster than invoking table.remove, but I confess that I have not tested this.
Inserting things not-at-the-end is the only place where I would need table.insert. But in reality I never do that.
My impression is that table.remove & insert are only useful when you have an array-like table with random deletes & inserts, and
you need to keep it in certain order, and you can't use table.sort. I have personally never needed such table - I guess someone might do. But I think that if you want to compare the speed of a data structure with Lua's tables, you should compare it with the insertion-at-end and replacing-by-last-and-deleting-last approaches I have just discussed. These are what someone concerned about speed will use.
