Рекурсия, ведущая к нехватке памяти

Question

ОЗУ у меня 2 ГБ. У нас есть приложение, которое выполняет операции экспорта / импорта. У нас есть рекурсивная функция, которая имеет одну локальную переменную типа Set, которая продолжает заполняться при каждой итерации. Этот набор продолжает расти, и в какой-то момент у нас заканчивается память.

Есть ли альтернативная структура данных, которая может оптимально использовать память?

Вот примерный код

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

Альтернативная структура не очень поможет. Скажем, вы переключились на класс, который использует половину памяти. Тем не менее, вы только откладываете гибель.

Размер структуры 2 ГБ обычно означает, что вам необходимо переключиться на структуру на основе диска, базу данных или хэш-таблицу с отображением в памяти.

Answer 2

Извините - я действительно не знаю C ++, но могу немного помочь. Если вы можете использовать индексную нотацию для доступа к элементам, и у вас есть указатели на родительские элементы, вы можете использовать стек для первого глубокого обхода и избежать значительных затрат рекурсии. Вот код 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 3

На мгновение сравните исходный вызов метода:

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

на ваш последующий рекурсивный вызов:

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

Если между ними не происходит волшебства, вы просто повторно вызываете метод с его собственным набором аргументов. Я подозреваю, что вы хотели поместить туда «exportLocal» вместо «exportSets», потому что в противном случае какой был смысл exportLocal.setShared.begin ()? Вы просто продолжите воссоздание нового exportLocal, сообщив ему о начале, повторении и т. Д.

Короче говоря, я думаю, что проблема в ошибке кодирования, а не в рекурсии.

В качестве дополнительного примечания - можете ли вы придумать способ сделать это циклом, а не рекурсией? Циклы почти всегда быстрее, проще, проще для понимания и быстрой отладки.

Answer 4

Обрабатывайте данные по частям, а не по всем сразу.

То есть:

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

Если вы не находитесь в очень конкретном случае, когда вам нужны все данные, чтобы иметь возможность выполнить экспорт (что весьма маловероятно)

Answer 5

Я не думаю, что рекурсия имеет непосредственное отношение к вашей проблеме. Проблема только в том, что данные, которые вы создаете, большие. Переход к итеративному решению не поможет с этим. Как уже указывалось, записывайте вывод по мере прохождения, а не сохраняйте его в структуре в памяти.

Однако вы можете минимизировать то, что происходит в стеке, передавая указатели в ваших рекурсивных вызовах, а не целые структуры.

Answer 6

Если ваша рекурсия потребляет 2 ГБ памяти, у вас, вероятно, возникнут проблемы с любым типом структуры данных в памяти. Можете ли вы опубликовать часть своего кода, чтобы мы могли лучше понять, что вы делаете?

Одной из идей может быть использование таблицы базы данных для хранения набора при его создании. Вы можете вставить новую запись для каждой рекурсии, и запись может иметь ссылку FK на родительскую запись в таблице. Таким образом, вы можете идти вверх и вниз по рекурсии, следуя родительским ссылкам в записях.