python 对分，是否可以使用降序排序列表？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2247394/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Bisect, is it possible to work with descending sorted lists?
提问by Steve D
How can I use bisect module on lists that are sorted descending? e.g.
如何在降序排序的列表上使用 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
The only methods are insort (insort_right) or insort_left - none of which work for me.
唯一的方法是 insort (insort_right) 或 insort_left - 它们都不适合我。
采纳答案by John La Rooy
Probably the easiest thing is to borrow the code from the library and make your own version
可能最简单的方法是从库中借用代码并制作自己的版本
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)
回答by rob
From the documentation:
从文档：
Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficent design (successive calls to bisect functions would not “remember” all of the previous key lookups).
与 sorted() 函数不同，bisect() 函数使用键或反向参数是没有意义的，因为这会导致设计效率低下（对 bisect 函数的连续调用不会“记住”之前的所有键查找） .
Therefore, if you have a list with inverse order, then you are out of luck.
因此，如果您有一个逆序的列表，那么您就不走运了。
The main usecase for bisect is the efficient update of an already ordered list.
You may want either to change the data format of your list (e.g. maintaining it in direct order as much as possible, and then reversing it at the very end), either to implement your own version of bisect.
Or, if you are not in the main usecase, you can opt not to use it at all, e.g. by inserting all elements and then sorting them at the very end.
bisect 的主要用例是有效更新已排序的列表。
您可能想要更改列表的数据格式（例如，尽可能以直接顺序维护它，然后在最后将其反转），或者实现您自己的 bisect 版本。
或者，如果您不在主要用例中，您可以选择根本不使用它，例如插入所有元素，然后在最后对它们进行排序。
回答by Mikael Lepist?
I had the same problem and since when I used ordered list.
我遇到了同样的问题，自从我使用有序列表以来。
I ended up with solution where I kept original list always in ascending order and just used reversed iterator when I needed to have descending order values.
我最终得到了解决方案，我始终按升序保留原始列表，并在需要降序值时仅使用反向迭代器。
This might not work with your problem...
这可能不适用于您的问题...
回答by jay
I've never used to the bisect package. But if it only works in ascending order and you're always keeping your list sorted (whether ascending or descending) then you could simply sort beforehand and then invert (if you want to keep it descending).
我从不习惯 bisect 包。但是，如果它只能按升序运行并且您始终保持列表排序（无论是升序还是降序），那么您可以简单地预先排序然后反转（如果您想保持降序）。
x.sort()
bisect.insort(x,2.5)
x.reverse()
Obviously more a hack then a real solution but at least it would work.
显然比真正的解决方案更像是一个黑客，但至少它会起作用。
回答by Dennis Golomazov
Slightly updated bisectlibrary code:
稍微更新的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
回答by JMae
One approach is to negate the keys. For example,
一种方法是否定键。例如，
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]
Result: [4, 3, 2.5, 2, 1]
结果：[4, 3, 2.5, 2, 1]
回答by u8256010
You can insert like this
你可以这样插入
bisect.insort_left(lists, -x)
bisect.insort_left(lists, -x)
and extract elements like this
并提取这样的元素
value = - lists[i]
回答by pedrovgp
I was looking to get the position to insert a number in a list, to keep it ordered. I ended up using the following solution:
我正在寻找在列表中插入一个数字的位置，以保持它的有序性。我最终使用了以下解决方案：
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)]
回答by Tomasz Elendt
Hopefully the "key" argument will be added to bisect module functions one day (see: http://bugs.python.org/issue4356). Unfortunately it's not possible without some kind of workaround at the moment (Python version < 3.4).
希望有朝一日将“key”参数添加到 bisect 模块函数中（请参阅：http: //bugs.python.org/issue4356）。不幸的是，目前没有某种解决方法是不可能的（Python 版本 < 3.4）。
One possible workaround is to use a wrapper like:
一种可能的解决方法是使用如下包装器：
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)
Usage:
用法：
>>> x = [4., 3., 2., 1.]
>>> bisect.insort(ReversedSequenceView(x), 2.5)
>>> x
[4.0, 3.0, 2.5, 2.0, 1.0]
