我有一个获取索引值的函数,将它放在一个数组中。然后使用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。
据我所知,当您将最后一个空闲索引插入数组时,代码将生成无限循环。
假使,假设:
1)im->height
为500,因此有效指数在[0 .. 499]范围内
2)您已经插入了499个值,即*visitedPixelsIndex
是499
因此,当调用该函数时,此条件*visitedPixelsIndex == im->height
将为false,因此您不会退出但继续执行并在数组中插入值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;
}