一尘不染

成对比较可返回比-1、0,+ 1多的信息的排序算法

algorithm

大多数排序算法都依赖成对比较来确定A B。

我正在寻找利用成对比较功能的算法(以及加分点,Python中的代码),该函数可以将少得多或少一点或多一点或多一点。因此,比较函数可能会返回{-2,-1,0,1,2}或{-5,-4,-3,-2,-1,0,1,而不是返回{-1,0,1}
,2、3、4、5}甚至间隔(-1,1)上的实数。

对于某些应用程序(例如近距离排序或近似排序),这将使通过较少的比较即可确定合理的排序。


阅读 292

收藏
2020-07-28

共1个答案

一尘不染

实际上,可以使用额外的信息来最大程度地减少比较的总数。可以使用对super_comparison函数的调用来进行推论,这等同于对常规比较函数的大量调用。例如,a much-less-than bc 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,一千以内为+/-。

理想的比较功能将是自适应的。对于任何给定的序列大小,比较功能应努力将序列细分为大小大致相等的分区。信息理论告诉我们,这将使每次比较的信息位数最大化。

自适应方法也具有良好的直观意义。人们应该先划分为 喜欢,
然后再进行更精细的区分,例如,很多爱与一点爱。进一步的分区通道应分别进行越来越精细的区分。

2020-07-28