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

Question

Докам не хватает примера... Как вы используете bisect.insort_left)_ на основе ключа?

Попытка вставить на основе ключа.

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

вставляет вставку в data[0],

Из документов...

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

Вставьте x в отсортированном порядке. Это эквивалентно a.insert(bisect.bisect_left(a, x, lo, hi), x) при условии, что а уже отсортировано. Имейте в виду, что в поиске O(log n) преобладает медленный шаг вставки O(n).

Пример использования:

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

Я хочу поставить ('brown', 7) после ('red', 5) в отсортированном списке в data с помощью bisect.insort_left, Прямо сейчас bisect.insort_left(data, ('brown', 7)) путы ('brown', 7) в data[0]... потому что я не использую ключи для вставки... документы не показывают для вставки с использованием ключей.

Answer 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 and save value 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))

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

Answer 3

Начиная с Python 3.10, все помощники двоичного поиска в bisect модуль теперь принимает аргумент:

keyзадает ключевую функцию одного аргумента, которая используется для извлечения ключа сравнения из каждого входного элемента. Значение по умолчанию - None (сравнить элементы напрямую).

Следовательно, вы можете передать ту же функцию, которую вы использовали для сортировки данных:

      >>> import bisect
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> data
[('black', 0), ('blue', 1), ('red', 5), ('yellow', 8)]
>>> bisect.insort_left(data, ('brown', 7), key=lambda r: r[1])
>>> data
[('black', 0), ('blue', 1), ('red', 5), ('brown', 7), ('yellow', 8)]

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

Запросы / патчи апстрима

У меня такое чувство, что это рано или поздно произойдет;-)

• https://github.com/python/cpython/pull/13970
• https://bugs.python.org/issue4356

Answer 5

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

Answer 6

Из версии на питоне 3.10, аргумент добавлен.

Источники:

• GitHubЗапрос функции
• Документация для версии 3.10
• Обратите внимание, что в документации для версии 3.9 нет keyаргумент.