メモリ不足の再帰

Question

私は2GBのRAMを持っています。エクスポート/インポート操作を実行するアプリケーションがあります。 私たちには、Set型の1つのローカル変数を持つ再帰関数があります。このセットは成長し続け、ある時点ではメモリが足りなくなります。

メモリを最適に使用できる代替データ構造はありますか？

は、ここで代替構造はあまり役に立たないラフなコード

GetObjectsForExportImpl(long lExportOptions, __int64 numIdProject, XExportSets 
    &exportSets, long lClientId, CComPtr<IEPIPDServer> ptrIPDServer,FILE *fp) 
{ 
    XExportSets exportLocal; //Thats a structure containing the Set 
    QueryObjectsForExport(lExportOptions, numIdProject, exportLocal, 
     lClientId, ptrIPDServer); 
    SetIDs::iterator it = exportLocal.setShared.begin(); 

    for (; it != exportLocal.setShared.end(); ++it) 
    { 
     //recursive call 
     pExportObject->GetObjectsForExportImpl(lExportOptions, 
      numIdProject, exportSets, lClientId, ptrIPDServer,fp); 
    } 
} 

Answer 1

です。半分のメモリを使用するクラスに切り替えたとします。それでもあなたは運命を遅らせるだけです。

通常、2GBの構造サイズは、ディスクベースの構造、データベース、またはメモリマップハッシュテーブルに切り替える必要があることを示します。

Answer 2

データをすべてではなくまとめて扱います。

です：

while (not end-of-file) { 
    data = read_some_information(); 
    export_some_information(data); 
} 

あなたの再帰が食べている場合、あなたはすべてのデータが（非常に低いです）エクスポートを行うことができるようにする必要があり非常に特殊なケース

Answer 3

でない限り2GBのメモリを使用すると、おそらくあらゆる種類のメモリ内データ構造に問題が生じるでしょう。あなたが行っていることをより良く理解できるように、コードの一部を投稿できますか？

ビルド中にセットを保存するために、データベーステーブルを使用することが考えられます。それぞれの再帰に対して新しいレコードを挿入することができ、そのレコードはテーブルの親レコードへのFK参照を持つことができます。こうすることで、レコード内の親参照に従うことで再帰を上下に移動することができます。あなたのその後の再帰呼び出しに

GetObjectsForExportImpl(
    long     lExportOptions, 
    __int64    numIdProject, 
    XExportSets   &exportSets, 
    long     lClientId, 
    CComPtr<IEPIPDServer> ptrIPDServer, 
    FILE     *fp 
    ) 

：

Answer 4

現時点では、あなたのオリジナルのメソッド呼び出しを比較

hr = pExportObject->GetObjectsForExportImpl(
         lExportOptions, 
         numIdProject, 
         exportSets, 
         lClientId, 
         ptrIPDServer, 
         fp); 

何かの魔法は、それらの間で起こっている場合を除き、あなたは、単にメソッドを再呼び出しされていますそれ自身の議論のセットと一緒に。 exportLocal.setShared.begin（）のポイントは何だったのでしょうか？そうでないと、そこに 'exportSets'の代わりに 'exportLocal'を入れようと思っていましたか？

要するに、問題はコーディングミスであり、再帰の問題ではないと思います。

補助メモ - 再帰ではなくループにする方法はありますか？ループはほぼで、常にであり、より簡単で分かりやすく、簡単にデバッグできます。

Answer 5

申し訳ありません - 私はC++を本当に知っていませんが、少し助けてくれるかもしれません。添字表記を使用して要素にアクセスすることができ、親要素へのポインタがある場合は、スタックを使用して深さを最初に探索し、再帰のコストを無視できます。

Stack<int> childIndex = new Stack<int>(); 
childIndex.Push(0); 

TreeNode<Folder> workingFolder = GetNodeById(folderId); 
TreeNode<Folder> returnFolder = ShallowClone(workingFolder); 

while (childIndex.Count > 0) { 
    int idx = childIndex.Peek(); 
    if (idx < workingFolder.Children.Count) { 
     visit(workingFolder.Children[idx]); 

     // increment count for this level 
     childIndex.Pop(); 
     childIndex.Push(idx + 1); 

     // replace current working folders and push new index 
     workingFolder = workingFolder.Children[idx]; 
     returnFolder = f; 
     childIndex.Push(0); 
    } else { 
     // no (more) children 
     workingFolder = (workingFolder.Parent == null ? workingFolder : workingFolder.Parent); 
     returnFolder = (returnFolder.Parent == null ? returnFolder : returnFolder.Parent); 
     childIndex.Pop(); 
    } 
} 

Answer 6

私は再帰があなたの問題と関係がありませんと思います。問題は、単に作成しているデータが大きいことです。反復的な解決策への移行はそれを助けません。すでに指摘したように、メモリ内の構造体に格納するのではなく、トラバースしながら出力を書き出します。

ただし、構造体全体ではなく、再帰呼び出しでポインタを渡すことで、スタック上の内容を最小限に抑えることができます。