14

我正在对整数键数组进行排序。

有关数据的信息：

  • 数组长 1176 个元素
  • 密钥在 750 000 和 135 000 000 之间；0 也是可能的
  • 有很多重复项，在每个数组中只有 48 到 100 个不同的键，但无法预测哪些值会超出整个范围
  • 有很多长排序子序列，大多数数组由 33 到 80 个排序子序列组成
  • 最小元素为0；0 的数量是可预测的并且在非常窄的范围内，每个数组大约 150 个

到目前为止我尝试了什么：

  1. stdlib.h qsort ;

    这很慢，现在我的函数在每次执行排序上花费 0.6 秒，而 stdlib.h qsort 是 1.0 秒；这与 std::sort 具有相同的性能

  2. 蒂姆排序；

    我试过这个：https ://github.com/swenson/sort和这个：http ://code.google.com/p/timsort/source/browse/trunk/timSort.c?spec=svn17&r=17 ；两者都比 stdlib qsort 慢得多

  3. http://www.ucw.cz/libucw/；

    他们的快速排序和插入排序组合是迄今为止我的数据最快的；我尝试了各种设置并将枢轴作为中间元素（不是 3 的中值）并从 28 个元素子数组（默认不是 8 个）开始插入排序可以提供最佳性能

  4. 壳排序；

    与这篇文章的差距的简单实现：http ://en.wikipedia.org/wiki/Shellsort ；它很不错，虽然比 stdlib qsort 慢

我的想法是 qsort 做了很多交换和破坏（即反向）排序的子序列，所以应该有一些方法可以通过利用数据结构来改进它，不幸的是到目前为止我所有的尝试都失败了。
如果您好奇这是什么类型的数据，这些是在已经在前一个板上排序的各种板上评估的扑克手组（这是排序子序列的来源）。

该函数在 C 中。我使用 Visual Studio 2010。有什么想法吗？

示例数据： http: //pastebin.com/kKUdnU3N
示例完整执行（1176 种）：https ://dl.dropbox.com/u/86311885/out.zip

4

8 回答 8

7

如果您首先通过数组对数字进行分组以消除重复项怎么办。每个数字都可以进入一个哈希表，其中数字是键，出现的次数是值。因此，如果数字 750 000 在数组中出现 57 次，则哈希表将保存 key=750000；值=57。然后，您可以按键对小得多的哈希表进行排序，其长度应少于 100 个元素。

有了这个，你只需要通过数组，另一个通过更小的哈希表键列表。这应该避免大多数交换和比较。

于 2012-06-19T02:26:40.423 回答
5

你可以看看我从这篇文章中看到的这个动画

我认为您的问题属于“少数独特”类别，其中 3 路分区快速排序和外壳排序非常快。

更新：

我基于sorting-algorithms.com上的伪代码实现了一些排序算法，并在OP给出的样本数据上运行它们。纯娱乐：

插入 0.154s

外壳 0.031s

快速排序 0.018s

基数 0.017s

3路快速分拣0.013s

于 2012-06-19T02:32:08.123 回答
2

Seems like a Radix Sort or a Bucket sort would be the way to go since they can be efficient on integers.

Radix sort's efficiency is O(k·n) for n keys which have k or fewer digits. Sometimes k is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which are all O(n·log(n)). While bucket sort is O(N*k) for n keys and k buckets.

It may come down to the constant (K) factor for radix sort. From my Java experimentation. Also, it's worth noting that radix doesn't fair so well with sorted elements.

100k integers:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.075   0.025   0.025
Quicksort           0.027   0.014   0.015
Heap sort           0.056   0.03    0.03
Counting sort       0.022   0.002   0.004
Radix sort          0.047   0.018   0.016

500k integers:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.286   0.099   0.084
Quicksort           0.151   0.051   0.057
Heap sort           0.277   0.134   0.098
Counting sort       0.046   0.012   0.01
Radix sort          0.152   0.088   0.079

1M integers:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.623   0.18    0.165
Quicksort           0.272   0.085   0.084
Heap sort           0.662   0.286   0.207
Counting sort       0.066   0.022   0.016
Radix sort          0.241   0.2     0.164

10M integers:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          7.086   2.133   1.946
Quicksort           4.148   0.88    0.895
Heap sort           11.396  3.283   2.503
Counting sort       0.638   0.181   0.129
Radix sort          2.856   2.909   3.901

It seems like 500k items is when the constant starts favoring radix sort over quicksort.

于 2012-06-19T02:50:29.220 回答
2

有一种算法可以利用已排序的子序列。它是合并排序的一种变体，称为自然合并排序。我在 C 中找不到一个很好的实现示例，但从头开始实现看起来并不难。基本上它是这样的：

  1. 您需要一个包含两个整数的结构，即子序列的索引和长度。创建这些结构的新数组（或者可能是链表）。
  2. 遍历整个数组一次，每次一个值小于前一个值时，它就是一个新子序列的开始，因此创建一个新结构并分配子序列的位置，并分配前一个子序列的长度- 前一个结构的序列。
  3. 遍历您的结构并对它们成对执行合并操作。
  4. 重复步骤 3，直到全部合并。

合并操作与Merge Sort中的合并操作相同。您有一个指向每个子序列开头的指针。哪个较小的应该在子序列的开头，所以如果它还没有，则将它移到那里，然后将指针移到您从中移动它的子序列上。继续合并两个子序列，直到它们完全排序。

您可以将其与 Oleski 的答案结合起来创建一种链表，其中每个节点都包含一个值以及一个值在子序列中连续出现的次数。然后，当您合并时，如果遇到等效值，您将它们的基数相加，以一次添加几个相同的值。您不需要为这种潜在的优化做一个散列。

于 2012-06-19T04:59:16.693 回答
1

建立一个哈希表并分配一个数组。对于输入数组中的每个项目，检查该项目是否在哈希表中。如果是，则增加其值。如果没有，请将其插入值为 1 的哈希表中，并将其附加到您的数组中。

对数组进行排序。对于数组中的每个项目，将该项目写入输出的次数等于其在哈希表中的计数。鳍。

编辑：您可以为需要排序的每个数组清除并重新使用哈希表。

于 2012-06-19T02:33:03.503 回答
0

我会尝试一个手动编码的 qsort，它具有在每个节点上存储数字的特殊技巧，以及它发生的次数。当您再次看到它时，您会增加计数。

始终从数组中间取枢轴，这样排序的子序列就不会给你一系列坏的枢轴。

于 2012-06-19T02:31:34.000 回答
0

给定已排序的运行，一种合理的可能性是使用就地合并将这些运行组合成大的已排序运行，直到您的整个数组被排序。请注意，如果函数只需要一个 C 接口（而不是必须用 C 本身编写），您可以使用C std::inplace_merge++ 标准库中的extern "C"

于 2012-06-19T05:26:12.263 回答
0

坦率地说，GNU 的 qsort 非常好并且难以击败，但我最近将大部分 qsort 调用转换为 Christopher Swenson 对tim_sort的调用，可以在https://github.com/swenson/sort/blob/master/找到sort.h - 它真的非常好。顺便说一句，它显式地利用了已经排序的段，比如你的数据中的段。

我正在做 C++，并且已经“模板化”了 Christopher 的（纯 C 宏）代码，但它可能不会改变这样一个事实，即它在您的数据上绝对是赢家。我相信以下在带有 -O3 的 GNU-64 中没有吸引力：

排序测试：

  • qsort: 00:00:25.4

  • 时间排序：00:00:08.2

  • 标准::排序：00:00:15.2

（每一种都运行一百万次）。

于 2020-01-12T02:08:27.123 回答