This is actually exactly what I was doing, originally. But I have to check for underflow for most operations. And nil is a valid value. And using insert/remove causes some extra GC thrash. And even if you're just poking at the end position, insert and remove take linear time because the use the # operator (or equivalent function?) which counts the entire array from 1 every time, so I have to cache and update the stack height. And, and, and...
I’m pretty sure insert/remove do NOT take linear time, though the time is complex to compute since Lua may or may not have migrated the array to the “array part” of the table. In either case your insert/remove time will be much closer to O(1) than O(n) since the table is based on hashing. I also suspect avoiding the use of ‘nil’ as a valid value would help.
More broadly, while Lua is a great language for many things, it’s design point is not purely speed, speed, speed. If speed is really vital to you, then perhaps Lua is not the correct choice for your project?
—Tim
|
