どのようにSystem.OutOfMemoryExceptionを回避するには、非再結合三項木を構築するとき

Question

特定の固定所得派生物を価格設定するために、非再結合三項木を「正常に」実装しました。 （下の図のようなものですが、再接続しない3つのブランチがあります）残念ながら、私が使用できるノードの数は、利用可能なメモリによって大きく制限されていました。私は20時間ステップでツリーを構築する場合、これは3^19個のノード（SO 1,1億ノード）

各時間ステップのノードをList<Node>に保存され、これらの配列はDictionary<double,List<Node>>

に格納されることになります

各ノードはnew Node(...)によってインスタンス化されます。また、リストと辞書のそれぞれをnew Class()でインスタンス化します。おそらく、これが私のエラーの原因です。

また、Dictionary/List-Objectが大きい（よくあることですが）ため、投げられませんが、あまりにも多くのノードを持っているように見えるため、しばらく後にnew Node(...)はそれ以上のメモリを割り当てることができません。最終的に2GBの最大リスト・キャパシティもまた、私はリストが各時間ステップで指数関数的に大きくなっていく様子を見ています。

私のデータ構造はあまりにも無駄であるか、または手元の仕事にはあまり適していないかもしれません。

可能な解決策は、ツリーをテキストファイルに保存してメモリ問題を完全に回避することです。しかし、これは大きな回避策を必要とします。

編集： さらに背景を追加します。パス依存の製品を価格するにはツリーが必要です。残念ながら、私はすべてのノードにアクセスする必要があります。木が築かれた後には何があるのですか？私は葉から始まり、価格を決定するために時を経て後退します。私はすでに必要なノードだけを生成しています。

Edit2： 私はトピックをいくつか与えましたが、さまざまな反応も考慮しました。それぞれのツリーレベルをハードドライブにシリアル化するだけでよいのでしょうか。だから基本的に - 私は1つのタイムステップ（List<Node>）を作成してディスクなどに書き込みます。その後、葉から始めて - それを逆方向にロードするだけです。

Answer 1

私たちがここに持っているのは、膨大な量の処理をフロントで行い、後で処理するためにすべてのデータをメモリに保存するという古典的な問題です。

シンプルですが、十分に厳しい条件（10億のエントリを持つようなもの）を指定すると、すべてのメモリが消費されます。

今、OPはツリーの意図や使い方を実際には指定していませんでしたが、すべてを一度に構築するのではなく、それが必要。

yield

代わりのすべてを一度にすべてをやって、それを保存することで遅延評価...あなたが実際にそれを必要とする場合にのみ、それを行うことが理想的であるかもしれません。 yieldの詳細と使用例については、postをご覧ください。

これは時間の束をtravereseする必要がある場合、これは素晴らしいことはありません...それでもあなたが現在行っているより深い深みを持つことができます。

Answer 2

基本的に2つの選択肢があります。あなたが気にしているブランチ（Andrewの歩留まり）だけを評価し、結果を保存しないでください。またはあなたのツリーを構築してディスクに保存し、ディスクの右部分にアクセスするカスタムコレクションインターフェイスを実装します。この場合でも、プロセスメモリに最小限のデータを保存し、OSを使用してディスクキャッシュを適切に行い、アクセスを高速化します。大規模なデータセットで作業を開始する場合、2番目のオプションはツールベルトに入れるのに適したツールなので、再利用することを念頭に置いて作成してください。

Answer 3

ディスクにシリアライズすると多少なりとも役立つと思います。 1つは、リストを逆シリアル化しようとするとメモリが不足します（私の知る限り、オブジェクトを部分的に逆シリアル化する方法はありません）。

データ構造をリレーショナルデータベースモデルに変更し、SQLEXPRESSデータベースに格納することを検討しましたか？

これは、カスタムツリートラバーサルロジックの代わりにインデックスを使用してクエリを実行するという追加の利点を提供します。