Quicksort e non ti preoccupare?

9

Soprattutto quando si scrivono applicazioni 'standard' (non-HPC), si considera quale algoritmo di ordinamento scegliere, o semplicemente si stabilisce con quicksort (che è ciò che la maggior parte delle librerie chiama semplicemente sort)? In una certa misura può essere redditizio in situazioni specifiche, ma d'altra parte un'adeguata ottimizzazione richiede del tempo per analizzare il problema e fare benchmark.

    
posta mbq 21.09.2010 - 00:19
fonte

6 risposte

12

In generale, l'utilizzo dei metodi predefiniti a meno che non vi sia un'esigenza specifica di fare qualcosa di più esotico mantiene tutto molto più leggibile / comprensibile lungo la strada. IMHO.

Se riscontri (o in alcuni casi, strongmente sospetto) che hai un problema di prestazioni che è il momento di aggiungere complessità.

D'altra parte, se stai usando un linguaggio abbastanza basso che non esiste un ordinamento predefinito per il tipo di oggetti che devi ordinare prova a sceglierne uno o due che coprano tutte le basi e implementali.

    
risposta data 21.09.2010 - 00:24
fonte
6

Chiama sempre le routine di libreria fornite, a meno che tu non abbia una ragione molto buona per non farlo (e hai bisogno di document perché è così).

Questo perché gli algoritmi di ordinamento sono difficili da avere assolutamente ragione. C'era un bug nel quicksort Java con dataset molto grandi, che è stato identificato, risolto e consegnato ai clienti da Sun, quindi non era necessario.

Anche l'ordinamento predefinito in Java 7 è stato aggiornato a un ordinamento nuovo e migliore. Anche gratis.

A meno che l'ordinamento predefinito provabilmente non sia abbastanza buono per te, seguilo.

    
risposta data 22.12.2010 - 11:52
fonte
3

Durante una conferenza, ho sentito una bella storia su questo.

In Microsoft qualcuno stava scrivendo un'app VB (c. VB 3) e spedito un gruppo di persone che dicevano che aveva un sacco di valori e voleva che comparissero nella combobox in ordine, come avrebbe dovuto farlo.

Tutti si sono tuffati per i loro vecchi libri di testo di informatica, cercando routine altamente efficienti e portandole a Visual Basic e spedendole a lui. Un tizio ha appena risposto "quanti valori nella casella combinata?".

"Circa 50" è arrivata la risposta.

"Basta impostare la proprietà ordinata su TRUE".

Nel 99.9999% delle ordinazioni, l'ordinamento è fatto meglio usando una libreria, controllo o in SQL selezionare come la differenza di prestazioni tra la routine di libreria e qualsiasi cosa scritta sarà trascurabile e il sovraccarico di sforzo e manutenzione supererà in modo massivo le conseguenze. / p>     

risposta data 22.12.2010 - 14:27
fonte
1

Questo è il momento di tirare fuori la citazione classica sull'ottimizzazione prematura. Nella maggior parte dei casi, non importa. Diamine, con la velocità delle CPU in questi giorni, si potrebbe probabilmente ordinare la maggior parte dei set di dati e non notare molto. Ma quando si ordinano set di dati veramente grandi e le prestazioni di ordinamento iniziano a diventare un problema, allora si dovrebbe assolutamente guardare ad altre opzioni.

    
risposta data 21.09.2010 - 00:23
fonte
0

Anche se ovviamente non ha importanza per bit e tempi. Trovo che l'unione di ordinamento sia più facile da scrivere e capire rispetto a quicksort. Quindi, se ho intenzione di scrivere il mio algoritmo di ordinamento, lo userei.

    
risposta data 21.09.2010 - 00:21
fonte
0

Almeno in una libreria scritta in modo competente, mi aspetto che la% di conversione incorporata in% sia implementata come Introsort anziché solo Quicksort. La differenza raramente conta molto, ma Introsort elimina le peggiori prestazioni nel caso peggiore di Quicksort con un effetto minimo sui casi più comuni.

Per rispondere alla tua domanda, tuttavia: sì - questo è quello che dovresti iniziare di solito, e finché / a meno che non ci siano risultati del profiler che indicano che si tratta di un problema, è lì che dovrebbe rimanere.

    
risposta data 21.09.2010 - 00:51
fonte

Leggi altre domande sui tag