 |
 |
 |
La libreria di riferimento di Python |  |
 |
 |
|
|
|
La libreria di riferimento di Python | |
|
|
(Questa spiegazione è dovuta a François Pinard. Il codice Python per questo modulo è stato fornito da Kevin O'Connor.)
Gli heap sono vettori per i quali a[k] <= a[2*k+1] e
a[k] <= a[2*k+2] per ogni k, contando gli
elementi da zero. Per esigenze di confronto, gli elementi non
presenti vengono considerati di valore infinito.
L'interessante proprietà degli heap è che a[0] è sempre il suo
elemento più piccolo.
La strana regola precedente può essere intesa come una rappresentazione
di un torneo con poco dispendio per la memoria .I numeri seguenti sono k, non
a[k]:
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Nell'albero precedente, ogni cella k è padre delle celle
2*k+1 e 2*k+2. In un qualunque torneo ad
eliminazione, come vediamo negli sport, ogni cella contiene il
vincitore delle celle sottostanti e possiamo seguire il vincitore
lungo l'albero per vedere tutti gli avversari che ha incontrato. Tuttavia
nelle applicazioni informatiche di tali tornei, non abbiamo bisogno di
tracciare la storia del vincitore. Per avere una maggior efficienza
nell'uso della memoria, quando un vincitore viene promosso, si cerca di
sostituirlo con qualcuno del livello sottostante, la regola
diventa quindi che una cella e le sue due celle sottostanti contengono
tre differenti elementi, ma la cella superiore "vince" sulle altre due.
Se questa regola dello heap viene sempre rispettata, l'elemento di indice zero è chiaramente il vincitore assoluto. Il meccanismo più semplice per rimuoverlo e cercare il "prossimo" vincitore consiste nello spostare un perdente (diciamo la cella 30 nel diagramma precedente) nella posizione 0 e poi far scendere questo elemento lungo l'albero, scambiando i valori, finché la regola viene ristabilita. Questo algoritmo è chiaramente logaritmico sul numero totale degli elementi che compongono l'albero. Iterando su tutti gli elementi, ottenete un ordinamento di tempo O(n log n).
Una caratteristica utile di questo algoritmo è che potete inserire in modo efficiente nuovi elementi mentre l'ordinamento è in funzione, purché gli elementi inseriti non siano "migliori" dell'ultimo elemento di indice 0 che avete estratto. Questo torna particolarmente utile nei contesti di simulazione, dove l'albero contiene tutti gli eventi introdotti e la condizione di "vincitore" indica il minor tempo di schedulazione. Quando un evento schedula altri eventi per l'esecuzione, questi verrano schedulati nel futuro, così che possano essere facilmente inseriti nello heap. Perciò lo heap è una buona struttura per implementare gli scheduler (e quello che ho usato per il mio sequenziatore MIDI :-).
Sono state studiate approfonditamente varie strutture per implementare gli scheduler e gli heap sono adatti a questo scopo, essendo ragionevolmente veloci, la velocità è pressoché costante ed il caso peggiore non è molto diverso dal caso medio. Ad ogni modo esistono altre rappresentazioni più efficienti, ma i casi peggiori potrebbero risultare terribili.
Gli heap sono molto utili anche per l'ordinamento di grandi dischi. Tutti voi probabilmente sapete che per realizzare grandi ordinamenti si producono delle "runs" (che sono sequenze preordinate, la cui dimensione è solitamente legata alla quantità di memoria della CPU), procedendo poi allo loro fusione, questa fusione è spesso organizzata molto ingegnosamente5.1. È molto importante che l'ordinamento iniziale produca sequenze più lunghe possibili. I tornei sono una buona soluzione. Se, usando tutta la memoria disponibile per contenere i tornei, sostituite e fate scendere gli elementi che si succedono per riempire la run corrente, produrrete run che sono due volte la dimensione della memoria per input casuali e ancora di più per input parzialmente ordinati.
Inoltre, se estraete l'elemento di indice 0 sul disco ed ottenete un input che non potrebbe essere inserito nell'attuale torneo (perché il valore "vince" sull'ultimo valore estratto), non potete inserirlo nello heap, percui la dimensione di quest'ultimo diminuisce. La memoria liberata potrebbe essere ragionevolmente riutilizzata subito per costruire progressivamente un secondo heap, che aumenta con la stessa rapidità con cui diminuisce il primo. Quando il primo heap è completamente svanito, scambiate gli heap e iniziate una nuova sequenza. Intelligente e abbastanza efficace!
In una parola, gli heap sono strutture di memorizzazione utili da
conoscere. Io gli uso in diverse applicazioni e credo sia bene tenere
a portata di mano un modulo `heap'. :-)
|
|
|
La libreria di riferimento di Python | |
|
|