Ottimizzare C++/Tecniche generali di ottimizzazione/Ordinamento: differenze tra le versioni
Nessun oggetto della modifica |
m Bot: Sostituzione automatica (-[[Categoria:Ottimizzare C++|Ottimizzare C++/Tecniche generali di ottimizzazione/ +[[Categoria:Ottimizzare C++|) |
||
Riga 35: | Riga 35: | ||
In STL ci sono gli algoritmi ''partial_sort'' e ''partial_sort_copy'', che, pur essendo più lenti dell'algoritmo ''nth_element'', sono tanto più veloci dell'algoritmo sort quanto più è breve la sequenza parziale da ordinare rispetto a quella totale. |
In STL ci sono gli algoritmi ''partial_sort'' e ''partial_sort_copy'', che, pur essendo più lenti dell'algoritmo ''nth_element'', sono tanto più veloci dell'algoritmo sort quanto più è breve la sequenza parziale da ordinare rispetto a quella totale. |
||
[[Categoria:Ottimizzare C++| |
[[Categoria:Ottimizzare C++|Ordinamento]] |
||
{{Avanzamento|75%|23 maggio 2008}} |
{{Avanzamento|75%|23 maggio 2008}} |
Versione delle 15:37, 24 mag 2008
Countingsort
Per ordinare un insieme di dati in base a una chiave intera avente un range limitato, usa l'algoritmo countingsort.
L'algoritmo countingsort ha complessità O(N+M), dove N è il numero di elementi da ordinare e M è il range delle chiavi di ordinamento, cioè la differenza tra la chiave massima e la chiave minima. Nel caso in cui si vogliano ordinare N elementi la cui chiave è un numero intero appartenente a un intervallo di non oltre 2 N valori, questo algoritmo può essere notevolmente più veloce di quicksort. In alcuni casi è più veloce anche per range più grandi, fino a 50 N.
Questo algoritmo può essere usato anche per un ordinamento parziale; per esempio, se la chiave è un intero compreso tra zero e un miliardo, si può ordinare solamente in base al byte più significativo della chiave, così da ottenere un ordine tale per cui per ogni n vale la formula
Partizionamento
Se devi solo dividere una sequenza in due gruppi in base a un criterio, usa un algoritmo di partizionamento, invece di uno di ordinamento.
In STL c'è l'algoritmo partition, che è più veloce dell'algoritmo sort, in quanto ha complessità O(N) invece di O(N log(N)).
Partizionamento e ordinamento stabili
Se devi partizionare o ordinare una sequenza per cui non è richiesto di mantenere l'ordine delle entità equivalenti, non usare un algoritmo stabile.
In STL c'è l'algoritmo di partizionamento stable_partition, che è leggermente più lento dell'algoritmo partition; e c'è l'algoritmo di ordinamento stable_sort, che è leggermente più lento dell'algoritmo sort.
Partizionamento d'ordine
Se devi solo individuare i primi N elementi di una sequenza, o l'N-esimo elemento di una sequenza, usa un algoritmo di partizionamento d'ordine, invece di un ordinamento.
In STL c'è l'algoritmo nth_element, che, pur essendo leggermente più lento dell'algoritmo stable_partition, è notevolmente più veloce dell'algoritmo sort, in quanto ha complessità O(N) invece di O(N log(N)).
Statistica d'ordine
Se devi solo ordinare i primi N elementi di una sequenza, usa un algoritmo di statistica d'ordine, invece di un algoritmo di ordinamento.
In STL ci sono gli algoritmi partial_sort e partial_sort_copy, che, pur essendo più lenti dell'algoritmo nth_element, sono tanto più veloci dell'algoritmo sort quanto più è breve la sequenza parziale da ordinare rispetto a quella totale.