作爲一個關於這段代碼的一小部分的原始問題的後續行動,我決定詢問一下後續內容,看看你能做得更好,然後我們到目前爲止所做的更好。樹型迭代器,你可以進一步優化它嗎?
下面的代碼迭代二叉樹(左/右=子/下)。我相信這裏有一個條件較少的空間(down
布爾值)。最快的答案獲勝!
- 的
cnt
語句可以是多條語句所以讓我們確保這個只出現一次 - 的
child()
和next()
成員函數約30倍的hasChild()和hasNext()操作一樣慢。 - 保持迭代< - 由於呈現的遞歸解決方案速度更快,因此放棄了此要求。
- 這是C++代碼
- 節點的訪問順序必須保持原樣,如下例所示。 (首先打擊父母,然後是孩子,然後是'下一個'節點)。
- BaseNodePtr是一個boost :: shared_ptr,因此賦值很慢,避免了任何臨時的BaseNodePtr變量。
目前這段代碼需要5897ms訪問測試樹中的62200000個節點,調用這個函數200,000次。
void processTree (BaseNodePtr current, unsigned int & cnt)
{
bool down = true;
while (true)
{
if (down)
{
while (true) {
cnt++; // this can/will be multiple statesments
if (!current->hasChild()) break;
current = current->child();
}
}
if (current->hasNext())
{
down = true;
current = current->next();
}
else
{
down = false;
current = current->parent();
if (!current)
return; // done.
}
}
}
這是什麼,一個作業問題?爲什麼這種奇怪和任意的限制? – 2009-08-19 20:11:42
這實際上不是家庭作業。沒有任何限制是任意的。我正在嘗試在我的應用程序中構建最快的樹型迭代器函數。這是我到目前爲止所提出的。我想看看它是否可以做得更好。 – Ron 2009-08-19 20:15:13
嗯...也許我可以想出一個更好的,但我不想花費所有的時間試圖在你的限制內解決這個問題。 :-)無論如何,我們可能無法幫助你,因爲你需要根據自己的個人需求來測試這種情況。 – Eli 2009-08-19 20:20:48