srand(time(0)) 和 rand() 导致堆栈溢出错误 [英] srand(time(0)) and rand() are causing a stack overflow error

问题描述

我正在从事一个课堂项目，我必须在其中实现不同的排序算法.其中之一是随机快速排序，但即使在设置了 srand 并设置了要从中选择的数字范围后，我的随机数始终设置为 -8 亿，从而导致堆栈溢出错误.

I'm working on a project for class where I have to implement different sorting algorithms. One of them is a randomized quicksort, but my random number is always set to -800 million even after setting srand and setting a scope of numbers to pick from, causing a stack overflow error.

我已经尝试了我真正能想到的所有方法，但并不多.我尝试在另一个 .cpp 文件中制作一个随机数生成器，它工作正常，但由于某种原因它在这种情况下不起作用.我只是不明白它是如何不能正确生成随机数的.

I've tried everything I can really think of, which isn't much. I tried making a random number generator in another .cpp file and it works fine, it just doesn't work in this context for some reason. I'm just not understanding how it's not properly generating a random number.

void randomizedQuickSort(int arr3[], int start, int end) {
    int temp, pivot;
    int s = start, e = end;
    srand(time(0)); //<------------------------ ERROR THROWN

    // Partitioning
    while (s <= e) {
        pivot = 0 + (rand() % 5);
        while (arr3[s] < pivot)
            s++;
        while (arr3[e] > pivot)
            e--;
        if (s <= e) {
            temp = arr3[s];
            arr3[s] = arr3[e];
            arr3[e] = temp;
            s++;
            e--;
        }

        // Recursion
        if (start < e)
            randomizedQuickSort(arr3, start, e);
        if (s < end)
            randomizedQuickSort(arr3, s, end);
    }
}

我希望数字在 0 到 4 之间，但它每次都会生成 -858,993,460.这是错误和变量值的屏幕截图:

I expect the number to be between 0 and 4, but it generates -858,993,460 every time. Here's a screenshot of the error and variable values:

^{(点击图片放大)}

推荐答案

您最可能遇到的问题是递归调用太深，导致堆栈溢出.此外，您不需要在每次递归调用中都使用 srand().srand() 只是初始化随机数生成器，它通常只完成一次，但不是在每个循环步骤中完成.把它放在 randomizedQuickSort() 之外.只需在程序开始时调用 srand(time(0)); (或当前线程，如果您在单独的线程中执行此操作).

The most possible issue you have is too deep recursive calls, which overflow the stack. Also you don't need that srand() in every recursion call. srand() just initializes random number generator and it usually is done once but not in every loop step. Put it outside of the randomizedQuickSort(). Just call srand(time(0)); in the start of the program (or current thread if you do it in separate thread).

Watch/Autos"Visual Studio 窗口中 pivot 的值为负，因为它在中断程序执行的堆栈溢出时尚未初始化.

You have negative value for pivot in "Watch/Autos" Visual Studio window, because it is not initialized yet at the moment of stack overflow that interrupts program execution.

另外(正如 Stefan 回答的那样)你可以在这里溢出你的数组边界

Also (as Stefan answered) you can overflow your array bounds here

while (arr3[s] < pivot)
    s++;
while (arr3[e] > pivot)
    e--; 

检查s和e是否在start和end的范围内:

Check s and e to be in bounds of start and end:

while (arr3[s] < pivot && s < end - 1)
    s++;
while (arr3[e] > pivot && e > start)
    e--; 

或者为 pivot 分配一个 start 和 end 之间的随机数组元素的值，而不仅仅是某个范围内的随机值.

Or assign pivot a value of a random array element between start and end instead of just random value in some range.

如果您仍然会出现堆栈溢出，请使算法迭代或在您排序的数据数组中放入更少的元素.

If you will still have stack overflow, make algorithm iterative or put less elements in the data array you sort.

这篇关于srand(time(0)) 和 rand() 导致堆栈溢出错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！