алгоритм сортировки, где парное сравнение может вернуть больше информации, чем -1, 0, +1

Question

Большинство алгоритмов сортировки основаны на парном сравнении, которое определяет, будет ли A B.

Я ищу алгоритмы (и бонусные баллы, код на Python), которые используют функцию парного сравнения, которая может отличать намного меньше от немного меньше или намного больше от немного большего. Так что, возможно, вместо возврата {-1, 0, 1} функция сравнения возвращает {-2, -1, 0, 1, 2} или {-5, -4, -3, -2, -1, 0, 1 , 2, 3, 4, 5} или даже действительное число на интервале (-1, 1).

Для некоторых применений (например, сортировка рядом или приближенно) это позволило бы определить разумную сортировку с меньшим количеством сравнений.

Answer 1

Вы можете использовать модифицированную быструю сортировку. Позвольте мне объяснить на примере, когда функция сравнения возвращает [-2, -1, 0, 1, 2]. Скажем, у вас есть массив для сортировки.

Создание 5 пустых массивов - Aminus2, Aminus1, A0, Aplus1, Aplus2.

Выберите произвольный элемент из A, X.

Для каждого элемента массива сравните его с X.

В зависимости от результата поместите элемент в один из массивов Aminus2, Aminus1, A0, Aplus1, Aplus2.

Примените ту же сортировку рекурсивно к Aminus2, Aminus1, Aplus1, Aplus2 (примечание: вам не нужно сортировать A0, поскольку все элементы там равны X).

Объедините массивы, чтобы получить окончательный результат: A = Aminus2 + Aminus1 + A0 + Aplus1 + Aplus2.

Answer 2

Дополнительная информация действительно может использоваться, чтобы минимизировать общее количество сравнений. Вызовы функции super_comparison могут использоваться, чтобы сделать вычеты эквивалентными большому количеству вызовов обычной функции сравнения. Например, a much-less-than b и c little-less-than b подразумевают a < c < b.

Вычеты могут быть организованы в контейнеры или разделы, каждый из которых может быть отсортирован отдельно. По сути, это эквивалентно быстрой сортировке с n-сторонним разделом. Вот реализация в 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)

Используя этот код с помощью модуля trace , можно измерить прирост производительности. В приведенном выше коде обычное трехстороннее сравнение использует 133 000 сравнений, в то время как функция супер сравнения уменьшает количество вызовов до 85 000.

Код также позволяет легко экспериментировать с различными функциями сравнения. Это покажет, что наивные функции n-way сравнения очень мало помогают в сортировке. Например, если функция сравнения возвращает +/- 2 для различий, превышающих четыре, и +/- 1 для различий, равных четырем или менее, количество сравнений уменьшается лишь на скромное 5%. Основная причина заключается в том, что используемые в начале разделы с детализированным курсом имеют только несколько «близких совпадений», а все остальное попадает в «дальние совпадения».

