Самая быстрая последовательность пробелов для сортировки оболочки?

Question

В соответствии с Оптимальной (самой известной) последовательностью приращений для алгоритма сортировки оболочки Марцина Чуры, лучшая последовательность для сортировки оболочек: 1, 4, 10, 23, 57, 132, 301, 701 ..., но как я могу создать такую ​​последовательность? В статье Марцина Чуры он сказал:

Обе последовательности Кнута и Хиббарда относительно плохо, потому что они определяется простыми линейными повторениями.

но в большинстве книг по алгоритмам, которые я нашел, обычно используется последовательность Кнута: k = 3k + 1, потому что ее легко генерировать. Какой у вас способ генерации последовательности сортировки?

Answer 1

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

Самым известным из приращений является Седжвик, о котором вы можете прочитать о здесь (см. Стр. 7).

Answer 2

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

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

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

Answer 3

Мне не было бы стыдно воспользоваться советом, данным в статье Shellsort Википедии,

Что касается среднего числа сравнений, самый известный разрыв последовательности 1, 4, 10, 23, 57, 132, 301, 701 и аналогичные с пробелами найден экспериментально. Оптимальные промежутки за 701 остаются неизвестными, но хорошими результаты могут быть получены путем расширения вышеуказанной последовательности в соответствии с рекурсивная формула h_k = \ lfloor 2.25 h_ {k-1} \ rfloor.

Последовательность Токуда [1, 4, 9, 20, 46, 103, ...], определяемая простой формулой h_k = \ lceil h'_k \ rceil, где h'k = 2.25h'k - 1 + 1, h'1 = 1, можно рекомендовать для практические применения.

догадываясь по псевдониму, кажется, что Марцин Сиура сам редактировал статью WP.

Answer 4

Последовательность составляет 1, 4, 10, 23, 57, 132, 301, 701, 1750. Для каждого следующего числа после 1750 умножьте предыдущее число на 2,25 и округлите вниз.

Answer 5

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

В середине я пишу

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

Проблема заключается в проверке предложенных пробелов, позволяющих сделать обоснованные выводы. Очевидно, что тестирование пробелов против всех n! упорядочения, что набор из n уникальных значений может быть выражен как неосуществимый. Например, тестирование для n = 16 означает, что 20 922 789 888 000 различных комбинаций из n значений должны быть отсортированы для определения точного среднего, наихудшего и обратно отсортированного случаев - просто для проверки одного набора пробелов, и этот набор может не быть Лучший. Возможны 2 ^ (16-2) набора пробелов для n = 16, первый из которых {1}, а последний {15,14,13,12,11,10,9,8,7,6,5,4 , 3,2,1}.

Чтобы проиллюстрировать, как использование случайных комбинаций может давать неверные результаты, предположим, что n = 3 может принимать шесть различных порядков 012, 021, 102, 120, 201 и 210. Вы создаете набор из двух случайных последовательностей для проверки двух возможных наборов пропусков , {1} и {2,1}. Предположим, что эти последовательности оказываются равными 021 и 201. для {1} 021 можно отсортировать с тремя сравнениями (02, 21 и 01) и 201 с (20, 21, 01), что дает в общей сложности шесть сравнений, разделенных на два и вуаля, в среднем 3 и наихудший случай 3. Использование {2,1} дает (01, 02, 21 и 01) для 021 и (21, 10 и 12) для 201. Семь сравнений с наихудшим случаем 4 и в среднем 3,5. Фактическое среднее и наихудшее значение для {1] составляет 8/3 и 3 соответственно. Для {2,1} значения равны 10/3 и 4. Средние значения были слишком высокими в обоих случаях, а худшие случаи были правильными. Если бы 012 был одним из случаев, {1} дал бы 2,5 в среднем - слишком низко.

Теперь расширим это, чтобы найти набор случайных последовательностей для n = 16, так что ни один из протестированных наборов пробелов не будет предпочтительным по сравнению с другими, и результат будет близок (или равен) истинным значениям, все время сохраняя обработку до минимума. Это можно сделать? Возможно. В конце концов, все возможно - но возможно ли это? Я думаю, что для этой проблемы случайным является неправильный подход. Выбор последовательностей в соответствии с некоторой системой может быть менее плохим и даже хорошим.

Answer 6

Я нашел эту последовательность, похожую на последовательность Марцина Чиуры:

1, 4, 9, 23, 57, 138, 326, 749, 1695, 3785, 8359, 18298, 39744, etc.

Например, последовательность Чуры:

1, 4, 10, 23, 57, 132, 301, 701, 1750

Это среднее от простых чисел. Код Python для определения среднего числа простых чисел находится здесь:

import numpy as np

def isprime(n):
    ''' Check if integer n is a prime '''
    n = abs(int(n))  # n is a positive integer
    if n < 2:  # 0 and 1 are not primes
        return False
    if n == 2:  # 2 is the only even prime number
        return True
    if not n & 1:  # all other even numbers are not primes
        return False
    # Range starts with 3 and only needs to go up the square root
    # of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

# To apply a function to a numpy array, one have to vectorize the function
vectorized_isprime = np.vectorize(isprime)

a = np.arange(10000000)
primes = a[vectorized_isprime(a)]
#print(primes)
for i in range(2,20):
    print(primes[0:2**i].mean())

Вывод:

4.25
9.625
23.8125
57.84375
138.953125
326.1015625
749.04296875
1695.60742188
3785.09082031
8359.52587891
18298.4733887
39744.887085
85764.6216431
184011.130096
392925.738174
835387.635033
1769455.40302
3735498.24225

Разрыв в последовательности медленно уменьшается с 2,5 до 2. Возможно, эта ассоциация может улучшить Шеллсорт в будущем.