此功能

我的代碼如下避免遞歸，此功能

myParent = curreObj->getmyParent(); 
if(myParent != NULL && myParent->getAttrib() != "abc") 
    myParent=myParent->getmyParent(); 
return myParent;

重要提示：屬性「ABC」可以被許多人持有。這不是一個1-1的財產。所以，維護一張地圖可能是不可能的。而且我希望在我的血統中。所以，如果我維護一個multimap，從屬性我會有一個對象的列表，我將不得不循環到我的對象，這將使它成爲一個O（n）操作。我試圖讓它比O（n）小，理想情況下爲O（1），如果不是O（log n）至少。有解決方案嗎？

我想我的祖先有屬性等於某個值。如果不是，則返回NULL。

我使用Visual Studio 2013，C++。

上面的代碼做的，但我想這樣做的更好，至少可以避免遞歸。

有沒有辦法做到這一點？有沒有我可以用來完成這個數據結構？

來源

2017-02-04 s_s

'此功能'/'我的代碼看起來'代碼實現_什麼？（把'最近的]祖先[滿足一些謂詞]'放在更突出的位置：標題，第一句，一個/這個過程的名稱。）'避免遞歸'在我的書中，_recursion_直接或間接讀取_directly或間接更多的same_：我沒有看到你的問題。（什麼是'血統'？） – greybeard

你可以存儲指向你的對象的父級，然後做到這一點： -

myParent = curreObj->parent; 
while(myParent != NULL && myParent->getAttrib() != "abc") 
    myParent=myParent->parent;

來源

2017-02-04 06:35:42

這節省了遞歸，但仍然是O（n）。也許我想去O（1）？那可能嗎？ –

不，你必須循環所有父母來檢查條件。 –

爲O（n），除非你做了前處理和保存一些數據結構中的所有信息是不可能的。

另外我假設在O（n）的n個指curreObj和其最遠祖先之間的長度。如果n是「curreObj」的所有節點的數量，並且您正在使用二叉樹來保存關係，那麼您應該已經達到了O（log n）。

如果你仍然想通過在預處理步驟中保存一些額外的數據來提高效率，我建議你在散列圖中有一個嵌入的散列圖，因此對於每個鍵，可能存在散列表存儲爲該值和在此散列映射中，對象引用的散列將是鍵，而對象本身將是該值。

我還沒有C++工作多年，所以請原諒我的錯誤的語法，這僅僅是僞代碼。

HashMap<string, HashMap<string, Object>> map; 

// it should be the value you specify 
HashMap<string, Object> embeddedMap = map.get("abc"); 
embeddedMap.get(curreObj.hash())

爲製作這份地圖，你需要遍歷所有節點，並保存這些屬性和相應的「家長」，它應該是這樣的，

HashMap<string, HashMap<string, Object>> map; 

myParent = curreObj->getmyParent(); 
if(myParent != NULL && myParent->getAttrib() != null){ 
    HashMap<string, Object> embeddedMap; 
    embeddedMap.put(curreObj.hash(),myParent); 
    map.put(myParent->getAttrib(), embeddedMap); 
}

這樣，您可以檢索O（1）中的值，但您必須將所有額外信息保存在O（n2）中。

希望我正確地理解你的問題，這可以給你一些啓示。

來源

2017-02-04 08:22:10 Simon

回答

相關問題