7

我正在做一些递归解析。

目前我有一个假堆栈，我在其中存储有限状态机的状态，因此当我递归向下钻取时，我推送我所处的状态，并在处理完递归的文本位后将其弹出。

有一个“状态ID”堆栈会更快吗：

 int* stack = 0
 int top = 0;
 // ...
 // drill down bit
 if (stack == 0)
     stack = (int*)malloc(STACK_JUMP_SIZE);
 else if (top % STACK_JUMP_SIZE == 0)
     stack = (int*)realloc(stack, (top+STACK_JUMP_SIZE) * sizeof(int));
 stack[top++] = currentState;
 // ...
 // pop up later
 {currentState = stack[--top]; {
 if (top == 0) {
     free(stack);
     stack = 0;
 } else if ((top+1) % STACK_JUMP_SIZE == 0) {
     stack = (int*)realloc(stack, (top+1)*sizeof(int));
 }

或者将事物拆分为适当的函数并让 C++ 担心堆栈会更快。

（我知道有人会告诉我“那是 C，它不是 C++”，所以我先发制人地回答，我的程序是 C++，但里面有很多 C）。

4

1 回答 1

9

这取决于实施——没有办法提前说。在函数调用便宜的机器上（例如 SPARC），函数堆栈可能会更快，但即使在那里，也会出现本地化等问题。（机器堆栈占用更多空间，因为它比您的模拟堆栈堆叠更多信息。）我会将事物拆分为适当的递归函数，并且只有在这被证明是瓶颈时才尝试手动堆栈管理。除非... 手动堆栈管理确实有一个重要优势：错误处理。机器堆栈溢出是未定义的行为：如果malloc或realloc返回一个空指针，您至少可以干净地报告错误。

如果您确实模拟堆栈，则应考虑使用，std::vector而不是malloc// realloc。free如果出现异常，它会为您节省时间，并且它也可能会更快一点。如果您可以为堆栈大小设置一个上限，并且它不是不合理的大，那么将堆栈声明为堆栈上的 C 样式数组会更快。

于 2012-02-17T10:41:55.893 回答