Переполнение стека во время большого цикла: как мне это исправить? - PullRequest
Новая
       11

Переполнение стека во время большого цикла: как мне это исправить?

3 голосов
/ 30 октября 2011

Рассмотрим следующее изображение:

enter image description here

Мое приложение сначала находит все синие пиксели, а также записывает координаты x, y всех своих братьев и сестер (братьев и сестер для данного пикселяэто те, которые граничат с ним: вверх, вниз, влево, вправо, вверху слева, вверху справа и т. д.).Затем он проходит через все эти синие пиксели, чтобы выяснить, сколько у них синих братьев и сестер.В конечном итоге цель состоит в том, чтобы определить, какая группа синих пикселей является самой большой.

Это большой цикл, который в результате выдает ошибку «предупреждение: невозможно восстановить ранее выбранный кадр».Я считаю, что это происходит, потому что я переполняю стек.Если это так, как бы вы посоветовали мне изменить свой код, чтобы исправить эту проблему?

Вот код:

Метод, который запускает цикл: 

for (NSString *key in pixelItemDict) {
    Pixel *px = [pixelItemDict objectForKey:key];
    if (!px.hasBeenCounted) {

        //If it hasn't been counted, we know that we're onto a new distinct area, because otherwise counterForSiblingsOfPixel would have already counted it. So we now add a copy of the pixelsCurrentlyBeingCounted array, empty that array, and reset the counter
        [pixelCounterDict setObject:[pixelsCurrentlyBeingCounted copy] forKey:[NSString stringWithFormat:@"%i",currentPxCounter]];

        [pixelsCurrentlyBeingCounted removeAllObjects];

        [self counterForSiblingsOfPixel:px];

    }
}

Метод, который постоянно вызывает себя, что приводит к переполнению стека: 

- (void)counterForSiblingsOfPixel:(Pixel *)px
{
    [pixelsCurrentlyBeingCounted addObject:px];
    currentPxCounter++;
    px.hasBeenCounted = true;

    for (Pixel *sibling in px.siblings) {
        if (!sibling.hasBeenCounted) [self counterForSiblingsOfPixel:px];
    }
}

По сути, у меня есть pixelItemDict, который содержит все синие пиксели.Я перечисляю этот словарь, вызывая метод counterForSiblingsOfPixel: для каждого из них.Этот метод в свою очередь вызывает себя для каждого из братьев и сестер переданного ему пикселя.Цикл forin восстанавливает управление только после подсчета каждого пикселя в области синего цвета.Поэтому большие синие области приводят к counterForSiblingsOfPixel:, вызывающему себя огромное количество раз, что приводит к переполнению.

Существует ли стандартный шаблон проектирования, который следует использовать в таких случаях, как этот?

1 Ответ

4 голосов
/ 30 октября 2011

Во-первых, вы не изменяете px, поэтому каждый вызов -counterForSiblingsOfPixel: будет делать одно и то же.Когда вы используете рекурсию, вы хотите убедиться, что каждый уровень рекурсии до некоторой степени упрощает проблему.Если рекурсия в конечном итоге не достигнет какого-то базового случая, она будет продолжаться вечно и, да, переполнять стек.Итак, начните с того, что убедитесь, что ваш вызов этого метода для какого-то более простого случая.

Во-вторых, вы, вероятно, не хотите упрощать всего на один пиксель ... Вам будет хорошо, если этот метод делитпикселей на две половины и вызывает себя рекурсивно для каждой половины, потому что в итоге вы получите только уровни рекурсии log2 (пикселей) - около 20 для миллионов пикселей.Но если вы обработаете один пиксель и затем рекурсивно вызовете себя для оставшихся пикселей, вы получите 1000000 уровней рекурсии, которые также будут переполнены.

...