如何在構建非重組三叉樹時在c＃中避免System.OutOfMemoryException

我已「成功」實現了非重組三叉樹以對某些固定收益衍生品進行定價。（如下圖所示 - 但有三個分支不能重新連接） this picture 如何在構建非重組三叉樹時在c＃中避免System.OutOfMemoryException

不幸的是，事實證明，我可以使用的節點數量受到可用內存的嚴重限制。如果我建立一個樹20個時間步長，這導致3^19個節點（1,1所以十億節點）

每個時間步長的節點都保存在List<Node>和這些陣列被存儲在Dictionary<double,List<Node>>

每個節點都通過new Node(...)實例化。我也通過new Class()實例化每個列表和字典，也許這是我錯誤的根源。

另外System.OutOfMemoryException由於字典/列表對象大（通常是這樣），但因爲我似乎有太多的節點 - 過了一段時間new Node(...)不能分配任何進一步的內存。最終2GB的最大列表容量也會啓動，我認爲 - 看看List如何隨着每個時間步驟以指數級增長。

也許我的數據結構太浪費了，或者不太適合手頭的任務。

一個可能的解決方案可能是將樹保存到文本文件，從而完全避免內存問題。然而，這將需要一個巨大的解決方法。

編輯： 添加一些更多的背景。我需要樹來定價路徑相關產品。這意味着不幸的是我將不得不訪問所有的節點。還有什麼更多的樹已經建成後，我從樹葉開始，並及時倒退，以確定價格。我也已經只生成了我需要的節點。

編輯2： 我已經給了一些主題，但也考慮了各種迴應。難道是我只需要將相應的樹級別序列化到硬盤驅動器。所以基本上 - 我創建一個時間步（List<Node>）將其寫入磁盤等。稍後當我從樹葉開始 - 我將只需要加載它在反向或向下。

來源

2014-01-09 Andrey Lujankin

這是運行在x64上嗎？ – Andrew

我的電腦在工作時的系統屏幕顯示64位 –

@AndreyLujankin您是否將程序編譯爲64位應用程序以利用此程序，或者將您編譯爲32位應用程序？ – Servy

我們這裏有一個經典的問題，先做大量的處理......然後將所有東西存儲到內存中，以備以後處理。

雖然很簡單，但在條件苛刻的情況下（如擁有十億個條目），它會吃掉所有的內存。

現在，OP沒有明確說明樹的意圖是什麼以及它將如何使用......但是我會建議不要一次構建它......建立它作爲你需要它。

懶惰的評價與yield

而是一下子做的一切，不必存儲它......它可能是理想的做它，只有當你真正需要它。查看post以獲取更多信息和使用yield的示例。

雖然如果您需要將樹經歷一段時間，那麼這樣做不會很好。但它仍然可以讓你比現在做得更深入。

來源

2014-01-09 19:27:28 Andrew

你基本上有兩種選擇。只評估你關心的分支（安德魯的產量）並且不要存儲結果或建立你的樹並保存到磁盤並在其上實現一個自定義的集合接口來訪問磁盤的右側部分。在這種情況下，您仍然要在進程內存中保留最少量的數據，並依靠操作系統進行適當的磁盤緩存，以便快速訪問。如果您開始使用大型數據集，則第二個選項是您的工具帶中的一個好工具，因此您應該在考慮到重複使用的情況下編寫這個工具。

來源

2014-01-09 19:36:52 Yaur

請注意，在更高版本的.NET中有一些不錯的[緩存類內置]（http://msdn.microsoft.com/en-us/library/system.runtime.caching.memorycache%28v= vs.110％29.aspx）。因此，您可以將整個對象保存到磁盤，但儘可能多地保持緩存在內存中，並且當您有一個緩存未命中時，您將轉到磁盤重新讀取數據。 –

@ScottChamberlain你提到的那些緩存類看起來很有趣。我從未與某事合作過。就像那個befor :) –

另一個想法 - 據我所知，cach恰好在CPU而不是磁盤或我混淆的東西？ –

我不認爲序列化到磁盤將有很大幫助。其一，當你嘗試反序列化列表時，你仍然會耗盡內存（就我所知，沒有辦法部分反序列化一個對象）。

您是否考慮過將數據結構轉換爲關係數據庫模型並將其存儲在SQLEXPRESS數據庫中？

這會爲您提供使用索引執行查詢而非自定義樹遍歷邏輯的額外好處。

來源

2014-01-10 13:51:34

是的，我考慮過了。不幸的是，我不知道如果我想讓代碼作爲Excel-Xll（通過Excel-DNA）可用，數據庫的使用是否可行， –

如何在構建非重組三叉樹時在c＃中避免System.OutOfMemoryException

回答

相關問題