Sequenza di spazi più veloce per l'ordinamento di shell?

Question

Secondo Marcin Ciura Optimal (best known) sequence of increments for shell sort algorithm, la sequenza migliore per shellsort è 1, 4, 10, 23, 57, 132, 301, 701 ..., ma come posso generare tale sequenza? In carta di Marcin Ciura, disse:

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

ma la maggior parte dei libri di algoritmi che ho trovato tendono a utilizzare la sequenza di Knuth: 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 limite superiore definito in dimensioni, è possibile hardcode la sequenza di passi. Probabilmente dovresti preoccuparti solo della generalità se è probabile che il tuo set di dati cresca senza limite superiore.

La sequenza mostrata sembra crescere più o meno come una serie esponenziale, anche se con stranezze. Sembra che ci sia una maggioranza di numeri primi, ma anche con i non-primi nel mix. Non vedo una formula di generazione ovvia.

Una domanda valida, supponendo che sia necessario gestire insiemi di dimensioni arbitrarie, è se è necessario dare risalto alle prestazioni nel caso peggiore, alle prestazioni nella media o alle prestazioni quasi ordinate. Se quest'ultimo, si può scoprire che un ordinamento di inserimento semplice utilizzando una ricerca binaria per la fase di inserimento potrebbe essere migliore di un shellsort. Se hai bisogno di buone prestazioni nel peggiore dei casi, la sequenza di Sedgewick sembra essere favorita. La sequenza che citi è ottimizzata per le prestazioni a medio termine, dove il numero di confronti supera il numero di mosse.

Answer 2

La carta di Ciura genera empiricamente la sequenza, cioè ha provato un sacco di combinazioni e questa è stata quella che ha funzionato al meglio. Generare una sequenza shellsort ottimale si è dimostrata complicata e il problema è stato finora resistente all'analisi.

L'incremento più noto è Sedgewick's, che è possibile leggere su (vedere pagina 7).

Answer 3

non vergognerei a prendere i consigli forniti in Shellsort articolo di Wikipedia,

Rispetto al numero medio di confronti, il gap più noto sequenze sono 1, 4, 10, 23, 57 , 132, 301, 701 e simili, con lacune trovate sperimentalmente. Le lacune ottimali oltre 701 rimangono sconosciute, ma i buoni risultati possono essere ottenuti estendendo la sequenza sopra riportata in base a la formula ricorsiva h_k = \ lfloor 2.25 h_ {k-1} \ rfloor.

Sequenza di Tokuda [1, 4, 9, 20, 46, 103, ...], definita dalla semplice formula h_k = \ lceil h'_k \ rceil, dove h'k = 2,25h'k - 1 + 1, h'1 = 1, può essere raccomandato per le applicazioni pratiche .

indovinando dallo pseudonimo, sembra che Marcin Ciura abbia modificato l'articolo del WP stesso.

Answer 4

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

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 

Si tratta di una media di 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 divario nella sequenza si sta lentamente diminuendo da 2,5 a 2. Forse questa associazione potrebbe migliorare la Shellsort nel futuro.