Как использовать bisect.insort_left с ключом?

Ответ 1

По сути, это делает то же самое, что SortedCollection recipe, о котором упоминается в документации bisect в разделе " См. Также: в конце", который поддерживает функцию ключа.

То, что делается, - это отдельный список отсортированных keys который поддерживается параллельно со списком отсортированных data для повышения производительности (это быстрее, чем создание списка ключей перед каждой вставкой, но хранить его и обновлять его не обязательно). Рецепт ActiveState инкапсулировал это для вас внутри класса, но в приведенном ниже коде они представляют собой просто два независимых независимых списка, поэтому им было бы легче выйти из синхронизации, чем если бы они оба были задержаны. в экземпляре класса рецепт).

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)]

Дополнительный вопрос:
Можно ли использовать bisect.insort_left?

Нет, вы не можете просто использовать bisect.insort_left() чтобы сделать это, потому что она не была написана так, чтобы поддерживать функцию ключа - вместо этого она просто сравнивает весь переданный ей элемент для вставки, x, с один из целых элементов в массиве в выражении if a[mid] < x:. Вы можете понять, что я имею в виду, посмотрев исходный код модуля bisect в Lib/bisect.py.

Вот соответствующая выдержка:

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)

Вы могли бы изменить вышеупомянутое, чтобы принять дополнительный аргумент ключевой функции и использовать его:

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

... и назовите это так:

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

На самом деле, если вы собираетесь написать собственную функцию ради большей эффективности за счет ненужной общности, вы можете обойтись без добавления общего аргумента функции ключа и просто жестко закодировать все, чтобы работать так, как нужно с данными формат у вас есть. Это позволит избежать накладных расходов на повторные вызовы ключевой функции при выполнении вставок.

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.
    . . .

... вызывается так, не передавая keyfunc:

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

Ответ 2

Вы можете обернуть свою итерацию в класс, который реализует __getitem__ и __len__. Это дает вам возможность использовать ключ с bisect_left. Если вы настроили свой класс на использование итерируемой и ключевой функции в качестве аргументов.

Чтобы расширить его для использования с insort_left необходимо реализовать метод insert. Проблема здесь в том, что если вы сделаете это, insort_left попытается вставить ваш ключевой аргумент в список, содержащий объекты, членом которых является ключ.

Пример понятнее

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")

Посмотрите, как в моем методе insert я должен был сделать его специфичным для словаря расписания, иначе insort_left попытается вставить "0359" куда он должен вставить {"time": "0359"}?

Обходными путями могут быть создание фиктивного объекта для сравнения, наследование от KeyWrapper и переопределение insert или передача некоторой фабричной функции для создания объекта. Ни один из этих способов не является особенно желательным с точки зрения идиоматического питона.

Так что самый простой способ - просто использовать KeyWrapper с bisect_left, который возвращает индекс вставки, а затем выполнить вставку самостоятельно. Вы можете легко обернуть это в специальную функцию.

например

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

В этом случае убедитесь, что вы не внедрили insert, поэтому вы будете немедленно осведомлены, если случайно передадите KeyWrapper в мутирующую функцию, например insort_left которая, вероятно, не будет работать правильно.

Чтобы использовать данные вашего примера

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)

Ответ 3

Если ваша цель состоит в том, чтобы сохранить список , отсортированный по ключу, выполняя обычные операции, такие как bisect insert, удалять и обновлять, я думаю, sortedcontainers также должно соответствовать вашим потребностям, и вы избежите вставок O (n).

Ответ 4

Добавьте методы сравнения в ваш класс

Иногда это наименее болезненный способ, особенно если у вас уже есть класс, и вы просто хотите отсортировать его по ключу:

#!/usr/bin/env python3

import bisect
import functools

@functools.total_ordering
class MyData:
    def __init__(self, color, number):
        self.color = color
        self.number = number
    def __lt__(self, other):
        return self.number < other .number
    def __str__(self):
        return '{} {}'.format(self.color, self.number)

mydatas = [
    MyData('red', 5),
    MyData('blue', 1),
    MyData('yellow', 8),
    MyData('black', 0),
]
mydatas_sorted = []
for mydata in mydatas:
    bisect.insort(mydatas_sorted, mydata)
for mydata in mydatas_sorted:
    print(mydata)

Выход:

black 0
blue 1
red 5
yellow 8

Смотрите также: "Включение" сравнения для классов

Протестировано в Python 3.5.2.