Ottimizzare C++/Tecniche generali di ottimizzazione/Ordinamento

Wikibooks, manuali e libri di testo liberi.
Ottimizzare C++
modifica
CopertinaOttimizzare C++/Copertina
  1. IntroduzioneOttimizzare C++/Introduzione
  2. Ciclo di vita dell’ottimizzazioneOttimizzare C++/Ciclo di vita dell’ottimizzazione
  3. Scrivere codice C++ efficienteOttimizzare C++/Scrivere codice C++ efficiente
    1. Costrutti che migliorano le prestazioniOttimizzare C++/Scrivere codice C++ efficiente/Costrutti che migliorano le prestazioni
    2. Costrutti che peggiorano le prestazioniOttimizzare C++/Scrivere codice C++ efficiente/Costrutti che peggiorano le prestazioni
    3. Costruzioni e distruzioniOttimizzare C++/Scrivere codice C++ efficiente/Costruzioni e distruzioni
    4. Allocazioni e deallocazioniOttimizzare C++/Scrivere codice C++ efficiente/Allocazioni e deallocazioni
    5. Accesso alla memoriaOttimizzare C++/Scrivere codice C++ efficiente/Accesso alla memoria
    6. Uso dei threadOttimizzare C++/Scrivere codice C++ efficiente/Uso dei thread
  4. Tecniche generali di ottimizzazioneOttimizzare C++/Tecniche generali di ottimizzazione
    1. Input/OutputOttimizzare C++/Tecniche generali di ottimizzazione/Input/Output
    2. CachingOttimizzare C++/Tecniche generali di ottimizzazione/Caching
    3. OrdinamentoOttimizzare C++/Tecniche generali di ottimizzazione/Ordinamento
    4. Altre tecnicheOttimizzare C++/Tecniche generali di ottimizzazione/Altre tecniche
  5. Ottimizzazione del codice C++Ottimizzare C++/Ottimizzazione del codice C++
    1. Allocazione e deallocazioneOttimizzare C++/Ottimizzazione del codice C++/Allocazione e deallocazione
    2. Supporto run-timeOttimizzare C++/Ottimizzazione del codice C++/Supporto run-time
    3. Numero di istruzioniOttimizzare C++/Ottimizzazione del codice C++/Numero di istruzioni
    4. Costruzioni e distruzioniOttimizzare C++/Ottimizzazione del codice C++/Costruzioni e distruzioni
    5. PipelineOttimizzare C++/Ottimizzazione del codice C++/Pipeline
    6. Accesso alla memoriaOttimizzare C++/Ottimizzazione del codice C++/Accesso alla memoria
    7. Operazioni velociOttimizzare C++/Ottimizzazione del codice C++/Operazioni veloci

Countingsort[modifica]

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 contenente un numero di valori non superiore al doppio di N (cioè quando vale M <= 2 * N), questo algoritmo può essere notevolmente più veloce di quick sort. In alcuni casi è più veloce anche per range più grandi.

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 a_n < a_{n + 1} + 256*256*256.

Partizionamento[modifica]

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[modifica]

Se devi partizionare oppure 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[modifica]

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 uno di 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[modifica]

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.