python bisect, có thể làm việc với các danh sách sắp xếp giảm dần không?

Question

Làm cách nào tôi có thể sử dụng mô-đun nhị phân trên các danh sách được sắp xếp giảm dần? ví dụ:

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 

Phương pháp duy nhất là insort (insort_right) hoặc insort_left - không có cách nào phù hợp với tôi. Bất kỳ đề xuất nào? cảm ơn bạn

Answer 1

Có lẽ điều dễ nhất là mượn mã từ thư viện và đưa ra phiên bản của riêng bạn

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) 

Answer 2

Tôi chưa bao giờ sử dụng gói bisect. Nhưng nếu nó chỉ hoạt động theo thứ tự tăng dần và bạn luôn giữ danh sách của bạn được sắp xếp (cho dù tăng dần hay giảm dần) thì bạn có thể sắp xếp trước và sau đó đảo ngược (nếu bạn muốn giữ nó giảm dần).

x.sort() 
bisect.insort(x,2.5) 
x.reverse() 

Rõ ràng là một hack thì một giải pháp thực sự nhưng ít nhất nó sẽ hoạt động.

Answer 3

Từ các tài liệu:

Không giống như các chức năng được sắp xếp(), nó không làm ý nghĩa cho các bisect() chức năng để có phím hoặc đảo ngược đối số vì điều đó sẽ dẫn đến một thiết kế không hiệu quả (các cuộc gọi liên tiếp để chia đôi các chức năng sẽ n ot "nhớ" tất cả khóa trước tra cứu).

Do đó, nếu bạn có danh sách theo thứ tự ngược lại thì bạn sẽ không may mắn.

Cách sử dụng chính để chia đôi là cập nhật hiệu quả danh sách đã được sắp xếp.
Bạn có thể muốn thay đổi định dạng dữ liệu trong danh sách của mình (ví dụ: duy trì định dạng dữ liệu theo thứ tự trực tiếp càng nhiều càng tốt, sau đó đảo ngược nó ở cuối), hoặc để triển khai phiên bản chia đôi của riêng bạn.
Hoặc, nếu bạn không ở trong nhóm sử dụng chính, bạn có thể chọn không sử dụng nó, ví dụ: bằng cách chèn tất cả các phần tử và sau đó sắp xếp chúng ở phần cuối.

Answer 4

Tôi đã gặp vấn đề tương tự và kể từ khi tôi sử dụng danh sách có thứ tự.

Tôi đã kết thúc với giải pháp mà tôi giữ danh sách gốc luôn theo thứ tự tăng dần và chỉ sử dụng trình đảo ngược lặp khi tôi cần có giá trị thứ tự giảm dần.

này có thể không làm việc với vấn đề của bạn ...

Answer 5

Hy vọng rằng những "chìa khóa" tranh luận sẽ được thêm vào bisect chức năng mô-đun một ngày (xem: http://bugs.python.org/issue4356). Thật không may là không thể không có một số cách giải quyết khác vào lúc này (phiên bản Python < 3.4).

Một workaround có thể là sử dụng một wrapper như:

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) 

Cách sử dụng:

>>> x = [4., 3., 2., 1.] 
>>> bisect.insort(ReversedSequenceView(x), 2.5) 
>>> x 
[4.0, 3.0, 2.5, 2.0, 1.0] 

Answer 6

cập nhật Hơi đang bisect thư viện:

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