algorithm - queso - ¿La secuencia de huecos más rápida para la ordenación de la concha?

queso con hoyos nombre

Question

De acuerdo con la secuencia Óptima (más conocida) de Marcin Ciura de incrementos para el algoritmo de ordenación de concha , la mejor secuencia para la concha es 1, 4, 10, 23, 57, 132, 301, 701 ..., pero ¿cómo puedo generar tal secuencia? ? En el artículo de Marcin Ciura, dijo:

Tanto la secuencia de Knuth como la de Hibbard son relativamente malas, porque están definidas por recurrencias lineales simples.

pero la mayoría de los libros de algoritmos que encontré tienden a usar la secuencia de Knuth: k = 3k + 1, porque es fácil de generar. ¿Cuál es tu forma de generar una secuencia de shellsort?

Answer 1

Ayer discutí esta pregunta here incluyendo las secuencias de huecos que he encontrado que funcionan mejor dada una n específica (baja).

En el medio escribo

Un efecto secundario desagradable de shellsort es que al usar un conjunto de combinaciones aleatorias de n entradas (para ahorrar tiempo de procesamiento / evaluación) para probar las brechas puede terminar con las mejores brechas para n entradas o las mejores brechas para su conjunto de combinaciones - muy probablemente el último.

El problema radica en probar los vacíos propuestos de manera que se puedan extraer conclusiones válidas. Obviamente, probando las brechas contra todos n! ordenando que un conjunto de n valores únicos pueda expresarse como no factible. La prueba de esta manera para n = 16, por ejemplo, significa que se deben clasificar 20,922,789,888,000 combinaciones diferentes de n valores para determinar el promedio exacto, los casos peores y los ordenados en orden inverso, solo para probar un conjunto de brechas y ese conjunto podría no ser el adecuado. mejor. 2 ^ (16-2) conjuntos de huecos son posibles para n = 16, el primero es {1} y el último {15,14,13,12,11,10,9,8,7,6,5,4 , 3,2,1}.

Para ilustrar cómo el uso de combinaciones aleatorias puede dar resultados incorrectos, suponga que n = 3 puede asumir seis ordenamientos diferentes 012, 021, 102, 120, 201 y 210. Produce un conjunto de dos secuencias aleatorias para probar los dos conjuntos de huecos posibles, {1 } y {2,1}. Supongamos que estas secuencias resultan ser 021 y 201. Para {1} 021 se pueden clasificar con tres comparaciones (02, 21 y 01) y 201 con (20, 21, 01) dando un total de seis comparaciones, divididas por dos y voilà, un promedio de 3 y el peor de los casos 3. Usando {2,1} da (01, 02, 21 y 01) para 021 y (21, 10 y 12) para 201. Siete comparaciones con el peor caso de 4 y un promedio de 3.5. El promedio real y el caso más desfavorable para {1] es 8/3 y 3, respectivamente. Para {2,1} los valores son 10/3 y 4. Los promedios fueron demasiado altos en ambos casos y los peores casos fueron correctos. Si 012 hubiera sido uno de los casos, {1} hubiera dado un promedio de 2.5 - demasiado bajo.

Ahora extienda esto para encontrar un conjunto de secuencias aleatorias para n = 16, de modo que no se favorezca ningún conjunto de huecos analizados en comparación con los demás y el resultado sea cercano (o igual) a los valores reales, manteniendo el procesamiento al mínimo. . Se puede hacer? Posiblemente. Después de todo, todo es posible, pero ¿es probable? Creo que para este problema aleatorio es el enfoque equivocado. La selección de las secuencias de acuerdo con algún sistema puede ser menos mala e incluso puede ser buena.

Answer 2

El artículo de Ciura genera la secuencia empíricamente, es decir, probó varias combinaciones y esta fue la que mejor funcionó. La generación de una secuencia óptima de shells ha demostrado ser complicada, y el problema hasta ahora ha sido resistente al análisis.

El incremento más conocido es Sedgewick''s, que puede leer here (vea la página 7).

Answer 3

He encontrado esta secuencia similar a la secuencia de Marcin Ciura:

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

Por ejemplo, la secuencia de Ciura es:

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

Esta es una media de números primos. El código de Python para encontrar la media de los números primos está aquí:

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())

La salida es:

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

La brecha en la secuencia está disminuyendo lentamente de 2.5 a 2. Tal vez esta asociación podría mejorar el Shellsort en el futuro.

Answer 4

La secuencia es 1, 4, 10, 23, 57, 132, 301, 701, 1750. Por cada número siguiente después de 1750, multiplique el número anterior por 2.25 y redondee hacia abajo.

Answer 5

No me avergonzaría tomar el consejo dado en el artículo Shellsort Wikipedia,

Con respecto al número promedio de comparaciones, las mejores secuencias de huecos conocidas son 1, 4, 10, 23, 57, 132, 301, 701 y similares, con huecos encontrados experimentalmente. Las brechas óptimas más allá de 701 siguen siendo desconocidas, pero se pueden obtener buenos resultados extendiendo la secuencia anterior de acuerdo con la fórmula recursiva h_k = / lfloor 2.25 h_ {k-1} / rfloor.

La secuencia de Tokuda [1, 4, 9, 20, 46, 103, ...], definida por la fórmula simple h_k = / lceil h''_k / rceil, donde h''k = 2.25h''k - 1 + 1, h ''1 = 1, se puede recomendar para aplicaciones prácticas.

adivinando por el seudónimo, parece que Marcin Ciura editó el artículo de WP.

Answer 6

Si su conjunto de datos tiene un límite superior definido en tamaño, puede codificar la secuencia de pasos. Es probable que solo deba preocuparse por la generalidad si es probable que su conjunto de datos crezca sin un límite superior.

La secuencia mostrada parece crecer aproximadamente como una serie exponencial, aunque con peculiaridades. Parece que hay una mayoría de números primos, pero con no primos en la mezcla también. No veo una fórmula de generación obvia.

Una pregunta válida, suponiendo que debe lidiar con conjuntos arbitrariamente grandes, es si necesita enfatizar el desempeño en el peor de los casos, el desempeño promedio del caso o el desempeño casi ordenado. Si es lo último, puede encontrar que una ordenación de inserción simple mediante una búsqueda binaria para el paso de inserción podría ser mejor que una orden común. Si necesita un buen desempeño en el peor de los casos, la secuencia de Sedgewick parece ser favorecida. La secuencia que mencionas está optimizada para el rendimiento de caso promedio, donde el número de comparaciones supera el número de movimientos.