A proposito di insertion sort e soprattutto perché si dice che la copia è molto più veloce di swap?

2

Da "Strutture dati e algoritmi in Java" di Lafore : (sull'insertion sort (che usa copy + shift anziché swap (usato in bubble e selection sort)))

However, a copy isn’t as time-consuming as a swap, so for random data this algo- rithm runs twice as fast as the bubble sort and faster than the selectionsort.

Inoltre, l'autore non menziona quanto sia dispendioso il turno.

Sembra che la copia sia l'operazione di assegnazione puntatore più semplice. Mentre lo scambio è di 3 operazioni di assegnazione puntatore, che non richiedono molto tempo. Inoltre, lo spostamento di N elementi è N operazioni di assegnazione del puntatore.

Qualcuno può spiegare questa apparente incoerenza?

    
posta dhblah 14.11.2012 - 15:01
fonte

2 risposte

2

a copy isn’t as time-consuming as a swap

Confrontiamo una copia in uno scambio:

int[] a = ...
int idx = ...

// copy:
a[idx] = a[idx + 1];

// swap:
int temp = a[idx];
a[idx] = a[idx + 1];
a[idx + 1] = temp;

Swap assegna una variabile temporanea esegue e tre copie, una dall'array alla variabile temporanea, una da un indice all'array a un'altra e una dalla variabile temporanea all'array. Pertanto uno swap è almeno 3 volte più costoso di una copia.

Spostare elementi in un array (al contrario dei bit di spostamento in un tipo intero primitivo) è costoso perché viene ripetuto copiando:

for (int i = shiftEnd - 1; i >= shiftStart; i--) {
  a[i + 1] = a[i];
}

Puoi vedere qui quando (shiftEnd - shiftStart) > 3 a turno eseguirà più operazioni di copia rispetto a uno scambio.

Diamo un'occhiata allo stesso esempio con una serie di puntatori agli oggetti invece di primitive int:

Object[] a = ...

// copy the pointer to an object from one array element to another
a[idx] = a[idx + 1]; 

// swap the pointer to an object between array elements
Object temp = a[idx];
a[idx] = a[idx + 1];
a[idx + 1] = temp;

Noterai che queste operazioni sono esattamente le stesse sia che si tratti di oggetti primitivi o primitivi. La versione List è più costosa a causa del overhead di chiamata metodo di accesso all'elenco. La maggior parte delle implementazioni di List utilizza matrici multiple per consentire il ridimensionamento dell'elenco che è più costoso rispetto all'utilizzo di una matrice primitiva a lunghezza fissa singola.

    
risposta data 18.11.2012 - 14:54
fonte
1

Non stai facendo uno scambio / copia che stai facendo approssimativamente n log(n) swaps / copie. Quindi ottieni 3n log(n) assegnazioni per lo scambio o n log(n) + n assegnazioni per copia.

    
risposta data 14.11.2012 - 15:11
fonte

Leggi altre domande sui tag