在非常深的樹上刪除

我正在爲10個字符集建立後綴trie（不幸的是，沒有時間正確實現後綴樹）。我想分析的字符串將會相當長（最多1M字符）。這棵樹的構造沒有任何問題，但是當我嘗試釋放內存後，我遇到了一些問題。在非常深的樹上刪除

在具體地，如果設置我構造和析構是這樣（其中CNode.child是指向的10個指向其他CNodes陣列，並且計數是一個簡單的無符號整數）：

CNode::CNode(){ 
    count = 0; 
    child = new CNode* [10]; 
    memset(child, 0, sizeof(CNode*) * 10); 
} 

CNode::~CNode(){ 
    for (int i=0; i<10; i++) 
     delete child[i]; 
}

嘗試刪除根節點時出現堆棧溢出。我可能是錯的，但我相當肯定這是由於過多的析構函數調用（每個析構函數調用最多10個其他析構函數）。我知道這在空間和時間方面都不是最理想的，但是，這應該是對於重複的子串問題的一種快速和骯髒的解決方案。

tl; dr：如何解放一棵很深的樹佔用的內存？

謝謝你的時間。

來源

2010-06-13 nikaspran

如果你可以使用一個調試器獲得堆棧跟蹤，你可以告訴它是否真的是你的析構函數導致堆棧溢出。 – strager 2010-06-13 14:42:32

只需更改節點指針即可將樹轉換爲線性列表，然後只需從頭至尾刪除即可。 – 2010-06-13 14:44:10

'child = new CNode * [10]（）'將創建一個最初設置爲null的10個指針的數組。不需要任何'memset'。 – AnT 2010-06-13 15:02:01

你是否爲節點本身初始化內存？從我所看到的，你的代碼只爲指針分配內存，而不是實際的節點。

至於你的問題，嘗試以迭代的方式遍歷樹，而不是遞歸。遞歸是不好的，只有當它在紙上，而不是在代碼中，這很好。

來源

2010-06-13 14:43:32 iksemyonov

遞歸不壞... = [ – strager 2010-06-13 14:45:14

雖然在不同的地方，這裏似乎並不相關。我可能會嘗試這種方法，但我希望有一個更優雅的解決方案:) – nikaspran 2010-06-13 14:45:31

@Kathoz：真的這是最簡單的方法。實際上，遞歸實現總是受堆棧大小的限制，因此您可能會很容易遇到遞歸方法的問題。 – iksemyonov 2010-06-13 14:49:04

您是否考慮過增加堆棧大小？

在Visual Studio中，您可以使用/ FNUMBER來實現，其中NUMBER是以字節爲單位的堆棧大小。您可能還需要指定/ STACK：reserve [，commit]。

來源

2010-06-13 14:46:45 George

OP表示數據集可能會達到100萬...現代系統上至少有4MB的堆棧。添加到參數，臨時等，你會有一個非常大的堆棧。 – strager 2010-06-13 14:54:40

@strager：你說如果4兆字節是很多。在嵌入式系統當然可以，但如果你正在談論一個現代的Windows或Linux桌面或服務器系統，4兆字節比花生少。一個8或16 MB的堆棧是沒有問題的。 – George 2010-06-13 15:00:06

我們使用一個8MB的堆棧PER線程（18），我工作的地方...服務器程序確實與嵌入式不同：D – 2010-06-13 16:16:12

一個選擇是從一個大緩衝區分配然後一次釋放該緩衝區。

例如（未經測試）：

class CNodeBuffer { 
    private: 
     std::vector<CNode *> nodes; 

    public: 
     ~CNodeBuffer() { 
      empty(); 
     } 

     CNode *get(...) { 
      CNode *node = new CNode(...); 
      nodes.push_back(node); 
      return node; 
     } 

     void empty() { 
      for(std::vector<CNode *>::iterator *i = nodes.begin(); i != nodes.end(); ++i) { 
       delete *i; 
      } 

      nodes = std::vector<CNode *>(); 
     } 
};

如果指針到std::vector的元素是穩定的，可以使事情有點simplier和只使用一個std::vector<CNode>。這需要測試。

來源

2010-06-13 14:50:08 strager

指向向量的指針不穩定。可以使用向量的索引。我通常實現上面例舉的內容，並使用索引而不是指針（可能可以在它們周圍實現自定義迭代器？）。雖然當需要保留免費節點列表以支持put（）（或delete（））操作時，它通常會變得更加混亂。 – Dummy00001 2010-06-13 17:47:28

@ Dummy00001，「put」或單個刪除基本上是noop，或者結構可以重用（例如，調用ctor）。我認爲我之前已經看到過這種模式（更普遍），但我忘記了它的名字。自定義迭代器聽起來像個好主意，但對於需要的東西感覺有點沉重。 – strager 2010-06-13 20:54:26

你會做很多刪除操作。這會花費很多時間，因爲你會以非常隨意的方式訪問內存。但是，那時你不再需要樹形結構。因此，我會做兩遍。在第一遍中，爲您的樹中的所有節點創建一個std::vector<CNode*>和reserve()足夠的空間。現在遞歸樹並將所有CNode *複製到您的向量中。在第二步中，對它們進行排序（！）。然後，在第三步中，刪除所有這些。第二步在技術上是可選的，但可能使第三步快得多。如果不是，請嘗試按相反順序排序。

來源

2010-06-14 11:54:55 MSalters

我認爲在這種情況下，通過將所有後向跟蹤信息放入deque而非OS提供的堆棧中，可以對寬度優先的清理有所幫助。它仍然不會愉快地解決它在析構函數中發生的問題。

僞代碼：

void CNode::cleanup() 
{ 
    std::deque<CNode*> nodes; 
    nodes.push_back(this); 
    while(!nodes.empty()) 
    { 
     // Get and remove front node from deque. 
     // From that node, put all non-null children at end of deque. 
     // Delete front node. 
    } 
}

來源

2010-06-14 13:45:28

在非常深的樹上刪除

回答

相關問題