近排序算法 - 何时使用？

Question

我不时浏览网页，寻找有趣的算法和数据结构，放入我的技巧。一年前，我遇到了 Soft Heap 数据结构，并了解了近距离排序。

这背后的想法是，如果您可以接受排序算法作弊的事实，则可以打破基于比较的排序的O（n log n）障碍。你得到一个几乎排序的列表，但你也必须忍受一些错误。

我在测试环境中使用了算法，但从未找到它们的用途。

所以问题：有没有人在实践中使用过近排序？如果是这样的应用程序？你能想到一个近距离排序是正确的用例吗？

Answer 1

有很多“贪婪”的启发式，您可以定期选择最小集合。贪婪的启发式并不完美，所以即使你选择了最低限度，也无法保证获得最佳答案。事实上， GRASP 元启发式，你故意引入随机错误，以便你获得多个最终版本解决方案并选择最佳解决方案。在这种情况下，在您的排序例程中引入一些错误以换取速度将是一个很好的权衡。

Answer 2

这是一个完全的飞行猜测，但考虑到“相关性”的固有主观性。在对搜索结果进行排序时采取措施，我敢说它们是否完美排序并不重要。对于建议也可以这样说。如果你能以某种方式安排你的算法的每个其他部分都是O（n）那么你可能会避免排序。

另请注意，在最糟糕的情况下，您的“近乎排序”了数据不符合“几乎排序”的一种可能的直观概念，即它只有少量的反转。这样做的原因只是如果您的数据只有O（n）反转，那么您可以使用插入排序或鸡尾酒排序（即双向冒泡排序）在O（n）时间内完成排序。因此，在O（n）时间内（使用比较），你不可能从完全未排序到达这一点。因此，您正在寻找应用程序，其中大多数数据子集被排序，其余部分被分散，不用于要求每个元素都接近其正确位置的应用程序。

Answer 3

这里只是推测，但我想到的一件事是数据库查询优化。

必须将诸如SQL之类的声明性语言中的数据库查询转换为称为“执行计划”的逐步程序。一个SQL查询通常可以转换为许多此类执行计划，这些计划都会产生相同的结果，但性能可能会有很大差异。查询优化器必须找到最快的，或至少一个相当快的。

基于成本的查询优化器具有“成本函数”，它们用于估计给定计划的执行时间。穷举优化器遍历所有可能的计划（对于“所有可能的”的某些值）并选择最快的一个。对于复杂的查询，可能的计划数量可能非常大，导致优化时间过长（甚至在您开始在数据库中搜索之前！），因此也有非详尽的优化器。他们只看一些计划，或许在选择哪些计划时有随机因素。这是有效的，因为通常存在大量“好”的东西。计划，找到绝对最好的计划可能并不那么重要 - 如果需要几分钟的优化才能找到2秒，那么选择5秒计划而不是最佳的2秒计划可能会更好计划。

一些优化算法使用“有希望”的排序队列。 （部分）计划。如果你找到绝对最好的计划并不重要，也许你可以使用几乎排序的队列？

另一个想法（我还在猜测）是时间共享系统中进程或线程的调度程序，如果某个进程或线程比严格的情况晚几毫秒获得其时隙可能并不重要按优先顺序排序。

Answer 4

近距离排序的一个常见应用是当一个人进行成对比较时，你不想要问他们那么多问题。

假设您有很多项目，您希望通过成对比较对人类进行排序。如果您愿意接受订购不准确，您可以大大减少您需要他们做的比较次数。例如，您可能不关心相邻的项目是否已被交换，因为首选项目位于顶部。

Answer 5

任何地方

1. 你应该快速反应，
2. 你并不向客户承诺确切的行为，
3. 但在内部你有一些规则

你可以使用它。如何“不那么严格”基于规则的优先级队列？那会有用吗？也许是线程/进程/资源调度。在线程/进程调度中，你真的没有希望任何一个线程可以进入第一，第二或最后，但通常你想给每个人一些机会。你可能想强制执行松散的规则，因此它是先发制人的，优先的，blabla ..

资源计划示例将响应披萨交付或向人们发送书籍等等。您无法在预期确定性结果的地方使用它，但在现实生活中有很多例子，事情不是那么确定/可预测的。

Answer 6

O（n log n）已经非常快了。我认为任何人都不会使用近似排序算法开始。您可以从完全排序的代码开始（因为您选择的编程语言可能提供 sort 函数而不是 nearsort 函数），并且当您根据经验找到时排序花了太长时间，你会开始怀疑你的数据真的是否需要完全排序，并考虑使用近似排序。

基本上，你甚至不会考虑使用近似排序，除非你第一次发现排序是你程序中的一个严重瓶颈。