Il modulo bisect implementa un algoritmo per inserire elementi in una lista mantenendo la stessa ordinata. Questo può essere molto più efficiente che dovere ordinare una lista ripetutamente, od ordinare esplicitamente una grande lista dopo che è stata costruita.

Esempio

Vediamo un semplice esempio usando bisect.insort() , che inserisce elementi in una lista secondo un ordinamento.

import bisect
import random

# Usa un seed costante per assicurarsi che si vedano
# gli stessi numeri pseudo-casuali ogni volta che eseguiamo
# il ciclo.
random.seed(1)

# Genera 20 numeri casuali e
# li inserisce in una lista secondo un
# ordinamento
l = []
for i in range(1, 20):
	r = random.randint(1, 100)
	position = bisect.bisect(l, r)
	bisect.insort(l, r)
	print '%2d %2d' % (r, position), l

L'output per questo script è:

$ python bisect_example.py
14  0 [14]
85  1 [14, 85]
77  1 [14, 77, 85]
26  1 [14, 26, 77, 85]
50  2 [14, 26, 50, 77, 85]
45  2 [14, 26, 45, 50, 77, 85]
66  4 [14, 26, 45, 50, 66, 77, 85]
79  6 [14, 26, 45, 50, 66, 77, 79, 85]
10  0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3  0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
84  9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
44  4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
77  9 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1  0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
45  7 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85]
73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
23  4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95]
91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95]

La prima colonna mostra il nuovo numero casuale. La seconda colonna mostra la posizione dove verrà inserito il numero nella lista. Il resto di ogni riga rappresenta la lista corrente ordinata.

Questo è un esempio semplice, e per il volume di dati che si stanno manipolando potrebbe essere più veloce costruire semplicemente la lista, quindi ordinarla una sola volta. Ma per liste lunghe, un significativo risparmio di memoria e tempo può essere ottenuto usando un algoritmo di inserimento ordinato come questo.

Si è probabilmente notato che il risultato di cui sopra comprende alcuni valori ripetuti (45 e 77). Il modulo bisect fornisce 2 modi per gestire i valori ripetuti. I nuovi valori possono essere inseriti alla sinistra dei valori esistenti oppure alla destra. La funzione insort() è in realtà un alias per insort_right() , che inserisce il valore dopo quello esistente. La funzione corrispondente insort_left() inserisce prima del valore esistente.

Se si manipolano gli stessi dati usando bisect_left() ed insort_left() , si arriva alla stessa lista ordinata, ma si noti che le posizioni di inserimento sono diverse per i valori duplicati

import bisect
import random

# Reimposta il seed
random.seed(1)

# Usa bisect_left ed insort_left.
l = []
for i in range(1, 20):
	r = random.randint(1, 100)
	position = bisect.bisect_left(l, r)
	bisect.insort_left(l, r)
	print '%2d %2d' % (r, position), l

$ python bisect_example2.py
14  0 [14]
85  1 [14, 85]
77  1 [14, 77, 85]
26  1 [14, 26, 77, 85]
50  2 [14, 26, 50, 77, 85]
45  2 [14, 26, 45, 50, 77, 85]
66  4 [14, 26, 45, 50, 66, 77, 85]
79  6 [14, 26, 45, 50, 66, 77, 79, 85]
10  0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3  0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
84  9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
44  4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
77  8 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1  0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
45  6 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85]
73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
23  4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95]
91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95]

Oltre alla implementazione Python, è disponibile anche una implementazione più veloce in C. Se la versione in C è presente, essa viene usata automaticamente al posto di quella in puro Python quando si importa il modulo bisect.