Сегфолт при обработке большого массива[вопрос новичка]

Всем здаравствуйте. Пишу на плюсах. Если не вдаваться в подробности, приложение обрабатывает определенным образом большой двумерный целочисленный массив. Обработка содержит в том числе и рекурсивную функцию. На небольших массивах (примерно 2000х2000 элементов и меньше) все работает адекватно, при попытке же обработать массив большей величины ловлю ошибку сегментирования. Если рекурсию закомментить, ошибка не вылетает (т.е. дело именно в ней). Так как альтернативы рекурсии я пока не придумал, встает вопрос: как быть? Или тут только от рекурсии избавляться?

"MaxSimka⇓" написал:

как быть? Или тут только от рекурсии избавляться?

MaxSimka, сегфолт значит что в программе ошибка... как быть — искать её...

ЗЫ: код в студию...

void Klasters::Rewrite(unsigned int i, unsigned int j) {

if (Matrix[ i ][ j ] < Matrix[ i-1 ][ j ]) {
Matrix[ i-1 ][ j ] = Matrix[ i ][ j ];
Rewrite(i-1,j);
}
if (Matrix[ i ][ j ] < Matrix[ i ][ j-1 ]) {
Matrix[ i ][ j-1 ] = Matrix[ i ][ j ];
Rewrite(i,j-1);
}
if (Matrix[ i ][ j ] < Matrix[ i ][ j+1 ]) {
Matrix[ i ][ j+1 ] = Matrix[ i ][ j ];
Rewrite(i,j+1);
}
if (Matrix[ i ][ j ] < Matrix[ i+1 ][ j ]) {
Matrix[ i+1 ][ j ] = Matrix[ i ][ j ];
Rewrite(i+1,j);
}

}

Вот эта функция и выдает сегфолт. Matrix - целочисленный массив с нулями по границе, внутри все элементы неотрицательны. Запускается рекурсия на одном из неотрицательных элементов. (i,j) - его индекс соответственно.

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

Не знаток Си, но попробую ляпнуть:
есть ли проверка выхода за границы массива?
если совпадут два условия?

"MaxSimka⇓" написал:

Вот эта функция и выдает сегфолт. Matrix - целочисленный массив с нулями по границе, внутри все элементы неотрицательны. Запускается рекурсия на одном из неотрицательных элементов. (i,j) - его индекс соответственно.

какая глубина рекурсии максимальная?
распечатывай на каждом шаге i,j и глубину рекурсии и посмотри, на чём всё слетает...

"MaxSimka⇓" написал:

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

потому что при переполнение стека возникает сегфолт... а какой именно сегфолт процессу не сообщают...

-=Serj=- написал:

Не знаток Си, но попробую ляпнуть:
есть ли проверка выхода за границы массива?

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

MaxSimka, за границы массива у вас элементы действительно не выйдут, а вот глубину рекурсии все же ограничьте. Массив у вас и с ограничнием по глубине перелопатится, а сегфолта(из-за переполнения стека) скорее всего не будет. Уверен что дело именно в этом.

Ограничил глубину рекурсии. Не перелопачивается массив, нужны другие методы =(

Всем спасибо, проблему решил ограничением глубины рекурсии и изменением алгоритма.

MaxSimka, можешь алгоритмом поделиться? Если это не тайна конечно, а то больно интересно стало 8)

да там все банально) главное, что работает быстро и стабильно. сейчас выложу.

Изначально кусок кода, вызывающий рекурсию, выглядел так:

 unsigned int Temp_Count = 1;
    for(unsigned i = 1; i < Height+1; i++)
        for(unsigned j = 1; j < Width+1; j++)
            if (Matrix[ i ][ j ] > 0) {
                if (Matrix[ i-1 ][ j ] == 0 && Matrix[ i ][ j-1 ] == 0)
                    Matrix[ i ][ j ] = Temp_Count++;
                else if (Matrix[ i-1 ][ j ] != 0 && Matrix[ i ][ j-1 ] == 0)
                    Matrix[ i ][ j ] = Matrix[ i-1 ][ j ];
                else if (Matrix[ i-1 ][ j ] == 0 && Matrix[ i ][ j-1 ] != 0)
                    Matrix[ i ][ j ] = Matrix[ i ][ j-1 ];
                else if (Matrix[ i-1 ][ j ] != 0 && Matrix[ i ][ j-1 ] != 0) {
                    Matrix[ i ][ j ] = qMin(Matrix[ i-1 ][ j ], Matrix[ i ][ j-1 ]);
                    Rewrite(i,j);       //Вызов той самой рекурсии
                }
            }
