Veloce sequenza gap per le coperture di tipo?

Question

Secondo ottimale (più noto) sequenza di incrementi per algoritmo shell sort , la sequenza migliore per Shellsort è 1, 4, 10, 23, 57, 132, 301, 701 ..., ma come posso generare una tale sequenza? Nel documento di Marcin Ciura, ha detto:

  

Sia le sequenze di Knuth e Hibbard di   sono relativamente male, perché sono   definita da semplici ricorrenze lineari.

, ma la maggior parte dei libri di algoritmi che ho trovato tendono ad usare di Knuth sequenza: k = 3k + 1, perché è facile da generare. Qual è il tuo modo di generare una sequenza Shellsort?

Answer 1

Se il set di dati ha un preciso limite superiore in termini di dimensioni, allora si può hardcode la sequenza di passi. Probabilmente si dovrebbe preoccupare solo di generalità se il set di dati è destinata a crescere senza un limite superiore.

La sequenza mostrata sembra crescere all'incirca come una serie esponenziale, seppur con peculiarità. Sembra che ci sia una maggioranza di numeri primi, ma con i non-numeri primi nel mix pure. Non vedo una formula ovvia generazione.

Una domanda valida, supponendo che si deve trattare con arbitrariamente grandi insiemi, è se è necessario sottolineare le prestazioni nel caso peggiore, le prestazioni nel caso medio, o le prestazioni quasi-ordinato. In quest'ultimo caso, è possibile che un inserimento semplice ordinare utilizzando una ricerca binaria per la fase di inserimento potrebbe essere migliore di uno Shellsort. Se avete bisogno di buone prestazioni nel caso peggiore, poi la sequenza di Sedgewick sembra essere favorita. La sequenza si parla è ottimizzato per le prestazioni nel caso medio, in cui il numero di confronti è superiore al numero di mosse.

Answer 2

L'articolo di Ciura genera la sequenza empiricamente - che è, ha cercato un po 'di combinazioni e questo era quello che ha funzionato al meglio. Generando una sequenza ottimale shellsort ha dimostrato di essere difficile, e il problema è stato finora resistente ad analisi.

L'incremento più noto è Sedgewick di, che si può leggere su qui (vedi pag. 7).

Answer 3

Non mi vergognerei di prendere i consigli forniti in di Wikipedia Shellsort articolo,

  

Per quanto riguarda il numero medio di confronti, il divario più conosciuto   sequenze sono 1, 4, 10, 23, 57, 132, 301, 701 e simili, con lacune   sperimentalmente. lacune ottimali oltre 701 rimangono sconosciute, ma buono   risultati possono essere ottenuti estendendo la sequenza sopra secondo   la formula ricorsiva h_k = \ lfloor 2.25 h_ {k-1} \ rfloor.

     

di Tokuda sequenza [1, 4, 9, 20, 46, 103, ...], definito dalla semplice formula h_k = \ lceil h'_k   \ Rceil, dove h'K = 2.25h'k - 1 + 1, h'1 = 1, può essere raccomandato per   applicazioni pratiche.

indovinando dalla pseudonimo, sembra Marcin Ciura modificato l'articolo WP se stesso.

Answer 4

La sequenza è 1, 4, 10, 23, 57, 132, 301, 701, 1750. Per ogni numero successivo dopo il 1750 precedente Numero moltiplicare per 2,25 e arrotondare.

Answer 5

Ho trovato questa sequenza simile a quella sequenza di Marcin Ciura:

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

Per esempio, la sequenza di Ciura è:

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

Questa è una media dei numeri primi. Python codice per trovare media dei numeri primi è qui:

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

L'output è:

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

Il gap nella sequenza viene lentamente ridotta rispetto 2.5 a 2. Forse questa associazione potrebbe migliorare la Shellsort in futuro.

Answer 6

ho discusso questa domanda qui ieri comprese le sequenze di gap che ho trovato lavoro migliore dato una specifica (basso) n.

Nel mezzo scrivo

  

Un brutto effetto collaterale di Shellsort è che quando si utilizza una serie di casuali   combinazioni di n immissioni (per risparmiare elaborazione / tempo di valutazione) per testare   lacune si può finire sia con i migliori lacune per n voci o la   migliori lacune per il set di combinazioni -. Molto probabilmente la seconda

Il problema sta nel testare le lacune proposte in modo tale che conclusioni valide si possono trarre. Ovviamente, testando le lacune nei confronti di tutti gli n! ordinamenti che un insieme di valori n univoci possono essere espressi come è irrealizzabile. Test in questo modo per n = 16, per esempio, significa che 20,922,789,888,000 diverse combinazioni di n valori devono essere scelti per determinare la media esatta, peggiore e reverse-filtrate casi - solo per testare una serie di lacune e che insieme non potrebbe essere la migliore. 2 ^ (16-2) serie di lacune sono possibili per n = 16, il primo essere {1} e l'ultimo {15,14,13,12,11,10,9,8,7,6,5,4 , 3,2,1}.

Per illustrare come utilizzare combinazioni casuali potrebbe fornire risultati non corretti assumono n = 3 che può assumere sei diversi ordinamenti 012, 021, 102, 120, 201 e 210. Si producono un insieme di due sequenze casuali per testare i due possibili insiemi gap , {1} e {2,1}. Presuppongono che queste sequenze risultano essere 021 e 201. per {1} 021 possono essere filtrate con tre confronti (02, 21 e 01) e 201 con (20, 21, 01) per un totale di sei confronti, dividere per due e voilà, una media di 3 e un caso peggiore di 3. Utilizzando {2,1} dà (01, 02, 21 e 01) per la 021 e (21, 10 e 12) per 201. Sette confronto con un caso peggiore di 4 e una media di 3.5. La media effettiva e caso peggiore per {1] è rispettivamente 8/3 e 3,. Per {2,1} i valori sono 10/3 e 4. Le medie sono troppo elevati in entrambi i casi ed i casi peggiori erano corrette. Era 012 stato uno dei casi {1} avrebbe dato una media di 2,5 -. Troppo bassa

Ora estendere questo per trovare un insieme di sequenze casuali per n = 16 tale che nessun insieme di lacune testate sarà favorito rispetto agli altri e il risultato chiudere (o uguale) ai valori veri, pur mantenendo trasformazione al minimo. Può essere fatto? Possibilmente. Dopo tutto, tutto è possibile - ma è probabile? Credo che per questo problema casuale è l'approccio sbagliato. Selezione delle sequenze in base a qualche sistema può essere meno male e potrebbe anche essere buono.