Бисект, можно ли работать с нисходящими отсортированными списками?
Как использовать модуль bisect в списках, отсортированных по убыванию?
например,
import bisect
x = [1.0,2.0,3.0,4.0] # normal, ascending
bisect.insort(x,2.5) # --> x is [1.0, 2.0, 2.5, 3.0, 4.0] ok, works fine for ascending list
# however
x = [1.0,2.0,3.0,4.0]
x.reverse() # --> x is [4.0, 3.0, 2.0, 1.0] descending list
bisect.insort(x,2.5) # --> x is [4.0, 3.0, 2.0, 1.0, 2.5] 2.5 at end, not what I want really
Единственные методы - insort (insort_right) или insort_left - ни один из них не работает для меня.
Ответы
Ответ 1
Наверное, проще всего заимствовать код из библиотеки и сделать свою собственную версию
def reverse_insort(a, x, lo=0, hi=None):
"""Insert item x in list a, and keep it reverse-sorted assuming a
is reverse-sorted.
If x is already in a, insert it to the right of the rightmost 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 x > a[mid]: hi = mid
else: lo = mid+1
a.insert(lo, x)
Ответ 2
Я никогда не пользовался биссектным пакетом. Но если он работает только в порядке возрастания, и вы всегда держите свой список отсортированным (независимо от того, восходящий или нисходящий), вы можете просто отсортировать его заранее, а затем инвертировать (если вы хотите, чтобы он нисходил).
x.sort()
bisect.insort(x,2.5)
x.reverse()
Очевидно, что больше рубить, чем реальное решение, но, по крайней мере, это сработает.
Ответ 3
Из документации:
В отличие от функции sorted(), она делает не имеет смысла для bisect() функции иметь ключ или отменять аргументов, поскольку это приведет к неэффективный дизайн (последовательные вызовы для деления пополам функций не будет "запомнить" весь предыдущий ключ поиски).
Поэтому, если у вас есть список с обратным порядком, то вам не повезло.
Основной функцией для bisect является эффективное обновление уже упорядоченного списка.
Вы можете либо изменить формат данных своего списка (например, сохранить его в прямом порядке, насколько это возможно, а затем перевернуть его в самом конце), либо реализовать свою собственную версию bisect.
Или, если вы не находитесь в основной утилите, вы можете отказаться от ее использования вообще, например. вставив все элементы, а затем отсортировав их в самом конце.
Ответ 4
У меня была та же проблема, и с тех пор, когда я использовал упорядоченный список.
У меня получилось решение, в котором я всегда сохранял исходный список в порядке возрастания и просто использовал обратный итератор, когда мне нужно было иметь значения порядка убывания.
Это может не сработать с вашей проблемой...
Ответ 5
Одним из подходов является отрицание ключей. Например,
a = [1,2,3,4]
a.reverse()
def comparator(a):
return -a
b = [comparator(i) for i in a]
bisect.insort_right(b,comparator(2.5))
a = [comparator(c) for c in b]
Результат: [4, 3, 2.5, 2, 1]
Ответ 6
Надеюсь, что аргумент "ключ" будет добавлен к функции биссектного модуля в один прекрасный день (см. http://bugs.python.org/issue4356). К сожалению, это невозможно без какого-либо обходного пути на данный момент (версия Python < 3.4).
Возможным обходным путем является использование обертки, например:
class ReversedSequenceView(collections.MutableSequence):
def __init__(self, seq):
self._seq = seq
def __getitem__(self, i):
return self._seq[-1 - i]
def __setitem__(self, i, v):
self._seq[-1 - i] = v
def __delitem__(self, i):
del self._seq[-1 - i]
def __len__(self):
return len(self._seq)
def insert(self, i, v):
return self._seq.insert(len(self._seq) - i, v)
Использование:
>>> x = [4., 3., 2., 1.]
>>> bisect.insort(ReversedSequenceView(x), 2.5)
>>> x
[4.0, 3.0, 2.5, 2.0, 1.0]
Ответ 7
Немного обновленный код библиотеки bisect
:
def reverse_bisect_right(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted in descending order.
The return value i is such that all e in a[:i] have e >= x, and all e in
a[i:] have e < x. So if x already appears in the list, a.insert(x) will
insert just after the rightmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
Essentially, the function returns number of elements in a which are >= than x.
>>> a = [8, 6, 5, 4, 2]
>>> reverse_bisect_right(a, 5)
3
>>> a[:reverse_bisect_right(a, 5)]
[8, 6, 5]
"""
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 x > a[mid]: hi = mid
else: lo = mid+1
return lo
Ответ 8
Вы можете вставить вот так
bisect.insort_left(lists, -x)
и извлекать такие элементы, как это
value = - lists[i]
Ответ 9
Я искал позицию, чтобы вставить номер в список, чтобы сохранить его в порядке. В итоге я использовал следующее решение:
def rev_bisect(l, v):
'''l -> list (descending order)
v -> value
Returns:
int -> position to insert value in list keeping it sorted
'''
h = list(range(len(l))) + [len(l)+1]
h.reverse()
l.reverse()
return h[bisect.bisect_left(l, v)]