Ottimizzare C++/Tecniche generali di ottimizzazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 247:
== 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). ===▼
▲
Il confronto tra stringhe case-insensitive costa di più del confronto case-sensitive.▼
▲Il confronto
=== 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.▼
▲
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.
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''.
▲
▲
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 l'array viene saltuariamente modificato, l'algoritmo può essere ancora competitivo, purché le modifiche siano molte meno delle ricerche.▼
▲Se l'array viene
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
Se invece la modifica è più massiccia, conviene ricreare tutto l'array.
=== 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 In 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”). ===▼
▲
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'').
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 ===
In STL c'è l'algoritmo
▲La “slist”, pur avendo molte limitazioni, occupa meno memoria ed è più veloce.
=== Partizionamento e ordinamento stabili ===
In STL c'è l'algoritmo
=== 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 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
▲=== 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).
In STL ci sono gli algoritmi ''partial_sort'' e ''partial_sort_copy'', che, pur essendo più lenti
[[Categoria:Ottimizzare C++|Tecniche generali di ottimizzazione]]
| |||