为什么我的n日志（n）堆排序比我的n^2选择排序慢

Question

我已经实现了两种从最高到最低排序元素的算法。

第一种方法在真实RAM模型上采用二次时间，第二种方法采用O（n log（n））时间。第二种方法使用优先级队列来获得缩减。

这里是计时，这是上述程序的输出。

>

 9600  1.92663      7.58865
 9800  1.93705      7.67376
10000  2.08647      8.19094

尽管在复杂度上存在巨大差异，但就所考虑的数组大小而言，第三列要比第二列大。为什么会这样？C的优先级队列实现慢吗？

我在Windows7上执行了这段代码，VisualStudio2012是32位的。

这是代码，

#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <Windows.h>
#include <assert.h>

using namespace std;

double time_slower_sort(vector<int>& a) 
{
    LARGE_INTEGER frequency, start,end;
    if (::QueryPerformanceFrequency(&frequency) == FALSE  ) exit(0);
    if (::QueryPerformanceCounter(&start)       == FALSE  ) exit(0);

    for(size_t i=0 ; i < a.size() ; ++i)  
    {

        vector<int>::iterator it = max_element( a.begin() + i ,a.end() ) ;
        int max_value = *it; 
        *it = a[i];
        a[i] = max_value;    

    }
    if (::QueryPerformanceCounter(&end) == FALSE) exit(0);
    return static_cast<double>(end.QuadPart - start.QuadPart) / frequency.QuadPart;
}



double time_faster_sort(vector<int>& a) 
{
    LARGE_INTEGER frequency, start,end;
    if (::QueryPerformanceFrequency(&frequency) == FALSE  ) exit(0);
    if (::QueryPerformanceCounter(&start)       == FALSE  ) exit(0);


    // Push into the priority queue. Logarithmic cost per insertion = > O (n log(n)) total insertion cost
    priority_queue<int> pq;
    for(size_t i=0 ; i<a.size() ; ++i)
    {
        pq.push(a[i]);
    }

    // Read of the elements from the priority queue in order of priority
    // logarithmic reading cost per read => O(n log(n)) reading cost for entire vector
    for(size_t i=0 ; i<a.size() ; ++i)
    {
        a[i] = pq.top();
        pq.pop();
    }
    if (::QueryPerformanceCounter(&end) == FALSE) exit(0);
    return static_cast<double>(end.QuadPart - start.QuadPart) / frequency.QuadPart;

}




int main(int argc, char** argv)
{
    // Iterate over vectors of different sizes and try out the two different variants
    for(size_t N=1000; N<=10000 ; N += 100 ) 
    {

        // initialize two vectors with identical random elements
        vector<int> a(N),b(N);

        // initialize with random elements
        for(size_t i=0 ; i<N ; ++i) 
        {
            a[i] = rand() % 1000; 
            b[i] = a[i];
        }

        // Sort the two different variants and time them  
        cout << N << "  " 
             << time_slower_sort(a) << "\t\t" 
             << time_faster_sort(b) << endl;

        // Sanity check
        for(size_t i=0 ; i<=N-2 ; ++i) 
        {
            assert(a[i] == b[i]); // both should return the same answer
            assert(a[i] >= a[i+1]); // else not sorted
        }

    }
    return 0;
}

Answer 1

O（N^2）算法的运行速度是O（N log N）算法的4倍。或者至少你认为你知道。

显而易见的是验证你的假设。从尺寸9600、9800和10000中，你可以得出的结论不多。试试尺寸1000, 2000, 4000, 8000, 16000, 32000。第一个算法是否按其应有的方式每次将时间增加4倍？第二种算法是否会按照它应该的那样，每次将时间增加一个略大于2的因子？

如果是，那么O（N^2）和O（N logn）看起来是正确的，但是第二个有大量的常数因子。如果没有，那么您对执行速度的假设是错误的，您将开始调查原因。在N=10000时，O（N logn）比O（N*N）长4倍是非常不寻常的，看起来非常可疑。

Answer 2

我认为这个问题确实比人们想象的更微妙。在O（N^2）解决方案中，您没有进行分配，算法在适当的位置工作，搜索最大值并与当前位置交换。这没关系。

但是在priority_队列version O（N log N）（内部的priority_队列默认有一个std:：vector来存储状态）。当你一个元素一个元素地向后推时，这个向量有时需要增长（确实如此），但这一次你在O（N^2）版本中没有损失。如果您在优先级队列的初始化过程中做了以下小更改：

优先级队列

O（N log N）的时间比O（N^2）的时间快很多。在提议的更改中，仍然存在priority_queue版本中的分配，但只有一次（您为大向量大小节省了大量分配，并且分配是重要的耗时操作之一）初始化（在O（N）中可以利用priority_queue的完整状态，不知道STL是否真的这样做）。

示例代码（用于编译和运行）：

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <Windows.h>
#include <assert.h>

using namespace std;

