Lua栈操作的复杂性（Lua C API）

Question

在 Lua C API 中，它提供了几个堆栈操作函数，如 Lua 的文档 所述。

int   lua_gettop (lua_State *L);
void  lua_settop (lua_State *L, int index);
void  lua_pushvalue (lua_State *L, int index);
void  lua_remove (lua_State *L, int index);
void  lua_insert (lua_State *L, int index);
void  lua_replace (lua_State *L, int index);

我的第一个问题是，这些函数的复杂度是什么？它是O（1）还是O（|index|）？我查看了Lua手册，发现Lua有两种不同的堆栈实现（基于堆栈和基于寄存器）。

更具体地说，如果我想从lua堆栈中读取并弹出前三个元素，我可以考虑以下两种实现方式，请问哪一种更具性能/推荐性？

解决方案1 - 逐个读取和弹出值：

for (int i = 0; i < 3; ++i) {
  values[i] = lua_tostring(lua_state, -1);
  ...
  lua_pop(lua_state, 1);
}

解决方案2 -- 先读取全部然后再逐一弹出：

for (int i = 0; i < 3; ++i) {
  values[i] = lua_tostring(lua_state, -1 - i);
}
...
lua_pop(lua_state, 3);

- keelar

---

为什么不看源代码呢？ - user253751

但是不同版本可能有不同的实现？只想知道一个是否总是优于另一个。 - keelar

一个建议.. lua_tostring 返回的指针在从堆栈中弹出后不能保证有效。请参阅手册中的 lua_tolstring。如果需要保留字符串值，请进行复制。 - Adam

Answer 1

Lua 5.3 defines lua_pop as

这句话意思是“Lua 5.3将lua_pop定义为……”，其中的HTML标签保留。

#define lua_pop(L,n)            lua_settop(L, -(n)-1)

在此可以看到lua_settop，它会填充堆栈槽位为nil，以便值可以被垃圾回收。因此，当参数是1时，它的时间复杂度为O(1)。这里。

您可以在O(1)时间内读取每个值，并且弹出N个值的时间复杂度为O(N)。

因此，您的两种方法应该大致相等。

关于在O(1)时间内读取值，函数index2addr将堆栈偏移量转换为地址。

- Doug Currie

---

这个回答似乎完全没有意义。问题是访问元素-3是否比访问元素-1慢。问题甚至不涉及lua_pop！即使是，你的回答也没有告诉我们关于lua_pop速度的任何信息。 - user253751

@immibis，抱歉，在回复之前我发布了。希望现在更清楚了。 - Doug Currie

然иҖҢпјҢиҝҷдёӘй—®йўҳ并дёҚжҳҜеңЁиҜўй—®lua_popзҡ„жҖ§иғҪпјҢиҖҢжҳҜеңЁиҜўй—®и®ҝй—®е Ҷж Ҳзҡ„е…¶д»–еҮҪж•°зҡ„жҖ§иғҪгҖӮ - user253751

谢谢您的回答。关于“您可以在O(1)中读取每个值”，您是否有参考资料来证明这一点？ - keelar

没错，但是 lua_pop 实际上是 O(N) 中占主导地位的操作。 - Doug Currie

@keelar，请查看我在index2addr上的补充说明。 - Doug Currie