何时排序需要更快

引言

有时，无论数据排序多快，都需要更快的速度。这里有一些关于算法和其他减少排序时间的想法。

某些系统的排序时间可能几乎消失。

添加问题是为了不断挑战我们的假设。

背景

有一些数据需要排序。数据量可能很大，甚至非常大。

无论有多少数据，都需要显著的时间（我们人类可以感知到的）来完成排序。如果排序时间少于1秒，我们仍然可以继续这项调查。

懒惰优化：我们能否完全跳过排序？

不能。后续处理需要按特定顺序排列的数据。

找出排序的特点

由于我们想更多地了解排序工作是如何进行的，请考虑对代码进行插桩和/或使用性能分析工具。

最低限度的排序插桩应该包括：使用的时间和需要排序的数据量。

更好的排序插桩还应包括：比较次数、交换次数、比较所花费的时间、交换所花费的时间、排序代码其他操作所花费的时间（例如，内存分配/重新分配的次数）。

我们还应该更多地了解数据本身，因为它会影响排序性能，以及哪种排序算法可能适合处理这些数据。

数据的结构是什么？是否有其他结构会更有效率？

我们通常不会编写在运行时四处跳转的代码。这有助于处理器以更少的 CPU 缓存未命中来获取指令。数据结构也一样。**引用局部性**（对于数据）绝对可以成为我们的朋友。

我们是否需要担心数据结构的大小，还是有一点余地可以通过向数据结构添加辅助成员来支持更快的排序？

数据存储在哪里，在排序时能否将其移动到访问速度更快的存储介质上？

将文件临时加载到内存中进行排序通常比在磁盘上排序快得多。例如，在旧的 Palm OS 手持设备上，一切都在内存中，但文件 API 比使用内存中的数组慢。

于是我们在这个网站上搜索 - insertion_sorted_list.aspx

（上面内容与此处建议的类似）

https://codeproject.org.cn/KB/tips/optimizationenemy.aspx

（并尽量不要过度优化）

以及网络上的其他地方 - http://en.wikipedia.org/wiki/Sorting_algorithm

来寻找更好的排序算法。

我们学习**分治算法**：特别是与排序相关的。

http://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

我们发现了一个 Quicksort 的新变种，它将数据分成三部分而不是两部分。

我们尝试了三路 Quicksort，它速度有所提升。假设总时间减少了 1/3。

这足够快了吗？

也许不够快，如果我们回顾一些假设。

这张图有什么问题？

让我们退一步，试着用类比来推理。

仓库！

我们有一个空仓库。卡车一直在到达。有些卡车装满了集装箱，有些只有几个小箱子。我们时间不多，所以我们只是把所有东西都堆在仓库的一个角落里，然后不断地把更多东西放进去，随着堆积物填满仓库向其他区域扩展。终于，最后一辆卡车（目前）已经卸载完毕。一位顾客来了，想要一份堆积物中的物品列表。

是时候放出排序助手了。也许需要几天或几周，才能找到顾客列表上的所有物品。

没有人会这样经营仓库。我们为什么会这样对待计算机数据？

我们应该明确**正式或非正式的架构或设计方法**所**要求**的是什么，以及后续处理**真正需要**的是什么。

**后续处理真正需要排序的数据**以进行进一步分析或 UI 显示等。后续处理不关心数据是如何或何时排序的，只要它被排序即可。所以这里真正需要的是排序，而不是排序**发生的时间**。

回到我们的仓库类比：将卡车卸下的物品在卸入仓库时进行排序会更有意义。这样，获取顾客的物品列表就会更容易、更快。这正是我们应该大力考虑的计算机数据处理方法：在获取数据的同时进行排序。

让我们回到**排序算法定义**（计算机科学方法的定义）

我们有一个包含 N 个项目的列表（或数组或其他）。按所需的顺序对列表进行排序。

我们应该考虑（也许更实际的）**系统设计定义**

我们有一个同时采集和排序数据的系统，以供后续处理。数据可以在所有采集完成后进行排序，也可以在采集过程中进行排序。我们应该对采集过程中排序进行原型设计和基准测试，并与所有采集完成后排序进行比较。我们将根据需要修改此定义（这里还有其他权衡需要考虑）。