Улучшение суперсравнения состоит в том, чтобы охватить логарифмические диапазоны (то есть +/- 1, если в пределах десяти, +/- 2, если в пределах ста, +/-, если в пределах тысячи.

Идеальная функция сравнения была бы адаптивной. Для любого заданного размера последовательности функция сравнения должна стремиться подразделить последовательность на разделы примерно одинакового размера. Теория информации говорит нам, что это максимизирует количество бит информации за сравнение.

Адаптивный подход также имеет смысл. Люди должны сначала быть разделены на любовь против как , прежде чем проводить более изысканные различия, такие как любовь много против любви немного. Дальнейшие разделительные проходы должны делать все более и более четкие различия.

Answer 3

Учитывая, что вы хотите заказать ряд предметов, основанных на человеческом сравнении, вы можете подойти к этой проблеме, например, к спортивному турниру. Вы можете позволить каждому человеческому голосу увеличить счет победителя на 3 и уменьшить проигравшего на 3, +2 и -2, +1 и -1 или просто 0 0 за ничью.

Тогда вы просто делаете обычную сортировку на основе баллов.

Другой альтернативой будет структура турнира с одиночным или двойным выбыванием.

Answer 4

Я не могу вспомнить ни одной ситуации, в которой это было бы действительно полезно. Даже если бы я мог, я подозреваю, что добавленные циклы ЦП, необходимые для сортировки нечетких значений, будут больше, чем те «дополнительные сравнения», на которые вы ссылаетесь. Но я все еще предложу предложение.

Рассмотрим эту возможность (все строки используют 27 символов a-z и _):

            11111111112
   12345678901234567890
1/ now_is_the_time
2/ now_is_never
3/ now_we_have_to_go
4/ aaa
5/ ___

Очевидно, строки 1 и 2 более похожи, чем 1 и 3, а намного более похожи, чем 1 и 4.

Одним из подходов является масштабирование значения разности для каждой идентичной позиции символа и использование первого другого символа для установки последней позиции.

Отложив знаки на данный момент, сравнивая строку 1 с 2, разница в положении 8 на 'n' - 't'. Это разница 6. Чтобы превратить это в одну цифру 1-9, мы используем формулу:

digit = ceiling(9 * abs(diff) / 27)

, поскольку максимальная разница равна 26. Минимальная разница 1 становится цифрой 1. Максимальная разница 26 становится цифрой 9. Наша разница 6 становится 3.

И поскольку разница находится в позиции 8, функция сравнения out вернет 3x10 ^-8 (на самом деле она вернет отрицательную величину, поскольку строка 1 следует после строка 2.

Используя аналогичный процесс для строк 1 и 4, функция сравнения возвращает -5x10 ^-1 . Максимально возможный возврат (строки 4 и 5) имеет разность в позиции 1 '-' - 'a' (26), которая генерирует цифру 9 и, следовательно, дает нам 9x10 ^-1 .

Возьмите эти предложения и используйте их по своему усмотрению. Мне было бы интересно узнать, как работает ваш нечеткий код сравнения.

Answer 5

Кажется, что использование модифицированной быстрой сортировки raindog позволит вам быстрее выводить результаты и, возможно, быстрее их просматривать.

Может быть, эти функции уже доступны в тщательно контролируемой операции qsort? Я не много думал об этом.

Это также звучит как радикальная сортировка, за исключением того, что вместо просмотра каждой цифры (или другого вида правила сегмента) вы составляете сегменты из богатых сравнений. Мне трудно думать о случае, когда доступны подробные сравнения, а цифры (или что-то в этом роде) отсутствуют.

Answer 6

Возможно, есть веская причина для этого, но я не думаю, что это лучше, чем альтернативы для любой конкретной ситуации, и , конечно, не годится для общих случаев. Причина? Если вы ничего не знаете о области входных данных и о распределении значений, которые вы не сможете улучшить, скажем, быстрой сортировкой. И если вы действительно знаете эти вещи, часто есть способы, которые были бы гораздо более эффективными.

Анти-пример: предположим, что ваше сравнение возвращает значение "огромной разницы" для чисел, отличающихся более чем на 1000, и что входное значение равно {0, 10000, 20000, 30000, ...}

Анти-пример: то же, что и выше, но с вводом {0, 10000, 10001, 10002, 20000, 20001, ...}

Но, вы говорите, я знаю, что мои данные не выглядят так! Что ж, в таком случае расскажите нам, как на самом деле выглядят ваши материалы. Тогда кто-то может действительно помочь.

Например, однажды мне нужно было отсортировать исторические данные. Данные были сохранены отсортированными. Когда добавлялись новые данные, они добавлялись, затем список запускался снова. У меня не было информации о том, где были добавлены новые данные. Я разработал гибридную сортировку для этой ситуации, которая легко побеждает qsort и другие, выбирая сортировку, которая была быстрой для уже отсортированных данных, и настраивая ее так, чтобы она была быстрой (по сути, переключаясь на qsort), когда она обнаруживала несортированные данные.

Единственный способ улучшить качество сортировки общего назначения - это знать свои данные. И если вы хотите получить ответы, вам нужно очень хорошо об этом сообщить.

Answer 7

Вы можете использовать два сравнения, чтобы достичь этого. Умножьте более важное сравнение на 2 и сложите их вместе.

Вот пример того, что я имею в виду в Perl. Он сравнивает две ссылки на массив по первому элементу, затем по второму элементу.

use strict;
use warnings;
use 5.010;

my @array = (
  [a => 2],
  [b => 1],
  [a => 1],
  [c => 0]
);

say "$_->[0] => $_->[1]" for sort {
  ($a->[0] cmp $b->[0]) * 2 +
  ($a->[1] <=> $b->[1]);
} @array;

a => 1
a => 2
b => 1
c => 0

Вы можете очень легко распространить это на любое количество сравнений.