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

Question

我想生成1000000个随机数，用快速排序算法排序them.There是两个不同的程序：

// 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;
}

输出：time: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;
}

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

Answer 1

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

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

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

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

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

编辑：

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

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

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

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

（编辑：stable/unstable 算法都受到重复项的影响。感谢@rcgldr）

Answer 2

问题是链接示例中使用的分区方法。它使用类似 Lomuto 的分区方案，而不是 Hoare partition scheme。我使用Visual C / C++ express 2010 release build测试，结果更差，1->10000 0.1秒，1->100 2.7秒

在下面的示例代码中，我使用了 Hoare 分区方案并结合了三的中位数作为数据透视表，并且随着重复数据或有序数据的增加，时间得到了改善。

在我的系统上，Intel 2600K，3.4ghz，使用 Visual C/C++ express 2010 release build，排序 10,000,000 个整数。这种快速排序的变体对于分布 1->10000 花费了 0.531 秒，对于 1->1000 花费了 0.469，对于 1->100 花费了 0.375，对于已经排序的数据花费了 0.109。 clock() 基于 64hz 自动收报机，所以时间 +/- 0.015625 秒。

typedef int int32_t;

void quicksort(int32_t a[], int lo, int hi) {
    int i = lo, j = (lo + hi)/2, k = hi;
    int32_t pivot;
    if (a[k] < a[i])            // median of 3
        std::swap(a[k], a[i]);
    if (a[j] < a[i])
        std::swap(a[j], a[i]);
    if (a[k] < a[j])
        std::swap(a[k], a[j]);
    pivot = a[j];
    while (i <= k) {            // partition
        while (a[i] < pivot)
            i++;
        while (a[k] > pivot)
            k--;
        if (i <= k) {
            std::swap(a[i], a[k]);
            i++;
            k--;
        }
    }
    if (lo < k)                 // recurse
        quicksort(a, lo, k);
    if (i < hi)
        quicksort(a, i, hi);
}

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

Why does using a function to generate random numbers lead to a slower quicksort?

c++

sorting

quicksort