Ottimizzare C++/Tecniche generali di ottimizzazione/Altre tecniche

Query con cursore

Invece di definire una funzione che restituisce al chiamante una collezione di dati (detta anche snapshot), definisci una funzione che restituisce un iteratore (detto anche cursore o dynaset), con il quale si possono generare ed eventualmente modificare i dati richiesti.

Questa tecnica è particolarmente utile per interrogazioni su database (dette anche query), ma è applicabile anche a strutture dati gestite internamente dall'applicazione.

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) un sottoinsieme da tale collezione.

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. Nel mondo dei database, tale iteratore si chiama cursore o dynaset. Il chiamante usa tale iteratore per estrarre, uno alla volta i dati filtrati, ed eventualmente per modificare tali dati.

Nota che questa soluzione non è del tutto equivalente, in quanto se durante l'uso dell'iteratore la collezione viene modificata da un'altra chiamata di funzione, 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.

Questa tecnica è indipendente dal linguaggio di programmazione, in quanto il concetto di iteratore è un design pattern, implementabile in qualsiasi linguaggio. Per esempio in Python esistono i generatori, navigabili con appositi iteratori.

Ricerca binaria

Se devi fare molte ricerche in una collezione che viene variata raramente o mai, invece di usare un albero di ricerca o una hashtable, puoi migliorare la velocità se poni i dati in un array, ordini l'array, ed effettui le ricerche con il metodo dicotomico (noto anche come ricerca binaria).

La ricerca binaria ha complessità logaritmica, come gli alberi di ricerca, ma ha il pregio della compattezza e della località dei riferimenti propria degli array.

Se l'array viene modificato, questo algoritmo può essere ancora competitivo, purché le modifiche siano molte meno delle ricerche.

Se la modifica consiste in pochissimi inserimenti o modifiche o eliminazioni di elementi, conviene effettuare uno scorrimento dell'array ad ogni operazione. Se invece la modifica è più massiccia, conviene ricreare tutto l'array.

In C++, se la dimensione dell'array non è una costante, usa un vector.

Lista a collegamento singolo

Se per una lista non hai bisogno di iteratori bidirezionali, non devi inserire gli elementi solo alla fine né prima dell'elemento corrente, e non ti serve sapere quanti elementi ci sono nella lista, usa una lista a concatenamento singolo, invece di una lista a concatenamento doppio.

Tale contenitore, pur avendo molte limitazioni, occupa meno memoria ed è più veloce.

Infatti, tipicamente, l'intestazione di una lista a concatenamento doppio contiene un puntatore alla cima, un puntatore al fondo della lista, e il contatore del numero di elementi, mentre l'intestazione di una lista a concatenamento singolo contiene solo un puntatore alla cima della lista. Inoltre, tipicamente, ogni nodo di una lista a concatenamento doppio contiene un puntatore all'elemento precedente e un puntatore all'elemento successivo, mentre ogni nodo di una lista a concatenamento singolo contiene solo un puntatore all'elemento successivo. Infine, ogni inserimento di un elemento in una lista a concatenamento doppio deve aggiornare quattro puntatori e incrementare un contatore, mentre ogni inserimento in una lista a concatenamento singolo deve solo aggiornare due puntatori.

Nella libreria standard del C++, il contenitore std::list è implementato da una lista a concatenamento doppio. Il contenitore slist, non standard ma disponibile in varie librerie, e il contenitore forward_list, che farà parte della libreria standard C++0x, sono implementati da una lista a concatenamento singolo.