大多数排序算法都依赖成对比较来确定A B。
我正在寻找利用成对比较功能的算法(以及加分点,Python中的代码),该函数可以将少得多或少一点或多一点或多一点。因此,比较函数可能会返回{-2,-1,0,1,2}或{-5,-4,-3,-2,-1,0,1,而不是返回{-1,0,1} ,2、3、4、5}甚至间隔(-1,1)上的实数。
对于某些应用程序(例如近距离排序或近似排序),这将使通过较少的比较即可确定合理的排序。
实际上,可以使用额外的信息来最大程度地减少比较的总数。可以使用对super_comparison函数的调用来进行推论,这等同于对常规比较函数的大量调用。例如,a much-less-than b和c little-less-than b暗示a < c < b。
a much-less-than b
c little-less-than b
a < c < b
扣除罐被组织成箱或分区,可以分别分类。实际上,这等效于具有n路分区的QuickSort。这是Python中的实现:
from collections import defaultdict from random import choice def quicksort(seq, compare): 'Stable in-place sort using a 3-or-more-way comparison function' # Make an n-way partition on a random pivot value segments = defaultdict(list) pivot = choice(seq) for x in seq: ranking = 0 if x is pivot else compare(x, pivot) segments[ranking].append(x) seq.clear() # Recursively sort each segment and store it in the sequence for ranking, segment in sorted(segments.items()): if ranking and len(segment) > 1: quicksort(segment, compare) seq += segment if __name__ == '__main__': from random import randrange from math import log10 def super_compare(a, b): 'Compare with extra logarithmic near/far information' c = -1 if a < b else 1 if a > b else 0 return c * (int(log10(max(abs(a - b), 1.0))) + 1) n = 10000 data = [randrange(4*n) for i in range(n)] goal = sorted(data) quicksort(data, super_compare) print(data == goal)
通过使用 跟踪 模块对该代码进行检测,可以测量性能增益。在上面的代码中,常规的三路比较使用133,000个比较,而超级比较功能将调用次数减少到85,000。
该代码还使您可以轻松地尝试各种比较功能。这将表明纯朴的n向比较功能对排序没有什么帮助。例如,如果比较函数对于大于四的差返回+/- 2,对于小于或等于四的差返回+/- 1,则比较次数仅减少了5%。根本原因是,一开始使用的粗粒度分区只有少数“接近匹配”,其他所有内容都属于“远匹配”。
超级比较的一个改进是覆盖了对数范围(即,十个以内为+/- 1,百个以内为+/- 2,一千以内为+/-。
理想的比较功能将是自适应的。对于任何给定的序列大小,比较功能应努力将序列细分为大小大致相等的分区。信息理论告诉我们,这将使每次比较的信息位数最大化。
自适应方法也具有良好的直观意义。人们应该先划分为 爱 与 喜欢, 然后再进行更精细的区分,例如,很多爱与一点爱。进一步的分区通道应分别进行越来越精细的区分。