8

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

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

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

所以问题是：有没有人在实践中使用过近似排序？如果是在哪种应用程序中？你能想出一个用例，其中接近排序是正确的做法吗？

4

6 回答 6

11

这是一个完全的猜测，但考虑到对搜索结果进行排序时“相关性”度量的固有主观性，我敢说它们是否被完美排序并不重要。建议也是如此。如果您可以以某种方式将这些算法的其他所有部分安排为 O(n)，那么您可能会避免排序。

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

于 2008-09-28T17:18:48.767 回答
5

有很多“贪婪”启发式方法，您可以定期选择一组中的最小值。贪心启发式并不完美，因此即使您选择最小值，也不能保证获得最佳最终答案。实际上，在GRASP元启发式算法中，您有意引入随机误差，以便获得多个最终解决方案并选择最佳的一个。在这种情况下，在您的排序例程中引入一些错误以换取速度将是一个很好的权衡。

于 2008-09-29T05:00:28.890 回答
4

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

使用诸如 SQL 之类的声明性语言的数据库查询必须被翻译成称为“执行计划”的分步程序。一个 SQL 查询通常可以转换为许多这样的执行计划，它们都给出相同的结果，但性能可能会有很大差异。查询优化器必须找到最快的，或者至少是相当快的。

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

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

另一个想法（我仍然只是推测）是分时系统中进程或线程的调度程序，如果某个进程或线程比严格按优先级排序晚几毫秒获得它的时隙，这可能并不重要.

于 2008-09-29T03:11:30.883 回答
2

近似排序的一个常见应用是当人类进行成对比较并且您不想问他们很多问题时。

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

于 2009-05-27T04:46:29.793 回答
1

任何地方

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

你可以使用它。“不那么严格”的基于规则的优先级队列怎么样？这在哪里有用？也许是线程/进程/资源调度。在线程/进程调度中，您真的不保证任何一个线程会先行、第二行或最后一行，但通常您希望给每个人一些机会。你可能想强制执行宽松的规则，所以它是先发制人的，优先的，blabla ..

资源计划示例是响应披萨交付或向人们运送书箱等。您不能在预期结果确定的情况下使用它，但在现实生活中存在很多事情不是那么确定/可预测的示例。

于 2008-09-29T03:27:58.520 回答
-1

O(n log n) 已经非常快了。我认为没有人会开始使用近似排序算法。您将从只进行完整排序的代码开始（因为您选择的编程语言可能提供sort函数而不是nearsort函数），当您凭经验发现排序花费的时间太长时，您会开始质疑您的数据是否确实需要完全排序，并考虑使用近似排序。

Basically, you would never even consider using a near sort unless you first discovered sorting to be a severe bottleneck in your program.

于 2011-04-28T07:05:52.837 回答