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

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

Создайте 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.

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

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

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

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

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

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

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

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

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

Для этого можно использовать два сравнения. Умножьте наиболее важное сравнение на 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

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

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

Затем вы просто выполняете обычную сортировку на основе очков.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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