Переделал вот в такой:
    unsigned int Temp_Count = 1;
    bool flag = false;
    for(unsigned i = 1; i < Height+1; i++)
        for(unsigned j = 1; j < Width+1; j++)
            if (Matrix[ i ][ j ] > 0) {
                if (Matrix[ i-1 ][ j ] == 0 && Matrix[ i ][ j-1 ] == 0)
                    Matrix[ i ][ j ] = Temp_Count++;
                else if (Matrix[ i-1 ][ j ] != 0 && Matrix[ i ][ j-1 ] == 0)
                    Matrix[ i ][ j ] = Matrix[ i-1 ][ j ];
                else if (Matrix[ i-1 ][ j ] == 0 && Matrix[ i ][ j-1 ] != 0)
                    Matrix[ i ][ j ] = Matrix[ i ][ j-1 ];
                else if (Matrix[ i-1 ][ j ] != 0 && Matrix[ i ][ j-1 ] != 0) {
                    Matrix[ i ][ j ] = qMin(Matrix[ i-1 ][ j ], Matrix[ i ][ j-1 ]);
                    Recursion_Count = 0;
                    flag = true;
                    Rewrite(i,j);       //Вызов той самой рекурсии
                }
            }
А вот так изменил саму рекурсию:
void Klasters::Rewrite(unsigned int i, unsigned int j) {
    if (Matrix[ i ][ j ] < Matrix[ i-1 ][ j ] && Recursion_Count < 50000) {
        Matrix[ i-1 ][ j ] = Matrix[ i ][ j ];
        Recursion_Count++;
        Rewrite(i-1,j);
    }
    if (Matrix[ i ][ j ] < Matrix[ i ][ j-1 ] && Recursion_Count < 50000) {
        Matrix[ i ][ j-1 ] = Matrix[ i ][ j ];
        Recursion_Count++;
        Rewrite(i,j-1);
    }
    if (Matrix[ i ][ j ] < Matrix[ i ][ j+1 ] && Recursion_Count < 50000) {
        Matrix[ i ][ j+1 ] = Matrix[ i ][ j ];
        Recursion_Count++;
        Rewrite(i,j+1);
    }
    if (Matrix[ i ][ j ] < Matrix[ i+1 ][ j ] && Recursion_Count < 50000) {
        Matrix[ i+1 ][ j ] = Matrix[ i ][ j ];
        Recursion_Count++;
        Rewrite(i+1,j);
    }
}

Хм, красиво) Благодарю за код и алгоритм, действительно интересное решение)

Упс, потерял кусок важного кода!)))

Вот так в итоге выглядит то, что рекурсию вызывает:

unsigned int Temp_Count = 1;
bool flag = false;
for(unsigned i = 1; i < Height+1; i++)
for(unsigned j = 1; j < Width+1; j++)
if (Matrix[ i ][ j ] > 0) {
if (Matrix[ i-1 ][ j ] == 0 && Matrix[ i ][ j-1 ] == 0)
Matrix[ i ][ j ] = Temp_Count++;
else if (Matrix[ i-1 ][ j ] != 0 && Matrix[ i ][ j-1 ] == 0)
Matrix[ i ][ j ] = Matrix[ i-1 ][ j ];
else if (Matrix[ i-1 ][ j ] == 0 && Matrix[ i ][ j-1 ] != 0)
Matrix[ i ][ j ] = Matrix[ i ][ j-1 ];
else if (Matrix[ i-1 ][ j ] != 0 && Matrix[ i ][ j-1 ] != 0) {
Matrix[ i ][ j ] = qMin(Matrix[ i-1 ][ j ], Matrix[ i ][ j-1 ]);
Recursion_Count = 0;
flag = true;
Rewrite(i,j); //Вызов той самой рекурсии
}
}

while (flag) {
flag = false;
for(unsigned i = 1; i < Height+1; i++)
for(unsigned j = 1; j < Width+1; j++)
if (Matrix[ i ][ j ] > 0)
if (Matrix[ i ][ j ] < Matrix[ i-1 ][ j ] || Matrix[ i ][ j ] < Matrix[ i ][ j-1 ] || Matrix[ i ][ j ] < Matrix[ i ][ j+1 ]
|| Matrix[ i ][ j ] < Matrix[ i+1 ][ j ]){
flag = true;
Recursion_Count = 0;
Rewrite(i,j);
}
}