但等等！没有排序算法可以边采集数据边排序！？！

没错。我们现在正在跳出计算机科学排序算法定义的框框，并试图让软件更有效。

排序插入“算法”伪代码

• 分配一个空列表（但如果已知 N，请考虑分配 N 个项目）。
• 从外部调用以获取一些数据（可能一次不止一个）。
• 将第一个数据放入列表中，无需比较。
• 将插入点变量设置为列表的第一个位置。
• **当**还有更多数据时

  使用插入排序算法的内层循环，一次将 1 个数据项进行排序插入到已排序的列表中。

  与插入点和/或其后的列表元素进行比较，以找到该数据项的正确插入点，这可能更快。保存当前插入点以备后用。

  // The insertion point approach works because sometimes
  // data will be already ordered correctly and only a couple 
  // of compares are needed to find the proper place.

• 从外部调用以获取更多数据，或者完成。
• 循环回**当**，直到没有更多数据可获取。
• （完成。）

O(n) 排序插入性能的粗略估计

请记住，这里需要检查的已排序项的数量从 1 到 N。

所有其他排序算法都有 N 个项目需要遍历。

因此，**平均需要遍历的项目数是 N/2，而不是总是 N**。

**最佳情况**：需要排序的数据已按顺序排列。

每个数据项的开销是 2 次比较和 1 次列表插入。

我认为这大约是 O(n)（线性成本）。

**平均情况**：不太确定如何估算。高度依赖于实际或测试数据模式的具体变化以及使用的数据结构。

**最坏情况**：数据按相反顺序排列，或数据按随机顺序排列。

我认为这大约是 O(n^2)（二次成本）。但这里的 n 比其他算法的值要小。如果使用数组排序，则二分搜索可以帮助找到插入点。

通过从最后一个已知插入点回溯到上一个点，可以改善反向排序数据的性能。我们可以预期需要回溯的列表项数量很少。那么开销将与最佳情况类似。

这是我们能期望的最好结果吗？让我们从代码回到类比。

仓库！(第二部分)

我们现在将伪代码应用于仓库。当卡车到达时，一名工人卸下一个箱子，然后将其放到仓库中的正确位置。然后工人回去从卡车上取另一个箱子。继续，直到所有箱子都卸载完毕。终于，最后一辆卡车（目前）已经卸载完毕。

这是仓库操作的一个糟糕示例！

大多数仓库会使用 2 名或更多工人，其中一名工人卸载卡车并将箱子放在某个临时区域。另一名工人将从临时区域取走每个箱子到其应在的位置。我们现在需要在算法中考虑 2 个或更多工作线程。

排序插入“算法”伪代码（多线程）

• 分配一个空列表（但如果已知 N，请考虑分配 N 个项目）。
• 将插入点变量设置为列表的第一个位置。
• 创建线程 2，并使其等待，直到被启动并传入待排序数据。
• **当**还有更多数据时
• 线程 1：获取一些数据（可能一次不止一个）。
• 线程 1：可以将数据放入队列，或者唤醒线程 2。
• 线程 1：循环回**当**。
• 线程 2：唤醒并开始进行排序插入。

  线程 2：使用插入排序算法的内层循环，一次将 1 个数据项进行排序插入到已排序的列表中。

  线程 2：与插入点和/或其后的列表元素进行比较，以找到该数据项的正确插入点，这可能更快。保存当前插入点以备后用。

  // The insertion point approach works because sometimes
  // data will be already ordered correctly and only a couple 
  // of compares are needed to find the proper place.

• 线程 2：继续排序数据，直到没有数据为止。

O(n) 多线程排序插入性能估计

如果获取数据的时间大于或等于对先前数据进行排序的时间，那么假设排序线程没有 CPU 饥饿，排序时间将仅限于最后几个项目，当没有更多数据时。

令 S 代表最后一次排序调用中的少量（相对于 N）项目数。

**最佳情况**：需要排序的数据已按顺序排列。

每个数据项的开销是 2 次比较和 1 次列表插入。

我认为这大约是 O(s)（小的线性成本）。

**平均情况**：不太确定如何估算。高度依赖于实际或测试数据模式的具体变化以及使用的数据结构。目前，我们使用 O(s^2)（小的二次成本）。

