是一個虛擬棧比一個真正的棧更快

目前我有一個假的堆棧，在那裏我爲我的有限狀態機存儲狀態，所以當我遞歸地向下鑽取時，我推入了我所處的狀態，稍後在完成處理遞歸位文本後彈出它。

難道是快有一個「狀態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）。

來源

2012-02-17 matiu

我個人認爲正常的功能會更快..但是有人比我想的要多很多，我覺得這個假的堆棧更快。現在我想看到更多的人比我更多的意見:) – matiu 2012-02-17 10:25:18

@matu這取決於機器。在Sparc上，函數調用需要零內存訪問，並且可能會更快。在英特爾，你最終會將你的返回地址和幀指針保存在內存中，以及該函數需要的任何參數：這可能非常昂貴。 – 2012-02-17 10:43:50

這取決於實施—有沒有辦法說預先。在函數調用很便宜的機器上（例如SPARC），函數堆棧可能會更快，但即使在那裏，本地化問題（例如本地化）也會介入。（機器堆棧需要更多空間，因爲它會堆疊更多的信息，而不是模擬的堆棧。）我會將這個東西分解爲正確的遞歸函數，並且只有在這個證明是瓶頸時才嘗試手動堆棧管理。除非...手動堆棧管理確實有一個重要的優點：錯誤處理。機器堆棧溢出是未定義的行爲：如果malloc或realloc返回空指針，您至少可以報告錯誤。

如果做模擬堆，你應該考慮使用std::vector，而不是malloc/realloc/free。如果有異常，它會爲您節省，並且它可能會更快一些。如果可以爲堆棧大小設置一個上限，並且這並不是不合理的大小，那麼將該堆棧聲明爲堆棧上的C風格陣列的速度甚至會更快，即使也會更快。

來源

2012-02-17 10:41:55

或者'std :: stack'，偶數。 – 2012-02-17 11:30:46

@SteveJessop好點。如果沒有別的，它的名字就是一個意圖的表達（這反過來又有助於理解代碼）。 – 2012-02-17 11:58:33

謝謝詹姆斯。我最初使用矢量，發現它稍慢。我想是因爲它重新分配更多;我敢肯定這可能會被修改。謝謝史蒂夫。我會看std :: stack。 – matiu 2012-02-17 13:58:10

是一個虛擬棧比一個真正的棧更快

回答

相關問題