lua - 为什么 Lua 中的大型队列在使用表删除/插入时效率低下？

Question

来自PiL（第 1 版和第 2 版）：

尽管我们可以使用 insert 和 remove（从表库中）轻松实现队列，但对于大型结构，这种实现可能太慢了。更有效的实现使用两个索引，一个用于第一个元素，另一个用于最后一个元素......

这是因为重新索引吗？还是有其他原因导致大型结构效率低下？

Answer 1

我在本书后面找到了答案：http ://www.lua.org/pil/19.2.html

...从数组中的给定位置删除（并返回）一个元素，向下移动其他元素以关闭空间并减小数组的大小。

要在结构的另一端插入，我们使用 table.insert(a, 1, x); 为此，我们使用 table.remove(a, 1) 删除。最后两个操作不是特别有效，因为它们必须上下移动元素。但是，因为表库在 C 中实现了这些函数，所以这些循环不会太昂贵，而且这种实现对于小型数组（例如，多达数百个元素）来说已经足够了。