Differenze tra le versioni di "Ottimizzare C++/Tecniche generali di ottimizzazione"

== Altre tecniche ==
 
=== Lettere maiuscole e minuscole ===
=== Prima di confrontare una stringa con una serie di altre stringhe, trasforma tutte le stringhe in lettere maiuscole (o in minuscole), ed esegui il confronto distinguendo tra minuscole e maiuscole (case-sensitive). ===
 
=== '''Prima di confrontare una stringa con una serie di altre stringhe, trasforma tutte le stringhe in lettere maiuscole (o in minuscole), ed esegui il confronto distinguendo tra minuscole e maiuscole (case-sensitive). ==='''
Il confronto tra stringhe case-insensitive costa di più del confronto case-sensitive.
 
Il confronto tra stringhe case-insensitive costatra distringhe richiede più tempo del confronto case-sensitive.
=== In una classe, invece di definire una funzione che restituisce al chiamante una collezione di dati, definisci una funzione che restituisce un iteratore di uscita, con il quale si possono generare i dati richiesti. ===
 
=== Query con cursore ===
Supponiamo di avere una collezione (o un insieme di collezioni) incapsulati in una classe. Tale classe espone uno o più metodi per estrarre (o filtrare) da tale collezione un sottoinsieme. Un modo di ottenere ciò è costruire una nuova collezione, copiarci i dati estratti, e restituire tale collezione al chiamante. Questa tecnica è però inefficiente, perché ognuna delle suddette operazioni è costosa.
 
=== '''In una classe, invece di definire una funzione che restituisce al chiamante una collezione di dati (detto anche ''snapshot''), definisci una funzione che restituisce un iteratore di uscita (detto anche ''cursore'' o ''dynaset''), con il quale si possono generare i dati richiesti. ==='''
Ecco una tecnica equivalente ma più efficiente. La funzione rende un iteratore di ingresso (input iterator). Il chiamante usa tale iteratore per estrarre, uno alla volta i dati filtrati.
 
Questa tecnica è particolarmente utile per interrogazioni su database (o ''query''), ma è applicabile anche a strutture dati gestite internamente dall'applicazione.
Si noti che questa soluzione non è del tutto equivalente, in quanto se durante l’uso dell’iteratore la collezione viene modificata da un’altra chiamata all’oggetto che incapsula la collezione, eventualmente proveniente da un altro thread, può succedere che l’iteratore sia invalidato, o anche solo che l’insieme filtrato non corrisponda ai criteri impostati. Pertanto questa tecnica è da usare solo se si ha la certezza che la collezione sottostante non viene modificata da nessuno, se non tramite l’iteratore stesso, durante tutta la vita dell'iteratore.
 
Supponiamo di avere una collezione (o un insieme di collezioni) incapsulati in una classe. Tale classe espone uno o più metodi per estrarre (o filtrare) da tale collezione un sottoinsieme. Un modo di ottenere ciò è costruire una nuova collezione, copiarci i dati estratti, e restituire tale collezione al chiamante. Questa tecnica è però inefficiente, perché ognuna delle suddette operazioni è costosa.
 
Un modo di ottenere ciò è costruire una nuova collezione, copiarci i dati estratti, e restituire tale collezione al chiamante.
Nel mondo dei database, tale collezione si chiama ''snapshot''.
Questa tecnica è però inefficiente, perché ognuna delle suddette tre operazioni richiede molto tempo, e potrebbe richiede molta memoria.
Inoltre, ha il difetto che, finché non sono stati estratti tutti i dati, non si può procedere a elaborare quelli già estratti.
 
Ecco una tecnica equivalente ma più efficiente.
La funzione di interrogazione rende un iteratore di uscita (o ''output iterator'').
Nel mondo dei database, tale iteratore si chiama ''cursore'' o ''dynaset''.
Ecco una tecnica equivalente ma più efficiente. La funzione rende un iteratore di ingresso (input iterator). Il chiamante usa tale iteratore per estrarre, uno alla volta i dati filtrati.
 
Si notiNota che questa soluzione non è del tutto equivalente, in quanto se durante l’uso dell’iteratoredell'iteratore la collezione viene modificata da un’altraun'altra chiamata all’oggettoall'oggetto che incapsula la collezione, eventualmente proveniente da un altro thread, può succedere che l’iteratorel'iteratore sia invalidato, o anche solo che l’insiemel'insieme filtrato non corrisponda ai criteri impostati. Pertanto questa tecnica è da usare solo se si ha la certezza che la collezione sottostante non viene modificata da nessuno, se non tramite l’iteratorel'iteratore stesso, durante tutta la vita dell'iteratore.
 
Questa tecnica è indipendente dal linguaggio di programmazione, in quanto il concetto di iteratore è un design pattern, implementabile in qualsiasi linguaggio.
 
=== Ricerca binaria ===
=== Per cercare numerose volte in una collezione che viene variata raramente o mai, invece di usare un albero di ricerca o una hashtable, può essere più efficiente porre i dati in un array, ordinare l'array, e usare la ricerca binaria. ===
 
==='''Se Perdevi cercarefare numerosemolte voltericerche in una collezione che viene variata raramente o mai, invece di usare un albero di ricerca o una hashtable, puòpuoi esseremigliorare piùla efficientevelocità porrese poni i dati in un array, ordinareordini l'array, e usareusi la ricerca binaria. ==='''
Se l'array viene saltuariamente modificato, l'algoritmo può essere ancora competitivo, purché le modifiche siano molte meno delle ricerche.
 
