0

我最近学会了如何使用堆和堆排序的美妙之处。我决定将 heapsort 与 C++ 中的 std::sort 和 Java 中的 Arrays.sort() 进行比较。我对一个整数数组进行了排序，每个整数在 <0 的范围内随机生成；2000000000)

我在 Java 中将 100,000,000 个整数生成到一个数组中，然后运行 ​​Arrays.sort()，然后生成新的随机序列并运行我的 heapSort()。这是我的 Java 程序的输出：

Arrays.sort time: 10.923 seconds.

Heap sort time: 1.402 seconds.

所以堆排序快了大约 8 倍。

然后我在 C++ 中运行了类似的代码，这次使用 std::vector 作为我的容器（因为 std::sort 需要两个迭代器）。

C++ 结果：

Heapsort: 3.213

std::sort: 37.264

所以在我的程序中，std::sort 慢了大约 12 倍。

在 Java 中，我使用 System.currentTimeMilis() 测量时间，而在 C++ 中，我使用来自 .

这是在 Windows 7、四核 Intel i5 2500k、超频至 4.8GHz 上进行测试的。C++ 是用-Wall -pedantic标志编译的。

谁能告诉我发生了什么？堆排序真的那么快吗？还是我在代码中犯了错误？我不想用大量代码淹没这篇文章，所以我将在本文末尾链接它。

顺便说一句：是的，我知道 Arrays.sort() 是稳定的，而 heapsort 不是。Java 没有不稳定的排序（至少，我还没有找到）。这就是为什么我在 C++ 中使用 std::sort 来查看它是否与稳定性有关。

源代码，C++ 和 Java：https ://gist.github.com/anonymous/7475399

4

3 回答 3

7

你的 Java 代码在我看来有问题

int tmp = heap[0];
heap[i] = heap[0];
heap[i] = tmp;

这不是交换两个元素的代码。

这对执行时间有影响吗？我对堆排序的了解不够好，无法确定。

于 2013-11-14T22:32:11.580 回答
2

您没有正确交换 Java 中的项目（正如 john 指出的那样），也没有正确交换 C++ 代码中的项目：

void heapSort(vector<int> & heap, int length)
{
    int heapsize = length;
    buildHeap(heap, heapsize);
    for(int i = heapsize-1; i >= 1; i--)
    {
        int tmp = heap[0];
        heap[i] = heap[0];
        heap[i] = tmp; // overwrote the item you just tried to swap!
        heapsize--;
        heapify(heap, 0, heapsize);
    }
}

简而言之，您的代码“更高效”，因为它根本不进行任何排序。

于 2013-11-14T22:52:32.513 回答
1

您的 C++ 代码中还有另一个问题与您如何生成随机分布有关：

int randomval()
{
  double d;
  int result;
  d = rand() / RAND_MAX;
  result = (int) (d * N);
  return result;
}

d总是会是0因为你正在执行一个int除法，然后隐式地将它转换为double之后。简而言之，您的randomval函数根本没有给您任何随机值。

当您使用自己的堆排序对其进行排序时，始终执行相同的代码路径。在您的情况下，heapify可能永远不会执行这部分代码：

if (largest != i)
{
    int tmp = heap[i];
    heap[i] = heap[largest];
    heap[largest] = tmp;

    heapify(heap, largest, heapsize);
}

这就是为什么您的实施似乎更快的原因。

使用实际分布修复随机测试数据我认为您会发现您的实现速度较慢：

#include <random>
// snip...
int main()
{
  int length = 10000000;
  std::vector<int> vint1;

  std::default_random_engine gen;
  std::uniform_int_distribution<int> randomval(1, N);
  for (int i = 0; i < length; i++)
  {
        vint1.push_back(randomval(gen));
  }
  std::vector<int> vint2 = vint1; /* so we're sorting same testdata for both */
  // ...

再次运行基准测试显示：

g++ -std=c++0x -Wall -pedantic -O2 heapsorttest.cpp -o heapsorttest.exe
heapsorttest.exe

Heapsort: 5.822s
true

std::sort: 0.936s
true
于 2013-11-14T23:56:31.443 回答