Почему модуль python 'bisect' (бинарный поиск) не позволяет использовать его с определенным «ключом»? - PullRequest
Новая
       8

Почему модуль python 'bisect' (бинарный поиск) не позволяет использовать его с определенным «ключом»?

0 голосов
/ 24 января 2020

Цитата из документов:

https://docs.python.org/3/library/bisect.html

В отличие от функции sorted (), функциям bisect () не имеет смысла иметь ключевые или обратные аргументы, потому что это может привести к неэффективному дизайну (последовательные вызовы функций деления не будут «помнить» все предыдущие поиски ключей).

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

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

Но предлагаемое решение работает для O(N) (создание списка ключей), а не для O(logN) (при условии, что необходимо вызвать разделить один раз на один список).

Существует ли какой-либо встроенный двоичный поиск, позволяющий осуществлять поиск по пользовательскому ключу?

(За исключением перегрузки operator __lt__() для пропущенных объектов.)

И если нет, тогда почему python не так ли? (при условии, что лозунг "батареи включены")

1 Ответ

0 голосов
/ 24 января 2020

В параметрах bisect и insort может быть несогласованность параметров, или вам придется передавать значение, а не ключ, для поиска. В любом случае кого-то ожидает неприятный сюрприз.

То есть либо 

def insort(a, x, lo=0, hi=None, *, key=None):
    lo = bisect(a, x, lo, hi, key)
    a.insert(lo, x)

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

>>> key=lambda r: r[1]
>>> insort(data, ('green', 3), key=key)
>>> bisect(data, 7, key=key) # error comparing tuple to int

, либо альтернативно 

def insort(a, x, lo=0, hi=None, *, key=None):
    if key is None:
        key = lambda x: x
    lo = bisect(a, key(x), lo, hi, key)
    a.insert(lo, x)

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

>>> key=lambda r: r[1]
>>> item = ('green', 3)
>>> insort(data, item, key=key)
>>> bisect(data, item, key=key) # error comparing int to tuple
...