Se l'array viene saltuariamente modificato, l'questo algoritmo può essere ancora competitivo, purché le modifiche siano molte meno delle ricerche.
Se la modifica consiste in un singolo inserimento o modifica o eliminazione di un elemento, conviene effettuare degli scorrimenti nell'array.
 
Se la modifica consiste in unpochissimi singolo inserimentoinserimenti o modificamodifiche o eliminazioneeliminazioni di un elementoelementi, conviene effettuare degliuno scorrimentiscorrimento nelldell'array ad ogni operazione.
 
Se invece la modifica è più massiccia, conviene ricreare tutto l'array.
 
=== Countingsort ===
=== Per ordinare un insieme di dati aventi un range limitato, usa l’algoritmo [[Implementazioni_di_algoritmi/Counting_sort|countingsort]]. ===
 
=== '''Per ordinare un insieme di dati aventiin base a una chiave intera avente un range limitato, usa l’algoritmol'algoritmo [[Implementazioni_di_algoritmi/Counting_sort|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. A volte è più veloce anche per range più grandi, fino a 50 * N.
 
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 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. A volte è 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.
 
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 <math>a_n < a_{n + 1} + 256*256*256. </math>
 
=== Il contenitore ''slist'' ===
=== Se per una lista ti basta l’iteratore in avanti, inserire gli elementi solo all’inizio o dopo l’elemento corrente, e non ti serve sapere quanti elementi ci sono nella lista, usa un oggetto “slist” (o in C++0x, “forward_list”). ===
 
=== '''Se per una lista ti basta l’iteratoreusare l'iteratore in avanti, inserire gli elementi solo all’inizioall'inizio o dopo l’elementol'elemento corrente, e non ti serve sapere quanti elementi ci sono nella lista, usa un oggettocontenitore “slist”di tipo ''slist'' (o, in C++0x, “forward_list”''forward_list''). ==='''
 
Mentre il contenitore ''std::list'' è implementato da una lista a collegamento doppio (o bidirezionale o ''doubly-linked list''), il contenitore ''slist'', è implementato da una lista a collegamento singolo (o unidirezionale o ''singly-linked list'').
 
LaTale “slist”contenitore, pur avendo molte limitazioni, occupa meno memoria ed è più veloce.
Infatti, tipicamente, l'intestazione di un oggetto ''std::list'' contiene un puntatore alla cima, un puntatore al fondo della lista, e il contatore del numero di elementi, mentre l’intestazione di un oggetto ''slist'' contiene solo un puntatore alla cima della lista.
Inoltre, tipicamente, ogni nodo di un oggetto ''std::list'' contiene un puntatore all'elemento precedente e un puntatore all'elemento successivo, mentre ogni nodo di un oggetto ''slist'' contiene solo un puntatore all'elemento successivo.
Infine, ogni inserimento di un elemento da un oggetto ''std::list'' deve aggiornare quattro puntatori e un contatore, mentre ogni inserimento da un oggetto ''slist'' deve aggiornare solo due puntatori.
 
=== Partizionamento ===
 
=== '''Se devi solo individuaredividere iuna primisequenza Nin elementidue digruppi unain sequenza,base oa l'N-esimoun elemento di una sequenzacriterio, usa un algoritmo di partizionamento d'ordine, invece di ununo di ordinamento. ==='''
 
In STL c'è l'algoritmo nth_element''partition'', 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)).
La “slist”, pur avendo molte limitazioni, occupa meno memoria ed è più veloce.
 
=== Partizionamento e ordinamento stabili ===
Infatti, tipicamente, l’intestazione di un oggetto “std::list” contiene un puntatore alla cima, un puntatore al fondo della lista, e il contatore del numero di elementi, mentre l’intestazione di un oggetto “slist” contiene solo un puntatore alla cima della lista. Inoltre, tipicamente, ogni nodo di un oggetto “std::list” contiene un puntatore all’elemento precedente e un puntatore all’elemento successivo, mentre ogni nodo di un oggetto “slist” contiene solo un puntatore all’elemento successivo. Infine, ogni inserimento di un elemento da un oggetto “std::list” deve aggiornare quattro puntatori e un contatore, mentre ogni inserimento da un oggetto “slist” deve aggiornare solo due puntatori.
 
=== '''Se devi solopartizionare dividereo ordinare una sequenza inper duecui gruppinon inè baserichiesto adi unmantenere criterio,l'ordine usadelle un algoritmo dientità partizionamentoequivalenti, invecenon diusare unoun dialgoritmo ordinamentostabile. ==='''
 
In STL c'è l'algoritmo partitiondi partizionamento ''stable_partition'', che è leggermente più velocelento dell'algoritmo sort''partition''; e c'è l'algoritmo di ordinamento ''stable_sort'', inche quantoè haleggermente complessitàpiù O(N)lento dell'algoritmo ''sort''.
 
=== Partizionamento d'ordine ===
=== Se non devi mantenere l'ordine delle entità equivalenti, non usare un algoritmo stabile. ===
 
'''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 stable_partition, che è leggermente più lento dell'algoritmo partition, e c'è l'algoritmo stable_sort, che è leggermente più lento dell'algoritmo sort.
 
In STL c'è l'algoritmo stable_partition''nth_element'', che, èpur essendo leggermente più lento dell'algoritmo partition, e c'è l'algoritmo stable_sortstable_partition'', che è leggermentenotevolmente più lentoveloce dell'algoritmo ''sort'', in quanto ha complessità O(N) invece di O(N log(N)).
=== 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. ===
 
=== Statistica d'ordine ===
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).
 
=== '''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 di 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++|Tecniche generali di ottimizzazione]]
323

contributi