python - ¿Cómo usar bisect.insort_left con una clave?

Question

A los doctores les falta un ejemplo ... ¿Cómo se usa bisect.insort_left)_ basado en una clave?

Tratando de insertar basado en clave.

bisect.insort_left(data, (''brown'', 7))

Pone insertar en los data[0] .

Desde docs ...

bisect.insort_left( a, x, lo = 0, hi = len (a) )

Insertar x en un orden ordenado. Esto es equivalente a a.insert(bisect.bisect_left(a, x, lo, hi), x) suponiendo que a ya está ordenado. Tenga en cuenta que la búsqueda O (log n) está dominada por el lento paso de inserción O (n).

Uso de la muestra:

>>> data = [(''red'', 5), (''blue'', 1), (''yellow'', 8), (''black'', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
(''black'', 0)
>>> data[bisect_left(keys, 1)]
(''blue'', 1)
>>> data[bisect_left(keys, 5)]
(''red'', 5)
>>> data[bisect_left(keys, 8)]
(''yellow'', 8)
>>>

Quiero poner (''brown'', 7) después (''red'', 5) en la lista ordenada en los data usando bisect.insort_left . En este momento, bisect.insort_left(data, (''brown'', 7)) pone (''brown'', 7) en data[0] ... porque no estoy usando las teclas para insertar ... docs no se muestran Hacer inserciones utilizando las teclas.

Answer 1

Básicamente, esto hace lo mismo que la SortedCollection recipe que menciona la documentación de SortedCollection recipe en la sección Vea también: al final que admite una función de tecla.

Lo que se está haciendo es una lista separada de keys ordenadas que se mantiene en paralelo con la lista de data ordenados para mejorar el rendimiento (es más rápido que crear la lista de claves antes de cada inserción, pero mantenerla y actualizarla no es estrictamente necesaria). La receta de ActiveState encapsuló esto para usted dentro de una clase, pero en el código a continuación solo se transmiten dos listas independientes (por lo que sería más fácil para ellos desincronizarse de lo que sería si ambas se mantuvieran) en una instancia de la clase de la receta).

from bisect import bisect_left

def insert(seq, keys, item, keyfunc=lambda v: v):
    """Insert an item into a sorted list using a separate corresponding
       sorted keys list and a keyfunc() to extract the key from each item.

    Based on insert() method in SortedCollection recipe:
    http://code.activestate.com/recipes/577197-sortedcollection/
    """
    k = keyfunc(item)  # Get key.
    i = bisect_left(keys, k)  # Determine where to insert item.
    keys.insert(i, k)  # Insert key of item to keys list.
    seq.insert(i, item)  # Insert the item itself in the corresponding place.

# Initialize the sorted data and keys lists.
data = [(''red'', 5), (''blue'', 1), (''yellow'', 8), (''black'', 0)]
data.sort(key=lambda r: r[1]) # Sort data by key value
keys = [r[1] for r in data]   # Initialize keys list
print(data)  # -> [(''black'', 0), (''blue'', 1), (''red'', 5), (''yellow'', 8)]

insert(data, keys, (''brown'', 7), keyfunc=lambda x: x[1])
print(data)  # -> [(''black'', 0), (''blue'', 1), (''red'', 5), (''brown'', 7), (''yellow'', 8)]

Pregunta de seguimiento:
¿ bisect.insort_left puede utilizar bisect.insort_left ?

No, no puedes simplemente usar la función bisect.insort_left() para hacer esto porque no se escribió de una manera que admita una función clave, sino que simplemente compara todo el elemento que se le pasó al inserto, x , con uno de los elementos completos de la matriz en su sentencia if a[mid] < x: Puede ver lo que quiero decir mirando la fuente del módulo Lib/bisect.py en Lib/bisect.py .

Aquí está el extracto relevante:

def insort_left(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the left of the leftmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError(''lo must be non-negative'')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    a.insert(lo, x)

Podría modificar lo anterior para aceptar un argumento de función clave opcional y usarlo:

def my_insort_left(a, x, lo=0, hi=None, keyfunc=lambda v: v):
    x_key = keyfunc(x)  # Get and save value comparison value.
    . . .
        if keyfunc(a[mid]) < x_key: # Compare key values.
            lo = mid+1
    . . .

... y llámalo así:

my_insort_left(data, (''brown'', 7), keyfunc=lambda v: v[1])

En realidad, si va a escribir una función personalizada, en aras de una mayor eficiencia a costa de una generalidad innecesaria, podría prescindir de la adición de un argumento de función de clave genérica y simplemente codificar todo para operar de la manera necesaria con los datos. formato que tienes. Esto evitará la sobrecarga de varias llamadas a una función clave al realizar las inserciones.

def my_insort_left(a, x, lo=0, hi=None):
    x_key = x[1]   # Key on second element of each item in sequence.
    . . .
        if a[mid][1] < x_key: lo = mid+1  # Compare second element to key.
    . . .

... Llamado de esta manera sin pasar keyfunc:

my_insort_left(data, (''brown'', 7))

Answer 2

Podría envolver su iterable en una clase que implemente __getitem__ y __len__ . Esto le da la oportunidad de usar una clave con bisect_left . Si configura su clase para tomar el iterable y una función clave como argumentos.

Para extender esto y poder utilizarlo con insort_left se requiere implementar el método de insert . El problema aquí es que si lo hace es que insort_left intentará insertar su argumento clave en la lista que contiene los objetos de los que la clave es miembro.

Un ejemplo es más claro.

from bisect import bisect_left, insort_left


class KeyWrapper:
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __getitem__(self, i):
        return self.key(self.it[i])

    def __len__(self):
        return len(self.it)

    def insert(self, index, item):
        print(''asked to insert %s at index%d'' % (item, index))
        self.it.insert(index, {"time":item})

timetable = [{"time": "0150"}, {"time": "0250"}, {"time": "0350"}, {"time": "0450"}, {"time": "0550"}, {"time": "0650"}, {"time": "0750"}]

bslindex = bisect_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")

islindex = insort_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")

Vea cómo en mi método de insert tuve que hacerlo específico para el diccionario de horarios, de lo contrario, insort_left intentaría insertar "0359" donde debería insertar {"time": "0359"} ?

La forma de evitar esto podría ser construir un objeto ficticio para la comparación, heredarlo de KeyWrapper e invalidar la insert o pasar algún tipo de función de fábrica para crear el objeto. Ninguna de estas formas es particularmente deseable desde el punto de vista idiomático de Python.

Por lo tanto, la forma más sencilla es utilizar KeyWrapper con bisect_left , que le devuelve el índice de inserción y luego hacer la inserción usted mismo. Usted podría fácilmente envolver esto en una función dedicada.

p.ej

bslindex = bisect_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")
timetable.insert(bslindex, {"time":"0359"})

En este caso, asegúrese de no implementar el insert , por lo que se dará cuenta inmediatamente si pasa accidentalmente un KeyWrapper a una función de mutación como insort_left que probablemente no haría lo correcto.

Para usar tus datos de ejemplo

from bisect import bisect_left


class KeyWrapper:
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __getitem__(self, i):
        return self.key(self.it[i])

    def __len__(self):
        return len(self.it)

data = [(''red'', 5), (''blue'', 1), (''yellow'', 8), (''black'', 0)]
data.sort(key=lambda c: c[1])

newcol = (''brown'', 7)

bslindex = bisect_left(KeyWrapper(data, key=lambda c: c[1]), newcol[1])
data.insert(bslindex, newcol)

print(data)

Answer 3

Si su objetivo es mantener una lista ordenada por clave , realizando las operaciones habituales como la inserción , eliminación y actualización sortedcontainers , creo que los sortedcontainers deben satisfacer sus necesidades, y evitará las inserciones O (n).