L'inserimento ordina molto più velocemente del genere Shell

Question

Sto leggendo il capitolo sull'ordinamento degli "algoritmi" di Sedgewick. Lungo il modo in cui ho scritto 3 algoritmi di base per l'ordinamento: selezione, inserimento e shell sort. Il libro dice, che, nonostante tutti e tre hanno la complessità dei casi peggiore quadratica, il tipo di shell dovrebbe essere molto più veloce del tipo di inserimento sui dati casuali. Nel libro ottengono 600x performance boost.

Ma ottengo i seguenti moltiplicatori (quasi non cambiano con l'aumento della dimensione dell'array) sul mio laptop:

.
• > Selezione: 5.5x
• Inserimento: 1x
• shell: 1.8x!

La domanda che mi infastidisce è - perché il tipo di shell è quasi due volte più lento, del tipo di inserimento?!

Immagino, qualcosa non va nel mio implementazione della mia shellsort. Ma l'ho quasi copiato dal libro:

class ShellSort extends Sort {
    //precalculate sequence: 1, 4, 13, 40, 121, 364, 1093, ...
    //(3^20 - 1)/2 is enough for any array I sort
    private static final int[] SEQUENCE = new int[20];
    static {
        for(int i = 1; i <= SEQUENCE.length; i++)
            SEQUENCE[i - 1] = (int)(Math.pow(3, i) - 1) / 2;
    }

    public void sort(int[] a) {
        int length = a.length;

        int seqLen = SEQUENCE.length;
        int nth;
        int j;

        for(int seqi = seqLen - 1; seqi >= 0; seqi--) {
            if(SEQUENCE[seqi] < length / 3) {
                nth = SEQUENCE[seqi];
                for(int n = 0; n < length; n+=nth) {
                    j = n;
                    while(j > 0 && a[j] < a[j - nth]) {
                        exch(a, j, j-nth);
                        j -= nth;
                    }
                }
            }
        }
    }
}

.

resto del codice per quelli che vorrebbero eseguire il test sulla loro macchina (raddoppiare il test delle dimensioni dell'array con il calore JVM non ha alcun effetto significativo sui risultati, quindi questo semplice test è abbastanza buono per N> ~ 200 000) .

Main:

int N = 500_000;
Random rand = new Random();
int[] a = new int[N];
for(int i = 0; i < N; i++)
    a[i] = rand.nextInt();

//insertion sort
int[] aCopy = Arrays.copyOf(a, a.length);
long start = System.nanoTime();
new InsertionSort().sort(aCopy);
System.out.println("insert:\t" + (System.nanoTime() - start));

//shell sort
aCopy = Arrays.copyOf(a, a.length);
start = System.nanoTime();
new ShellSort().sort(aCopy);
System.out.println("shell:\t" + (System.nanoTime() - start));

.

inseritionsort e classi classi:

class InsertionSort extends Sort {
    public void sort(int[] a) {
        int length = a.length;
        int j;
        int x;
        for(int i = 1; i < length; i++) {
            j = i;
            x = a[i];
            while(j > 0 && x < a[j-1]) {
                a[j] = a[--j];
            }
            a[j] = x;
        }
    }
}
abstract class Sort {
    abstract public void sort(int[] a);

    protected static final void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

.

Answer 1

La tua implementazione è rotta e emette l'array ordinato solo a causa del fatto che l'ultimo passaggio è 1 e i due cicli interni eseguono l'ordinamento di inserimento di base quando il passaggio è 1. Quando il passaggio è maggiore di 1, i due cicli interni nella tua implementazione fanno altro che passo-ordina l'array, quindi ciò che implementa la realizzazione è mescolare l'array in tutte le iterazioni del ciclo esterno e quindi l'inserimento-lo ordina nell'ultimo Iterazione del ciclo esterno. Ovviamente ci vorrà più tempo, quindi solo inserimento, ordinalo una volta.

Riutilizzo della sequenza La corretta implementazione della shell ordinamento dovrebbe assomigliare a questo:

public void sort( int[] a ) {
    int length = a.length;

    int stepIndex = 0;
    while ( stepIndex < SEQUENCE.length - 1 && SEQUENCE[ stepIndex ] < length / 3 ) {
        stepIndex++;
    }

    while ( stepIndex >= 0 ) {
        int step = SEQUENCE[ stepIndex-- ];
        for ( int i = step; i < length; i++ ) { // DIFF: i++ instead of i+=step
            for ( int j = i; j >= step && a[ j ] < a[ j - step ]; j -= step ) {
                exch( a, j, j - step );
            }
        }
    }
}

.

Due principali differenze tra questa attuazione e la tua:

.
• Indici iniziali corretti per due cicli interni
• Affremento indice appropriato per il ciclo medio (+1 anziché + passo nel tuo codice)

Inoltre, controlla il http://algs4.cs.princeton.edu/ 21elementary / shell.java.html per una buona implementazione e una buona sequenza passo.

Answer 2

Da una rapida occhiata puoi vedere che la shell ordinamento sembra più lento con più anelli. Forza bruta, puoi mettere un sistema.out.Println nel ciclo più interno per vedere quanti confronti sono fatti.

3 loop di shellsort

.
• per (int seqi= seqlen - 1; seqi>= 0; seqi -)
• per (int n= 0; n
• while (j> 0 && a [j]

2 anelli di inserimento

.
• per (int i= 1; i
• while (j> 0 && x

Answer 3

Credo che la ragione sarebbe la memorizzazione nella cache.Shell Ordinty ha un sacco di (kinda) Accessi a caso in modo che più manca di cache.Credo che darebbe prestazioni peggiori con i nuovi hardware.L'inserimento Ordina praticamente funziona sempre sulle stesse aree di memoria in modo da eseguire meglio