क्रमबद्ध सूची में अगले निचले आइटम को खोजें

Question

मान लें कि मेरे पास फ़्लोट्स की एक क्रमबद्ध सूची है। अब मैं किसी दिए गए मान के अगले निचले आइटम की अनुक्रमणिका प्राप्त करना चाहता हूं। सामान्य फॉर-लूप एप्रोच में ओ (एन) की जटिलता है। चूंकि सूची क्रमबद्ध की गई है, इसलिए इंडेक्स को ओ (लॉग एन) के साथ प्राप्त करने का एक तरीका होना चाहिए।

मेरे हे (एन) दृष्टिकोण:

index=0 
for i,value in enumerate(mylist): 
    if value>compareValue: 
     index=i-1 

वहाँ हे (लॉग एन) में है कि समस्या को हल करने के लिए एक डेटाप्रकार है?

सादर सेबस्टियन

Answer 1

आप वस्तु आप देख रहे हैं के सूचकांक मिलता है और कम प्रवेश पाने के लिए यह नीचे सूचकांक प्राप्त करने के लिए एक सरणी/सूची पर एक द्विआधारी खोज कर सकते हैं (जो दिए गए वहाँ वास्तव में एक कम प्रविष्टि है!)।

देखें: Binary search (bisection) in Python

सावधान रहें समानता के लिए जब comparing floating point numbers!

Answer 2

डेटाटाइप के बारे में प्रश्न के उत्तर का उत्तर देने के लिए: सामान्य अर्थ में, डेटाटाइप ओ (लॉग एन) समय में चीजों को खोजने के लिए सबसे उपयुक्त है (जबकि आवेषण और हटावट पर ओ (1) प्रदर्शन को बनाए रखने के दौरान!) बाइनरी पेड़ है । आप बाएं-दाएं फैसलों की एक श्रृंखला बनाकर इसमें चीजें पा सकते हैं, जो कि रैखिक सूची में बाइनरी खोज कैसे करते हैं, लेकिन यह (आईएमओ) थोड़ा अधिक अवधारणात्मक अंतर्ज्ञानी है।

उस ने कहा, मुझे पाइथन के बारे में बहुत कम पता है, बाइनरी पेड़ भाषा की मानक पुस्तकालय में नहीं लगते हैं। आपके आवेदन के लिए, इस उद्देश्य के लिए केवल कार्यान्वयन को शामिल करने का कोई लाभ नहीं होगा।

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

Answer 3

कैसे bisect?

>>> import bisect 
>>> float_list = [1.0, 1.3, 2.3, 4.5] 
>>> i = bisect.bisect_left(float_list, 2.5) 
>>> index = i - 1 
>>> index 
2 

आप कम से कम या अलग से सूची (इस मामले में index == -1) में सबसे कम/वाम-पंथी मूल्य के बराबर एक खोज मूल्य के मामले को संभालने के लिए हो सकता है।

समानता के मामले में आप जिस इंडेक्स को रखना चाहते हैं उसके आधार पर, आपको इसके बजाय bisect_right का उपयोग करना पड़ सकता है।

Answer 4

bisect मॉड्यूल का उपयोग करें। समारोह

bisect.bisect_left(mylist, compareValue) 

क्रमबद्ध व्यवस्था बनाए रखने के सूची में आइटम के लिए उचित सम्मिलन बिंदु देता है।

Answer 5

import bisect 

def next_lower_value(values_list, input_value): 
    index= bisect.bisect_left(values_list, input_value) 
    if index == 0: # there's not a "next lower value" 
     raise NotImplementedError # you must decide what to do here 
    else: 
     return values_list[index - 1] 

>>> l= [11, 15, 23, 28, 45, 63, 94] 
>>> next_lower_value(l, 64) 
63 
>>> next_lower_value(l, 63) 
45 
>>> next_lower_value(l, 1000) 
94 
>>> next_lower_value(l, 1) 
Traceback (most recent call last): 
    File "<pyshell#29>", line 1, in <module> 
    next_lower_value(l, 1) 
    File "<pyshell#26>", line 4, in next_lower_value 
    raise NotImplementedError # you must decide what to do here 
NotImplementedError 

आप सूचकांक और नहीं अगले कम मूल्य का अनुरोध के बाद से, समारोह next_lower_valueindex - 1 बजाय values_list[index - 1] वापस जाने के लिए बदल जाते हैं।

Answer 6

यदि मैं यह सही पढ़ रहा हूं, तो अगला निचला आइटम सूची में पहला आइटम है जो x से कम या उसके बराबर है।

def find_le(a, x): 
    'Find rightmost value less than or equal to x' 
    i = bisect_right(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError