logo标签列表

近似排序算法 - 何时使用？

algorithmlanguage-agnosticsorting
8

有时候我会浏览网页，寻找有趣的算法和数据结构以便丰富我的技能库。一年前我发现了 Soft Heap 数据结构，并学习了近似排序的相关知识。

这个想法的背后是，如果你能接受排序算法“作弊”一点，那么你就可以突破基于比较的排序的 O(n log n) 限制。你可以得到一个几乎排序好的列表，但是你也必须接受一些错误。

我在测试环境中尝试了这些算法，但从未找到过使用它们的机会。

所以问题来了：有没有人曾经在实践中使用过近似排序？如果有，在哪些应用程序中使用？你能想到一个适合使用近似排序的用例吗？

6个回答
11

这只是一种大胆的猜测，但考虑到在搜索结果排序时“相关性”度量的固有主观性，我认为它们是否完全排序并不重要。 推荐也可以这么说。 如果你能以O（n）的方式安排算法的每个其他部分，那么你可能会尝试避免排序。

还要注意，在最坏的情况下，“几乎排序”的数据不满足“几乎排序”的一个可能的直观想法，即它只有少量的逆序对。原因就是，如果你的数据只有O（n）个逆序对，那么你可以使用插入排序或鸡尾酒排序（即双向冒泡排序）在O（n）时间内完成排序。由此可知，你不可能在O（n）时间（使用比较）从完全未排序的状态到达这个点。因此，你正在寻找的应用程序是其中大多数数据集已排序且其余部分散布而不是需要每个元素都接近其正确位置的应用程序。

5

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

4

只是猜测，但我想其中一个可能是数据库查询优化。

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

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

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

另一个想法（我仍然只是猜测）是进程或线程调度器在时间共享系统中，其中某个进程或线程稍晚一些获得其时间片可能并不重要，而不是按优先级严格排序。

+1，我喜欢数据库规划优化的例子。关于进程调度，我猜它更加复杂，因为如果没有确切的保证“如何以及多少”结果无法完美排序，你可能会遇到进程饥饿的情况。 - j_random_hacker
2

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

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

1

无论何时

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

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

资源调度的例子可能是响应比萨外送或向人们发送书籍盒子等。你不能在期望确定性结果的地方使用它，但在现实生活中有很多例子是不那么确定性/可预测的。

-1

O(n log n)已经相当快了。我不认为有人会一开始就使用近似排序算法。你会从只完成完整排序的代码开始（因为你选择的编程语言可能提供了一个sort函数而不是nearsort函数），当你发现排序太慢时，你会开始质疑你的数据是否真的需要完全排序，并考虑使用近似排序。

基本上，除非你首先发现排序是程序中的严重瓶颈，否则你永远不会考虑使用近似排序。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接