c++ - 为什么使用函数生成随机数会导致快速排序变慢？

Question

我想生成1000000个随机数，并使用快速排序算法对它们进行排序。有两种不同的程序:

// Program 1
void quicksort()
{
   // ...
}

int main()
{
    int *arr = new int[1000000];

    // generate random number in main()
    std::default_random_engine e(100);
    std::uniform_int_distribution<unsigned> u(1,10000);
    for(int i = 0;i < 999999;++i)
       arr[i] = u(e);

    clock_t start = clock();
    quicksort(arr,0,999999);
    clock_t end = clock();
    cout<<"time:"<<static_cast<float>(end-start)/CLOCKS_PER_SEC<<endl;
    delete [] arr;
    return 0;
}

输出:时间:0.361684

// Program 2
void quicksort()
{
       // ...
}

void generateRandom(int *arr,int size,int seed)
{
   std::uniform_int_distribution<unsigned> u(0,1000);
   std::default_random_engine e(seed);
   for(int i = 0; i < size; ++i)
       arr[i] = u(e);
}

int main()
{
        int *arr = new int[1000000];

        generateRandom(arr,1000000,100);  // The only different between Program1 and Program2

        clock_t start = clock();
        quicksort(arr,0,999999);
        clock_t end = clock();
        cout<<"time:"<<static_cast<float>(end-start)/CLOCKS_PER_SEC<<endl;
        delete [] arr;
        return 0;
}

输出:时间:1.88307
为什么使用generateRandom()生成随机数会导致快速排序变慢？ Here是完整的程序。
感谢您的帮助。

Answer 1

您只记录对快速排序的调用，这会将时间差隔离到仅对已生成的数字进行排序的工作。

快速排序的运行时间根据其输入而变化。在最坏的情况下，快速排序的运行时间为 O(n**2)。 O(n log n) 平均。例如，如果快速排序实现选择第一个可用元素作为主元，那么最坏的情况是给它一个已经排序的数组，因为需要更多交换。

你在时间上的差异是因为你的输入不同，而不是因为你是在函数中生成数字而不是内联。您的生成器在两个程序中使用相同的种子，但您使用的是 (1,1000) 与 (1,10000) 不同的分布——这将导致一组完全不同的整数。

均匀分布中较小的分布会减少数组中的熵(例如，会有更多重复值)，这会影响为使数组完全排序而必须执行的交换次数。数组中的初始相对顺序将影响整数必须围绕所选枢轴移动的次数。

在这两种情况下，您生成的数字在内存中的布局是相同的(一个线性数组)，并且程序的占用空间足够小，我们可以安全地排除代码缓存未命中导致快速排序调用内部运行时间不同的可能性。您的总运行时间将受到您正在进行的内存比较和交换次数的影响(以及您发生的少数缓存未命中——您有 4MiB 的数字要排序，并不多)。我假设两个 quicksort() 中的代码是相同的。

编辑:

为了说明问题，你可以修改你的程序如下:

for(int i = 0;i < 999999;++i)
  arr[i] = i; //u(e);

完全放弃随机生成。这会使您的快速排序算法在已经排序的数组上运行——这是最坏的情况。

在我的系统上，尝试运行几次在函数内部生成数字的版本会在 1 到 2 秒内完成(如外部代码链接中所示)，而使用排序版本会在更长的时间内完成多少时间。仅对已排序的数字数组从 0 到 100000(而不是一百万)进行排序就需要超过 15 秒。

(编辑:稳定/不稳定算法都受到重复的影响。感谢@rcgldr)