Il modulo bisect implementa un algoritmo per l'inserimento di elementi in una lista mantenendo la lista ordinata.

Inserire con Ordinamento

Ecco un semplice esempio utilizzando insort() per inserire elementi in una lista mantenendo l'ordinamento.

# bisect_example.py

import bisect

# UNa serie casuale di numeri
values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]

print('Nuovi Posizione Contenuto')
print('----- --------- ---------')

l = []
for i in values:
    position = bisect.bisect(l, i)
    bisect.insort(l, i)
    print('{:5}     {:5}'.format(i, position), l)

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

$ python3 bisect_example.py

Nuovi Posizione Contenuto
----- --------- ---------
   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]
   77         8 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
    1         0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]

Questo è un semplice esempio, e per l'ammontare dei dati che si stanno manipolando potrebbe essere più veloce costruire semplicemente la lista, per poi ordinarla una sola volta. Tuttavia, per liste lunghe, significativi risparmi di tempo e memoria possono essere raggiunti utilizzando un algoritmo di inserimento ordinato tipo questo.

Gestire Duplicati

Il risultato mostrato precedentemente comprende un valore ripetuto, 77. Il modulo bisect fornisce due modi per gestire le ripetizioni. I nuovi valori possono essere inseriti alla sinistra di quelli 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 il valore prima di quello esistente.

# bisect_example2.py

import bisect

# UNa serie casuale di numeri
values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]

print('Nuovi Posizione Contenuto')
print('----- --------- ---------')

# Utilizzo bisect_left ed insort_left.
l = []
for i in values:
    position = bisect.bisect_left(l, i)
    bisect.insort_left(l, i)
    print('{:5}     {:5}'.format(i, position), l)

Quando gli stessi dati vengono manipolati utilizzando bisect_left() ed insort_left(), il risultato è la stessa lista ordinata ma le posizioni di inserimento sono diverse per i valori duplicati.

$ python3 bisect_example2.py

Nuovi Posizione Contenuto
----- --------- ---------
   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]
   77         7 [3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]
    1         0 [1, 3, 10, 14, 26, 45, 50, 66, 77, 77, 79, 84, 85]

Oltre all'implementazione Python, è disponibile una implementazione in C più veloce. Se la versione C è presente, essa sovrascrive quella in puro Python automaticamente quando viene importato bisect.