bisect — Mantener listas en orden

Propósito:Mantiene una lista ordenada sin tener que ordenarla cada vez que se agrega un elemento a la lista.

El módulo bisect implementa un algoritmo para insertar elementos en una lista mientras se mantiene la lista ordenada.

Insertar en orden

Aquí hay un ejemplo simple en el que insort() se usa para insertar elementos en una lista en orden.

bisect_example.py
import bisect

# A series of random numbers
values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]

print('New  Pos  Contents')
print('---  ---  --------')

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

La primera columna del resultado muestra el nuevo número aleatorio. La segundoa columna muestra la posición donde se insertará el número en la lista. El resto de cada línea es la lista ordenada actual.

$ python3 bisect_example.py

Nuevo  Posición  Contenidos
-----  --------  ----------
 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]

Este es un ejemplo simple. De hecho, dada la cantidad de datos que son manipulados, podría ser más rápido simplemente crear la lista y luego ordenar una vez. Por otra parte, se pueden lograr ahorros significativos de tiempo y memoria para listas largas, usando un algoritmo de ordenación de inserción como este, especialmente cuando la operación para comparar dos miembros de la lista requiere un cálculo costoso.

Manejo de duplicados

El conjunto de resultados que se muestra anteriormente incluye un valor repetido, 77. El módulo bisect proporciona dos maneras de manejar las repeticiones: los nuevos valores pueden insertarse a la izquierda de los valores existentes, o a la derecha. La función insort() es en realidad un alias para insort_right(), que inserta un elemento después del valor existente. La función correspondiente insort_left() inserta un elemento antes del valor existente.

bisect_example2.py
import bisect

# A series of random numbers
values = [14, 85, 77, 26, 50, 45, 66, 79, 10, 3, 84, 77, 1]

print('New  Pos  Contents')
print('---  ---  --------')

# Use bisect_left and insort_left.
l = []
for i in values:
    position = bisect.bisect_left(l, i)
    bisect.insort_left(l, i)
    print('{:3}  {:3}'.format(i, position), l)

Cuando los mismos datos se manipulan usando bisect_left() y insort_left(), los resultados son la misma lista ordenada pero las posiciones de inserción son diferentes para los valores duplicados.

$ python3 bisect_example2.py

Nuevo  Posición  Contenidos
-----  --------  ----------
 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]

Ver también