Ottimizzare C++/Tecniche generali di ottimizzazione/Ordinamento: differenze tra le versioni

Wikibooks, manuali e libri di testo liberi.
Contenuto cancellato Contenuto aggiunto
RamaccoloBot (discussione | contributi)
m Bot: Sostituzione automatica (-[[Categoria:Ottimizzare C++|Ottimizzare C++/Tecniche generali di ottimizzazione/ +[[Categoria:Ottimizzare C++|)
Nessun oggetto della modifica
Riga 3: Riga 3:
=== Countingsort ===
=== Countingsort ===


'''Per ordinare un insieme di dati in base a una chiave intera avente un range limitato, usa l'algoritmo [[Implementazioni_di_algoritmi/Counting_sort|countingsort]].'''
'''Per ordinare un insieme di dati in base a una chiave intera avente un range limitato, usa l'algoritmo [[Implementazioni_di_algoritmi/Counting_sort|''counting sort'']].'''


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.
L'algoritmo ''counting sort'' 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.
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 [[w:Quick_sort|''quick sort'']].
In alcuni casi è più veloce anche per range più grandi, fino a 50 N.
In alcuni casi è più veloce anche per range più grandi, fino a 50 N.


Riga 15: Riga 15:
'''Se devi solo dividere una sequenza in due gruppi in base a un criterio, usa un algoritmo di partizionamento, invece di uno di ordinamento.'''
'''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)).
In STL c'è l'algoritmo <code>std::partition</code>, che è più veloce dell'algoritmo <code>std::sort</code>, in quanto ha complessità O(N) invece di O(N log(N)).


=== Partizionamento e ordinamento stabili ===
=== Partizionamento e ordinamento stabili ===
Riga 21: Riga 21:
'''Se devi partizionare o ordinare una sequenza per cui non è richiesto di mantenere l'ordine delle entità equivalenti, non usare un algoritmo stabile.'''
'''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''.
In STL c'è l'algoritmo di partizionamento <code>std::stable_partition</code>, che è leggermente più lento dell'algoritmo <code>std::partition</code>; e c'è l'algoritmo di ordinamento <code>std::stable_sort</code>, che è leggermente più lento dell'algoritmo <code>std::sort</code>.


=== Partizionamento d'ordine ===
=== Partizionamento d'ordine ===
Riga 27: Riga 27:
'''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.'''
'''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)).
In STL c'è l'algoritmo <code>std::nth_element</code>, che, pur essendo leggermente più lento dell'algoritmo <code>std::stable_partition</code>, è notevolmente più veloce dell'algoritmo <code>std::sort</code>, in quanto ha complessità O(N) invece di O(N log(N)).


=== Statistica d'ordine ===
=== Statistica d'ordine ===
Riga 33: Riga 33:
'''Se devi solo ordinare i primi N elementi di una sequenza, usa un algoritmo di statistica d'ordine, invece di un algoritmo di ordinamento.'''
'''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.
In STL ci sono gli algoritmi <code>std::partial_sort</code> e <code>std::partial_sort_copy</code>, che, pur essendo più lenti dell'algoritmo <code>std::nth_element</code>, sono tanto più veloci dell'algoritmo <code>std::sort</code> quanto più è breve la sequenza parziale da ordinare rispetto a quella totale.


[[Categoria:Ottimizzare C++|Ordinamento]]
[[Categoria:Ottimizzare C++|Ordinamento]]
{{Avanzamento|75%|23 maggio 2008}}
{{Avanzamento|100%|25 maggio 2008}}

Versione delle 15:24, 25 mag 2008

Indice del libro

Countingsort

Per ordinare un insieme di dati in base a una chiave intera avente un range limitato, usa l'algoritmo counting sort.

L'algoritmo counting sort 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 quick sort. 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 std::partition, che è più veloce dell'algoritmo std::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 std::stable_partition, che è leggermente più lento dell'algoritmo std::partition; e c'è l'algoritmo di ordinamento std::stable_sort, che è leggermente più lento dell'algoritmo std::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 std::nth_element, che, pur essendo leggermente più lento dell'algoritmo std::stable_partition, è notevolmente più veloce dell'algoritmo std::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 std::partial_sort e std::partial_sort_copy, che, pur essendo più lenti dell'algoritmo std::nth_element, sono tanto più veloci dell'algoritmo std::sort quanto più è breve la sequenza parziale da ordinare rispetto a quella totale.