Shell vs. Confronto di complessità del tempo di Hibbard

Question

Sto facendo un esperimento per confrontare come l'ordinamento di shell di Thomas Hibbard (dimensione del gap = 2^k-1) e l'ordinamento di shell di Donald Shell (n/2^k) si eseguano sullo stesso array. Quando la dimensione dell'array è tra 10 e 1000, Hibbard sta andando meglio della shell. Ma quando la dimensione raggiunge 10000 o superiore, l'ordinamento di shell è più veloce di Hibbard.

In base alla notazione O grande, Hibbard è O (N^1.5), Shell è O (N^2), il che mi fa pensare che Hibbard dovrebbe avere maggiori miglioramenti rispetto a Shell all'aumentare delle dimensioni del set di dati. Qualcuno può dirmi perché i miei risultati potrebbero non essere come previsto?

Capisco che la notazione O è la peggiore delle ipotesi, ma sembra che le prestazioni siano meglio allineate alla notazione.

Ecco il mio codice scritto in Java: (nota: unsortedArray viene dichiarato e inizializzato in precedenza)

{ 
    int temp; 
    int[] sortedArray = unsortedArray.clone(); 
    printArray(); 
    int k = (int)(Math.log(sortedArray.length)/Math.log(2)); 
    int gap = (int)(Math.pow(2,k)-1); 
    int count = 0; 
    long endTime; 
    long startTime = System.nanoTime(); 

    while (gap > 0) 
    { 
     for (int g = 0; g < gap; g++) 
     { 
      for (int d = g + gap; d < sortedArray.length; d = d + gap) 
      { 
       for (int i = d; i - gap >= 0; i = i - gap) 
       {       
        if (sortedArray[i - gap] <= (sortedArray[i])) 
        { 
         break; 
        } 
        count++; 
        temp = sortedArray[i]; 
        sortedArray[i] = sortedArray [i-gap]; 
        sortedArray[i-gap] = temp; 

       } 
      } 
     } 

     k = k -1; 
     gap = (int)(Math.pow(2,k)-1); 
    } 
    endTime = System.nanoTime(); 
    System.out.println("The total time for hibbard sort is" + (endTime-startTime)); 
    System.out.println("the number of swaps for hibbard sort is" + count); 
} 

Answer 1

penso che la performance potrebbe essere influenzata da JVM, quindi sarebbe meglio per misurare in un altro linguaggio come C o C++.

Maggiori informazioni su algoritmo di ordinamento Shell in Java, C++ e C# potrebbe essere trovato qui:

http://www.programming-algorithms.net/article/41653/Shell-sort

e informazioni su misura algoritmo di complessità è qui:

http://www.programming-algorithms.net/article/44682/Asymptotic-complexity

speranza che aiuta.

Answer 2

Misurare la differenza di complessità temporale tra questi due algoritmi di generazione gap è in realtà un po 'più complicato di così.

Considerare di fornire entrambi una sequenza ordinata di dati e assumere n = 8. Per Shell otteniamo una sequenza vuota di {4,2,1} e per Hibbard {7,3,1}. Per eseguire la sequenza ordinata richiederebbe (Shell) (n-4) + (n-2) + (n-1) o 17 confronti e (Hibbard) (n-7) + (n-3) + (n- 1) o 13.

È ovvio che non è possibile trarre la conclusione che Hibbard eseguirà nel 13/17 del tempo di Shell assegnando una sequenza casuale di n elementi.

Si può scoprire che una determinata sequenza generata casualmente risulta essere più adatta per essere ordinata utilizzando Shell rispetto a Hibbard o viceversa. L'unico modo per determinare quale è meglio è testare tutte le possibili combinazioni di sequenze di dati e calcolare il numero medio di confronti che richiedono. Questo è fatto abbastanza facilmente quando n = 8 (solo n! O 40320 combinazioni) ma ... "più" diffcult quando n = 100 o 1000.

A Shellsort su tutte le sequenze possibili quando n = 8 utilizzando i due spazi vuoti sopra (per inserzione e migliore gap shellsort inclusi per confronto)

     number of comparisons when n=8 
gap sequence   minimum average maximum reverse 
{1} (insertion sort)  7  19.28  28  28 
{5,1} (best gap)   10  17.4  24  15 
{4,2,1} (Shell)   17  21.82  30  22 
{7,3,1} (Hibbard)  13  18.57  24  20 

Così, nel caso di n = 8 Hibbard è molto meglio di Shell, meglio di inserzione ma peggiore della migliore sequenza gap. È interessante notare che, per il miglior gap, l'ordinamento di una sequenza inversa di dati è più veloce del caso medio!

Se osserviamo n = 14 troviamo che Shell e Hibbard risultano nella stessa sequenza, {7,3,1} - dove ovviamente nessuno degli algoritmi sarà migliore dell'altro - e ad n = 16 otteniamo { 8,4,2,1} e {15,7,3,1}, rispettivamente.Ciò si traduce in un caso molto migliore per Hibbard (n * 4) - (15 + 7 + 3 + 1) o 38 confronti rispetto a Shell (n * 4) - (8 + 4 + 2 + 1) o 49.

Quale sarà migliore dell'altra come n aumenta? Mi sembra che la migliore sequenza di gap dipenda da n che dovrebbe dare un vantaggio a Shell poiché Hibbard, ad esempio, ha la stessa sequenza {7,3,1} quando 8 < = n < 16 e {15,7, 3,1} quando 16 < 32: in pratica "taglia unica".

Shellsort vuole spostare valori distanti tra loro per il gap iniziale (s) e mentre quello può essere vero per Hibbard quando n = 16, 17 o 18 e il gap è 15 è molto meno vero quando n si avvicina al limite superiore 31.

Tuttavia, ciò non significa che Shell produca sequenze di interruzioni migliori. Il primo gap di n/2 sarà sempre ostacolato dagli stessi problemi del gap iniziale di Hibbard mentre n si avvicina al limite superiore per la sequenza.

Quindi la mia ipotesi è che Shell fornirà risultati stabili peggiori di Hibbard e probabilmente anche di tipo di inserimento. I risultati di Hibbard dai limiti inferiore a quello superiore n per il gap iniziale aumenteranno in modo sproporzionato. Da qualche parte, mentre n si avvicina al limite superiore n, anche Hibbard comincerà a peggiorare rispetto all'inserimento sort.

Oltre al calcolo dei valori degli spazi, è necessario determinare anche il numero di spazi. Come mostrato in precedenza, due spazi vuoti sono sufficienti quando n = 8 ma sarà vero anche quando n = 10 o più? Ad esempio, da 2 < = n < 6 un ordinamento di inserimento sarà più veloce di qualsiasi shellsort, ma da n = 6 due intervalli consente a Shellsort di battere l'ordinamento di inserimento.