पायथन बिसेक्ट, अवरोही क्रमबद्ध सूचियों के साथ काम करना संभव है?

Question

मैं उन सूचियों पर बिसेक्ट मॉड्यूल का उपयोग कैसे कर सकता हूं जो अवरोही क्रमबद्ध हैं? उदाहरण के लिए।

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 कर रहे हैं - मेरे लिए जो कोई भी काम न। कोई सुझाव? धन्यवाद

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

Answer 2

मैंने कभी भी बिसेक्ट पैकेज में उपयोग नहीं किया है। लेकिन अगर यह केवल आरोही क्रम में काम करता है और आप हमेशा अपनी सूची को क्रमबद्ध करते हैं (चाहे आरोही या अवरोही हो) तो आप बस पहले से सॉर्ट कर सकते हैं और फिर उलटा कर सकते हैं (यदि आप इसे अवरोही रखना चाहते हैं)।

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

स्पष्ट रूप से एक असली समाधान तो एक हैक लेकिन कम से कम यह काम करेगा।

Answer 3

प्रलेखन से बनाने के लिए है:

अनुसार क्रमबद्ध() फ़ंक्शन के विपरीत, यह नहीं पड़ता है bisect() के लिए भावना तर्कों को कुंजी या उलट करने के लिए है क्योंकि इससे एक अक्षम डिजाइन (लगातार कॉल कार्यों को विभाजित करने के लिए होगा) n ot पिछली कुंजी लुकअप "याद रखें"।

इसलिए, यदि आपके पास व्यस्त क्रम की सूची है, तो आप भाग्य से बाहर हैं।

बिसेक्ट के लिए मुख्य उपयोगकेस पहले से ही आदेशित सूची का कुशल अद्यतन है।
आप या तो अपनी सूची के डेटा प्रारूप को बदलना चाहते हैं (उदाहरण के लिए इसे जितना संभव हो सके सीधे क्रम में बनाए रखना, और फिर इसे अंत में उलटाना), या तो अपने स्वयं के संस्करण को कार्यान्वित करने के लिए।
या, यदि आप मुख्य उपयोग में नहीं हैं, तो आप इसका उपयोग न करने का विकल्प चुन सकते हैं, उदा। सभी तत्वों को सम्मिलित करके और फिर उन्हें बहुत अंत में सॉर्ट करके।

Answer 4

मुझे एक ही समस्या थी और जब से मैंने आदेश सूची का उपयोग किया था।

मैं समाधान के साथ समाप्त हुआ जहां मैंने मूल सूची हमेशा आरोही क्रम में रखी और जब मैंने अवरोही क्रम मूल्यों की आवश्यकता होती है तो केवल उलटा हुआ इटरेटर इस्तेमाल किया।

यह आपकी समस्या के साथ काम नहीं कर सकते ...

Answer 5

उम्मीद है कि "कुंजी" तर्क मॉड्यूल कार्यों एक दिन द्विभाजित में जोड़ दिया जाएगा (देखें: http://bugs.python.org/issue4356)। दुर्भाग्यवश इस समय किसी प्रकार के कामकाज के बिना संभव नहीं है (पायथन संस्करण < 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] 

Answer 6

थोड़ा अद्यतन 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