La información adicional de hecho se puede utilizar para minimizar el número total de comparaciones. Las llamadas a la función super_comparison se pueden usar para hacer deducciones equivalentes a un gran número de llamadas a una función de comparación regular. Por ejemplo, a much-less-than b y c little-less-than b implica a < c < b.
Las deducciones pueden organizarse en contenedores o particiones que pueden clasificarse por separado. Efectivamente, esto es equivalente a QuickSort con partición n-way. Aquí está una implementación en 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)
instrumentando este código con el módulo de traza , es posible medir la ganancia de rendimiento. En el código anterior, una comparación tridireccional regular utiliza 133,000 comparaciones, mientras que una función de súper comparación reduce la cantidad de llamadas a 85,000.
El código también hace que sea fácil experimentar con una variedad de funciones de comparación. Esto demostrará que las funciones de comparación n-way ingenuas hacen muy poco para ayudar al género. Por ejemplo, si la función de comparación devuelve +/- 2 para las diferencias superiores a cuatro y +/- 1 para las diferencias de cuatro o menos, solo hay una modesta reducción del 5% en el número de comparaciones. La causa principal es que las particiones granulares utilizadas al principio solo tienen un puñado de "coincidencias cercanas" y todo lo demás corresponde a "coincidencias lejanas".
Una mejora a la comparación súper es cubre rangos logarítmicos (es decir +/- 1 si dentro de diez, +/- 2 si dentro de un centenar, +/- si dentro de un mil.
Una función de comparación ideales sería adaptativo. Para cualquier tamaño de secuencia dado, la función de comparación debería tratar de subdividir la secuencia en particiones de tamaño aproximadamente igual. La teoría de la información nos dice que esto maximizará la cantidad de bits de información por comparación.
El enfoque adaptativo también tiene sentido intuitivo. Las personas primero deben dividirse en amor frente a como antes de hacer distinciones más refinadas como love-a-lot vs love-a-little. Los pases de partición adicionales deberían hacer cada uno distinciones más finas y más finas.
¿Se puede garantizar que para la función de comparación f() y los valores x, y y z, las distancias f (x, y) + f (y, z) = f (x, z)? ¿Sería eso <=? Hace la diferencia :-). – Joel
Sí, soy consciente de ese problema. En mi aplicación, no puedo garantizarlo pero solo estoy buscando un tipo cercano, de todos modos, no del todo. –
Si lee hacia abajo, OP está buscando minimizar las comparaciones proporcionadas por un panel de expertos humanos donde los resultados de comparación son subjetivos –