C пытается исправить бесконечный цикл

Question

У меня есть функция, которая получает значение индекса, помещает его в массив.Затем генерирует новый новый случайный индекс, используя rand + srand ( key ).И он проверяет, находится ли недавно сгенерированный индекс в массиве, он будет продолжать генерировать новый индекс и проверять, пока не будет сгенерировано уникальное значение.

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

int getNewIndex(PPM *im, int index, int *visitedPixels, int *visitedPixelsIndex) {

    int i = 0;
    if(*visitedPixelsIndex == im->height) {
        perror("Cannot encode anymore: pixels limit reached");
        exit(1);
    }

    visitedPixels[*visitedPixelsIndex] = index;
    (*visitedPixelsIndex)++;
    // If index is already in the list, generate a new number and check again.
    while (i < *visitedPixelsIndex) {
        if(index == visitedPixels[i]) {
            index = rand() % im->height;
            i = 0;
        } else {
            i++;
        }
    }

    return index;
}

РЕДАКТИРОВАТЬ: im->height, то есть высота изображения в среднем составляет около 400-600.

Answer 1

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

Предположим, что:

1) im->height равно 500, поэтомуэтот действительный индекс находится в диапазоне [0 .. 499]

2) Вы уже вставили 499 значений, т.е. *visitedPixelsIndex равно 499

Так, когда функция вызывается, это условие *visitedPixelsIndex == im->height будет ложным, поэтому вы не выйдете, а продолжите работу и вставите в массив значение 500.

Затем вы делаете (*visitedPixelsIndex)++;, так что *visitedPixelsIndex становится 500.

Послечто вы входите в цикл while, пытаясь найти новый неиспользованный index.Однако, поскольку вы уже использовали все 500 допустимых значений индекса, вы никогда не найдете неиспользуемый индекс.

Другими словами - бесконечный цикл

Может быть, вы должны сделать:

(*visitedPixelsIndex)++;
if(*visitedPixelsIndex == im->height) {
    perror("Cannot encode anymore: pixels limit reached");
    exit(1);
}

Я также думаю, что вы должны сгенерировать новый index до цикл while.

Однако в целом я думаю, что ваш код будет более понятным, если вы разделите текущую функцию на две функции.Как

int isPresent(int index, int *visitedPixels, int N) 
{
    for(int i = 0; i<N; ++i)
    {
        if (index == visitedPixels[i]) return 1;
    }
    return 0;
}

int getNewIndex(PPM *im, int index, int *visitedPixels, int *visitedPixelsIndex) 
{
    visitedPixels[*visitedPixelsIndex] = index;

    (*visitedPixelsIndex)++;

    if (*visitedPixelsIndex == im->height) {
        perror("Cannot encode anymore: pixels limit reached");
        exit(1);
    }

    do
    {
        index = rand() % im->height;
    } while(isPresent(index, visitedPixels, *visitedPixelsIndex));

    return index;
}