double time_slower_sort(vector<int>& a) {
    LARGE_INTEGER frequency, start, end;
    if (::QueryPerformanceFrequency(&frequency) == FALSE)
        exit(0);
    if (::QueryPerformanceCounter(&start) == FALSE)
        exit(0);

    for (size_t i = 0; i < a.size(); ++i) {

        vector<int>::iterator it = max_element(a.begin() + i, a.end());
        int max_value = *it;
        *it = a[i];
        a[i] = max_value;
    }
    if (::QueryPerformanceCounter(&end) == FALSE)
        exit(0);
    return static_cast<double>(end.QuadPart - start.QuadPart) /
           frequency.QuadPart;
}

double time_faster_sort(vector<int>& a) {
    LARGE_INTEGER frequency, start, end;
    if (::QueryPerformanceFrequency(&frequency) == FALSE)
        exit(0);
    if (::QueryPerformanceCounter(&start) == FALSE)
        exit(0);

    // Push into the priority queue. Logarithmic cost per insertion = > O (n
    // log(n)) total insertion cost
    priority_queue<int> pq(a.begin(), a.end());  // <----- THE ONLY CHANGE IS HERE

    // Read of the elements from the priority queue in order of priority
    // logarithmic reading cost per read => O(n log(n)) reading cost for entire
    // vector
    for (size_t i = 0; i < a.size(); ++i) {
        a[i] = pq.top();
        pq.pop();
    }
    if (::QueryPerformanceCounter(&end) == FALSE)
        exit(0);
    return static_cast<double>(end.QuadPart - start.QuadPart) /
           frequency.QuadPart;
}

int main(int argc, char** argv) {
    // Iterate over vectors of different sizes and try out the two different
    // variants
    for (size_t N = 1000; N <= 10000; N += 100) {

        // initialize two vectors with identical random elements
        vector<int> a(N), b(N);

        // initialize with random elements
        for (size_t i = 0; i < N; ++i) {
            a[i] = rand() % 1000;
            b[i] = a[i];
        }

        // Sort the two different variants and time them
        cout << N << "  " << time_slower_sort(a) << "\t\t"
             << time_faster_sort(b) << endl;

        // Sanity check
        for (size_t i = 0; i <= N - 2; ++i) {
            assert(a[i] == b[i]);     // both should return the same answer
            assert(a[i] >= a[i + 1]); // else not sorted
        }
    }
    return 0;
}

在我的PC（Core 2 Duo 6300）中获得的输出是：

1100  0.000753738      0.000110263
1200  0.000883201      0.000115749
1300  0.00103077       0.000124526
1400  0.00126994       0.000250698
...
9500  0.0497966        0.00114377
9600  0.051173         0.00123429
9700  0.052551         0.00115804
9800  0.0533245        0.00117614
9900  0.0555007        0.00119205
10000 0.0552341        0.00120466

Answer 3

对于所考虑的阵列大小，第三列大于第二列。

“大O”符号只告诉您时间是如何随输入大小而增长的。

你的时代是（或者应该是）

A + B*N^2          for the quadratic case,
C + D*N*LOG(N)     for the linearithmic case.

但完全有可能C比A大得多，当N足够小时，导致线性算术代码的执行时间更长。

线性算法的有趣之处在于，如果您的输入从9600增长到19200（翻倍），那么对于二次算法，您的执行时间应该大约是四倍，约为八秒，而线性算法的执行时间应该是其执行时间的两倍多一点。

因此，执行时间比率将从2:8变为8:16，即二次算法现在的速度只有原来的两倍。

再次将输入的大小加倍，8:16变为32:32；当遇到大约40000个输入时，这两种算法同样快速。

当处理80000的输入大小时，比率是相反的：4乘以32是128，而2乘以32只有64。128:64意味着线性算法现在是另一种算法的两倍。

为了更好地估计A、B、C和D常量，您应该使用非常不同的大小进行测试，可能是N、2*N和4*N。

这一切归结起来就是，不要盲目依赖大O分类。如果你希望你的投入变得越来越大，就使用它；但对于较小的输入，很可能是可伸缩性较差的算法更有效。

您甚至可能决定实现算法的两个版本，并根据输入大小使用其中一个版本。有一些递归算法正是这样做的，并在最后一次迭代中切换到迭代实现。在图中的例子中，您可以为每个大小范围实现最佳算法；但最好的折衷办法是只使用两种算法，在N=15之前使用二次算法，然后切换到对数算法。

我在这里找到了对Introsort的引用

是一种排序算法，最初使用快速排序，但当递归深度超过基于被排序元素数对数的级别时，会切换到堆排序，并且由于其良好的引用局部性（即当数据最有可能驻留在内存中且易于引用时），会对小型情况使用插入排序。

在上述情况下，插入排序利用内存局部性，这意味着其B常量非常小；递归算法可能会产生更高的成本，并且具有显著的C值。因此，对于小数据集，更紧凑的算法表现良好，即使它们的大O分类更差。