क्या कोई मानक पायथन डेटा संरचना है जो क्रमबद्ध क्रम में चीज रखती है?

Question

मुझे लगता है कि कुछ इस तरह लग सकता है पर्वतमाला का एक सेट है:

[(0, 100), (150, 220), (500, 1000)] 

मैं तो एक सीमा जोड़ना होगा, (250, 400) कहना और सूची इस प्रकार दिखाई देगा:

[(0, 100), (150, 220), (250, 400), (500, 1000)] 

मैं तो कोशिश करेंगे (399, 450) श्रेणी जोड़ने के लिए, और यह त्रुटि होगी क्योंकि यह (250, 400) ओवरलैप किया गया था।

जब मैं एक नई रेंज जोड़ता हूं, तो मुझे यह सुनिश्चित करने की ज़रूरत है कि नई रेंज मौजूदा सीमा को ओवरलैप न करे। और सूची में कोई सीमा कभी भी नहीं होगी जो सूची में एक और सीमा को ओवरलैप करती है।

इस अंत में, मुझे एक डेटा संरचना चाहिए जो सख्ती से क्रमबद्ध क्रम में अपने तत्वों को बनाए रखे, और जल्दी से मुझे किसी दिए गए तत्व से पहले या बाद में तत्व ढूंढने की अनुमति दी।

क्या इस समस्या को हल करने का कोई बेहतर तरीका है? क्या पाइथन में उपलब्ध डेटा संरचना है? मुझे पता है कि bisect मॉड्यूल मौजूद है, और यह संभव है कि मैं इसका उपयोग करूंगा। लेकिन मैं उम्मीद कर रहा था कि कुछ बेहतर था।

संपादित करें: मैंने bisect मॉड्यूल का उपयोग करके इस समस्या को हल किया। कोड के लिए एक लिंक यहाँ है। यह थोड़ा दीर्घाकार है, तो मैं इसे यहाँ पोस्ट नहीं होगा:

Implementation of byte range list

Answer 1

SortedCollection से उपयोग SortedDict।

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

मैंने इसका उपयोग किया है - यह काम करता है। दुर्भाग्यवश मेरे पास उचित प्रदर्शन तुलना करने का समय नहीं है, लेकिन व्यक्तिगत रूप से यह bisect मॉड्यूल से तेज़ हो गया है।

Answer 2

सस्ते खोज और सस्ते प्रविष्टि अंतर पर हो जाते हैं। आप डेटा संरचना के लिए linked list का उपयोग कर सकते हैं। फिर एक नए तत्व के लिए सम्मिलन बिंदु खोजने के लिए खोज ओ (एन) है, और सही स्थान में नए तत्व के बाद सम्मिलन ओ (1) है।

लेकिन आप शायद सीधे सीधी पाइथन सूची का उपयोग कर बेहतर हैं। यादृच्छिक पहुंच (यानी आपकी जगह ढूंढना) लगातार समय लेता है। इस प्रकार को बनाए रखने के लिए सही स्थान में सम्मिलन सैद्धांतिक रूप से अधिक महंगा है, लेकिन यह इस बात पर निर्भर करता है कि dynamic array कैसे लागू किया गया है। अंतर्निहित सरणी के पुनर्वितरण तक आप वास्तव में सम्मिलन के लिए बड़ी कीमत का भुगतान नहीं करते हैं।

दिनांक सीमा ओवरलैप की जांच के संबंध में, मुझे अतीत में एक ही समस्या हुई है। मैं जिस कोड का उपयोग करता हूं वह यहां है। मैंने मूल रूप से इसे एक ब्लॉग पोस्ट में पाया, जो एसओ उत्तर से जुड़ा हुआ है, लेकिन वह साइट अब मौजूद नहीं है। मैं वास्तव में अपनी श्रेणियों में डेटाटाइम का उपयोग करता हूं, लेकिन यह आपके संख्यात्मक मूल्यों के साथ समान रूप से अच्छी तरह से काम करेगा।

def dt_windows_intersect(dt1start, dt1end, dt2start, dt2end): 
    '''Returns true if two ranges intersect. Note that if two 
    ranges are adjacent, they do not intersect. 

    Code based on: 
    http://beautifulisbetterthanugly.com/posts/2009/oct/7/datetime-intersection-python/ 
    http://stackoverflow.com/questions/143552/comparing-date-ranges 
    ''' 

    if dt2end <= dt1start or dt2start >= dt1end: 
     return False 

    return dt1start <= dt2end and dt1end >= dt2start 

यहाँ यह काम करता है साबित करने के लिए इकाई परीक्षण कर रहे हैं:

from nose.tools import eq_, assert_equal, raises 