**最坏情况**：数据按相反顺序排列，或数据按随机顺序排列。

我认为这大约是 O(s^2)（小的二次成本）。但这里的 n 比其他算法的值要小。如果使用数组排序，则二分搜索可以帮助找到插入点。

通过从最后一个已知插入点回溯到上一个点，可以改善反向排序数据的性能。我们可以预期需要回溯的列表项数量很少。那么开销将与最佳情况类似。

经验 1：排序链表

在**前向链表**排序时回溯将是一个问题。不确定是否有优雅的解决方案。一个对我有效的、不那么优雅的方法是同时跟踪前向链表的 1/4、1/2 和 3/4 位置，然后从那里向前遍历链接以找到插入点。这就像一个粗粒度的起始点列表，类似于粗略的**二分**搜索，然后运行**线性**搜索。因为线性搜索是从最近的 1/4 点开始的，而平均项数为 N/2，所以线性搜索在任何时候覆盖的平均项数为 N/16（N/2 的 1/4 的 1/2）。与仅使用插入点方法对超过 10,000 个项目的前向链表进行排序相比，这种改进将排序时间减少了约 30%。跟踪 1/8 的位置**可能**会带来另一项有价值的速度提升。

对于 10,000 多个项目，原始排序时间超过一小时。一位团队成员更改代码使用 Quicksort，时间缩短到一小时以下（快了约 25%）。改为排序插入（不借助更快的线性搜索）将时间缩短到约 1 分钟（快了 60 倍）。借助线性搜索的排序插入将时间缩短到约 40 秒。环境是原始的 IBM PC 8088 CPU，运行速度为 4.77 MHz，使用 16 位 ASM 编写的 DOS TSR 图形引擎。前向链表是一个边缘列表，必须从上到下排序才能与支持的 4096 x 1367 24 位 RGB 数字电影记录器和/或各种打印机和显示器一起工作。

（下面是关于使用分治法处理大于 DOS 1 MB 主内存的数据。这基本上是排序合并的一半，而合并是不需要的。）

后来，代码被增强以处理甚至更大的边缘列表，这些列表不再适合内存。使用了排序插入，直到内存几乎耗尽，然后使用 1/2 的插入点将内存中的列表分割成 2 个 RAM 磁盘文件。随着内存也被分割并用作 2 个缓冲区，可以添加更多边缘。缓冲区会写入直到填满。然后一个填满的缓冲区会再次被分割。分割可以持续到使用多达 26 个临时 RAM 磁盘文件和 26 个内存缓冲区。

经验 2：排序字符串数组

对于 30,000 多个项目，原始排序时间超过 90 分钟。一位团队成员更改代码使用 Quicksort，时间缩短到一小时多一点（快了约 30%）。改为排序插入将时间缩短到约 45 秒（快了 80 倍，这包括从 Windows 和 NetWare API 获取数据的时间）。因为使用了数组，所以不需要代码来辅助线性搜索。环境是 Win95 Pentium 90 MHz 运行 OS 和应用程序安装程序，在 LAN 上，用 32 位 C++ 编写。数组列表是需要排序以在 UI 中显示的列表，该 UI 显示大型公司内网的所有网络节点名称或用户名。

排序插入总结

还有其他几种方法可以帮助加快排序速度，这里没有涵盖。

数据结构的替代结构（以及相关算法）以及使用多处理和/或多线程的硬件方法似乎是首选。请参阅 parallelSort.aspx。

优点

• 何时排序数据以及使用工作线程可以大大减少排序时间
• 如果获取数据的时间 >= 对先前数据排序的时间，那么排序时间可以接近于零！
• 为了获得更好的性能，可能需要一个获取数据的线程池和另一个排序的线程池。

缺点

• 增加了数据采集逻辑的复杂性
• 强烈建议对您的使用场景进行原型设计/基准测试
• 我没有看到对这种方法的研究（也许我错过了那些网站）

关注点

有时你必须凭你的程序员直觉行事，即使同事嘲笑比 Quicksort 更快的排序想法。

在使用类比时，请尝试来回检查类比，并检查是否有不合理的陈述。请记住，类比是一种近似，问题依然存在：它对这个上下文有用吗？

历史

• 2011年6月11日：初始帖子
• 2011年6月14日：文章更新