class test_dt_windows_intersect(): 
    """ 
    test_dt_windows_intersect 
    Code based on: 
    http://beautifulisbetterthanugly.com/posts/2009/oct/7/datetime-intersection-python/ 
    http://stackoverflow.com/questions/143552/comparing-date-ranges 

       |-------------------|   compare to this one 
    1    |---------|    contained within 
    2   |----------|     contained within, equal start 
    3     |-----------|   contained within, equal end 
    4   |-------------------|   contained within, equal start+end 
    5  |------------|      overlaps start but not end 
    6      |-----------|  overlaps end but not start 
    7  |------------------------|   overlaps start, but equal end 
    8   |-----------------------|  overlaps end, but equal start 
    9  |------------------------------| overlaps entire range 

    10 |---|         not overlap, less than 
    11 |-------|        not overlap, end equal 
    12        |---| not overlap, bigger than 
    13        |---|  not overlap, start equal 
    """ 


    def test_contained_within(self): 
     assert dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,6,30), datetime(2009,10,1,6,40), 
     ) 

    def test_contained_within_equal_start(self): 
     assert dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,6,0), datetime(2009,10,1,6,30), 
     ) 

    def test_contained_within_equal_end(self): 
     assert dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,6,30), datetime(2009,10,1,7,0), 
     ) 

    def test_contained_within_equal_start_and_end(self): 
     assert dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
     ) 

    def test_overlaps_start_but_not_end(self): 
     assert dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,5,30), datetime(2009,10,1,6,30), 
     ) 

    def test_overlaps_end_but_not_start(self): 
     assert dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,6,30), datetime(2009,10,1,7,30), 
     ) 

    def test_overlaps_start_equal_end(self): 
     assert dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,5,30), datetime(2009,10,1,7,0), 
     ) 

    def test_equal_start_overlaps_end(self): 
     assert dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,30), 
     ) 

    def test_overlaps_entire_range(self): 
     assert dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,5,0), datetime(2009,10,1,8,0), 
     ) 

    def test_not_overlap_less_than(self): 
     assert not dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,5,0), datetime(2009,10,1,5,30), 
     ) 

    def test_not_overlap_end_equal(self): 
     assert not dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,5,0), datetime(2009,10,1,6,0), 
     ) 

    def test_not_overlap_greater_than(self): 
     assert not dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,7,30), datetime(2009,10,1,8,0), 
     ) 

    def test_not_overlap_start_equal(self): 
     assert not dt_windows_intersect(
      datetime(2009,10,1,6,0), datetime(2009,10,1,7,0), 
      datetime(2009,10,1,7,0), datetime(2009,10,1,8,0), 
     ) 

Answer 3

आपके प्रश्न का उत्तर करने के लिए:

Is there a data structure like that available in Python? 

कोई वहाँ नहीं है। लेकिन सूची में रखने के लिए सूची को रखने और ओवरलैप की जांच करने के लिए आप आसानी से एक सूची का उपयोग करके मूल संरचना और कोड के रूप में एक सूची का उपयोग कर स्वयं को बना सकते हैं।

class RangeList(list): 
"""Maintain ordered list of non-overlapping ranges""" 
    def add(self, range): 
    """Add a range if no overlap else reject it""" 
     lo = 0; hi = len(self) 
     while lo < hi: 
      mid = (lo + hi)//2 
      if range < self[mid]: hi = mid 
      else: lo = mid + 1 
     if overlaps(range, self[lo]): 
      print("range overlap, not added") 
     else: 
      self.insert(lo, range) 

मैं अभ्यास के रूप में overlaps फ़ंक्शन छोड़ देता हूं। (यह कोड अवांछित है और कुछ tweeking की आवश्यकता हो सकती है)

Answer 4

ऐसा लगता है कि आप bisect's insort_right/insort_left कुछ चाहते हैं। बिसेक्ट मॉड्यूल सूचियों और tuples के साथ काम करता है।

import bisect 

l = [(0, 100), (150, 300), (500, 1000)] 
bisect.insort_right(l, (250, 400)) 
print l # [(0, 100), (150, 300), (250, 400), (500, 1000)] 
bisect.insort_right(l, (399, 450)) 
print l # [(0, 100), (150, 300), (250, 400), (399, 450), (500, 1000)] 

आप अपनी खुद की overlaps समारोह है, जो आप insort उपयोग करने से पहले जाँच करने के लिए उपयोग कर सकते हैं लिख सकते हैं।

मुझे लगता है कि आपने अपनी संख्याओं के साथ गलती की है क्योंकि (250, 400)(150, 300) ओवरलैप करता है। overlaps() इसलिए की तरह लिखा जा सकता है:

def overlaps(inlist, inrange): 
    for min, max in inlist: 
     if min < inrange[0] < max and max < inrange[1]: 
      return True 
    return False 

Answer 5

हो सकता है कि मॉड्यूल द्विविभाजित सरल निम्नलिखित समारोह की तुलना में बेहतर हो सकता है? :

li = [(0, 100), (150, 220), (250, 400), (500, 1000)] 


def verified_insertion(x,L): 
    u,v = x 
    if v<L[0][0]: 
     return [x] + L 
    elif u>L[-1][0]: 
     return L + [x] 
    else: 
     for i,(a,b) in enumerate(L[0:-1]): 
      if a<u and v<L[i+1][0]: 
       return L[0:i+1] + [x] + L[i+1:] 
    return L 


lo = verified_insertion((-10,-2),li) 

lu = verified_insertion((102,140),li) 

le = verified_insertion((222,230),li) 

lee = verified_insertion((234,236),le) # <== le 

la = verified_insertion((408,450),li) 

ly = verified_insertion((2000,3000),li) 

for w in (lo,lu,le,lee,la,ly): 
    print li,'\n',w,'\n' 

फ़ंक्शन तर्क के रूप में पारित सूची को संशोधित किए बिना एक सूची देता है।

परिणाम

[(0, 100), (150, 220), (250, 400), (500, 1000)] 
[(-10, -2), (0, 100), (150, 220), (250, 400), (500, 1000)] 

[(0, 100), (150, 220), (250, 400), (500, 1000)] 
[(0, 100), (102, 140), (150, 220), (250, 400), (500, 1000)] 

[(0, 100), (150, 220), (250, 400), (500, 1000)] 
[(0, 100), (150, 220), (222, 230), (250, 400), (500, 1000)] 

[(0, 100), (150, 220), (250, 400), (500, 1000)] 
[(0, 100), (150, 220), (222, 230), (234, 236), (250, 400), (500, 1000)] 

[(0, 100), (150, 220), (250, 400), (500, 1000)] 
[(0, 100), (150, 220), (250, 400), (408, 450), (500, 1000)] 

[(0, 100), (150, 220), (250, 400), (500, 1000)] 
[(0, 100), (150, 220), (250, 400), (500, 1000), (2000, 3000)]