python - पाइथन में बाइनरी सर्च(बायसेक्शन)




binary-search bisection (14)

Bisect_left / right के लिए कोड को क्यों न देखें और अपने उद्देश्य के अनुरूप इसे अनुकूलित करें।

इस तरह:

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x: 
            hi = mid
        else:
            return mid
    return -1

क्या कोई लाइब्रेरी फ़ंक्शन है जो किसी सूची / ट्यूपल पर बाइनरी खोज करता है और यदि पाया जाता है तो आइटम की स्थिति वापस लौटाता है और 'गलत' (-1, कोई नहीं, आदि) यदि नहीं?

मुझे bisect_left / bisect मॉड्यूल में सही कार्य मिलते हैं, लेकिन आइटम अभी भी सूची में नहीं है, भले ही वे एक स्थिति वापस कर दें। यह उनके इच्छित उपयोग के लिए बिल्कुल ठीक है, लेकिन मैं सिर्फ यह जानना चाहता हूं कि कोई आइटम सूची में है या नहीं (कुछ भी डालना नहीं चाहता)।

मैंने bisect_left का उपयोग करने के बारे में सोचा और फिर जांच कर रहा हूं कि उस स्थिति में आइटम जो मैं खोज रहा हूं उसके बराबर है, लेकिन यह बोझिल लगता है (और मुझे यह भी जांचने की सीमा है कि यह संख्या मेरी सूची में सबसे बड़ी संख्या से बड़ी हो सकती है) । यदि कोई अच्छा तरीका है तो मैं इसके बारे में जानना चाहता हूं।

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

इसके लिए एक शब्दकोश का उपयोग करना सबसे तेज़ तरीका होगा, लेकिन (लगभग) स्मृति आवश्यकताओं को दोगुना करेगा।

मैं इस सवाल से यह सोच रहा था कि मैंने पाइथन पुस्तकालयों में कुछ अनदेखा किया होगा। ऐसा लगता है कि मुझे अपना खुद का कोड लिखना होगा, जैसा कि मो ने सुझाव दिया था।


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

पाइथन बिसेक्ट का उपयोग यह इंगित करने के लिए किया जाता है कि एक क्रमबद्ध सूची में एक नया मान / खोज आइटम कहां डालना है। नीचे दिया गया कोड जो bisect_left का उपयोग करता है जो सूची / सरणी में खोज आइटम मिलने पर हिट की अनुक्रमणिका वापस कर देगा (नोट bisect और bisect_right प्रविष्टि बिंदु के रूप में हिट या मैच के बाद तत्व की अनुक्रमणिका लौटाएगा) यदि नहीं मिला , bisect_left क्रमबद्ध सूची में अगले आइटम पर एक इंडेक्स लौटाएगा जो खोज मूल्य == नहीं होगा। एकमात्र अन्य मामला यह है कि खोज वस्तु सूची के अंत में जाएगी जहां सूचकांक लौटाया गया सूची सूची / सरणी के अंत से अधिक होगा, और जो पाइथन द्वारा शुरुआती निकास के नीचे कोड में "और" तर्क हैंडल के साथ होगा। (पहली शर्त झूठी पायथन बाद की स्थितियों की जांच नहीं करता है)

#Code
from bisect import bisect_left
names=["Adam","Donny","Jalan","Zach","Zayed"]
search=""
lenNames = len(names)
while search !="none":
    search =input("Enter name to search for or 'none' to terminate program:")
    if search == "none":
        break
    i = bisect_left(names,search)
    print(i) # show index returned by Python bisect_left
    if i < (lenNames) and names[i] == search:
        print(names[i],"found") #return True - if function
    else:
        print(search,"not found") #return False – if function
##Exhaustive test cases:
##Enter name to search for or 'none' to terminate program:Zayed
##4
##Zayed found
##Enter name to search for or 'none' to terminate program:Zach
##3
##Zach found
##Enter name to search for or 'none' to terminate program:Jalan
##2
##Jalan found
##Enter name to search for or 'none' to terminate program:Donny
##1
##Donny found
##Enter name to search for or 'none' to terminate program:Adam
##0
##Adam found
##Enter name to search for or 'none' to terminate program:Abie
##0
##Abie not found
##Enter name to search for or 'none' to terminate program:Carla
##1
##Carla not found
##Enter name to search for or 'none' to terminate program:Ed
##2
##Ed not found
##Enter name to search for or 'none' to terminate program:Roger
##3
##Roger not found
##Enter name to search for or 'none' to terminate program:Zap
##4
##Zap not found
##Enter name to search for or 'none' to terminate program:Zyss
##5
##Zyss not found

डेव अब्राहम का समाधान अच्छा है। हालांकि मैंने इसे न्यूनतम किया होगा:

def binary_search(L, x):
    i = bisect.bisect_left(L, x)
    if i == len(L) or L[i] != x:
        return -1
    return i

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

def binary_search(values, key, lo=0, hi=None, length=None, cmp=None):
    """
    This is a binary search function which search for given key in values.
    This is very generic since values and key can be of different type.
    If they are of different type then caller must specify `cmp` function to
    perform a comparison between key and values' item.
    :param values:  List of items in which key has to be search
    :param key: search key
    :param lo: start index to begin search
    :param hi: end index where search will be performed
    :param length: length of values
    :param cmp: a comparator function which can be used to compare key and values
    :return: -1 if key is not found else index
    """
    assert type(values[0]) == type(key) or cmp, "can't be compared"
    assert not (hi and length), "`hi`, `length` both can't be specified at the same time"

    lo = lo
    if not lo:
        lo = 0
    if hi:
        hi = hi
    elif length:
        hi = length - 1
    else:
        hi = len(values) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if not cmp:
            if values[mid] == key:
                return mid
            if values[mid] < key:
                lo = mid + 1
            else:
                hi = mid - 1
        else:
            val = cmp(values[mid], key)
            # 0 -> a == b
            # > 0 -> a > b
            # < 0 -> a < b
            if val == 0:
                return mid
            if val < 0:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

यदि आप सिर्फ यह देखना चाहते हैं कि यह मौजूद है, तो सूची को एक निर्देश में बदलने का प्रयास करें:

# Generate a list
l = [n*n for n in range(1000)]

# Convert to dict - doesn't matter what you map values to
d = dict((x, 1) for x in l)

count = 0
for n in range(1000000):
    # Compare with "if n in l"
    if n in d:
        count += 1

मेरी मशीन पर, "अगर एन में एल" ने 37 सेकंड लिया, जबकि "अगर एन में डी" ने 0.4 सेकंड लिया।


यह उल्लेखनीय हो सकता है कि बिसेक्ट डॉक्स अब खोज उदाहरण प्रदान करते हैं: http://docs.python.org/library/bisect.html#searching-sorted-lists

(लौटने के बजाय ValueError बढ़ाना -1 या कोई भी अधिक पायथन नहीं है - list.index () उदाहरण के लिए करता है। लेकिन निश्चित रूप से आप उदाहरणों को अपनी आवश्यकताओं के अनुसार अनुकूलित कर सकते हैं।)


यह एक है:

  • रिकर्सिव नहीं है (जो इसे अधिक पुनरावर्ती दृष्टिकोण से अधिक स्मृति-कुशल बनाता है)
  • वास्तव में काम कर रहा है
  • तेजी से जब यह किसी भी अनावश्यक के बिना चलाता है और शर्तों
  • गणितीय दावे के आधार पर कि (निम्न + उच्च) / 2 की मंजिल हमेशा उच्च से छोटी है जहां कम सीमा कम है और उच्च ऊपरी सीमा है।
  • परीक्षण: डी
def binsearch(t, key, low = 0, high = len(t) - 1):
    # bisecting the range
    while low < high:
        mid = (low + high)//2
        if t[mid] < key:
            low = mid + 1
        else:
            high = mid
    # at this point 'low' should point at the place
    # where the value of 'key' is possibly stored.
    return low if t[low] == key else -1

यह मैनुअल से सही है:

http://docs.python.org/2/library/bisect.html

8.5.1। क्रमबद्ध सूची खोज रहे हैं

उपरोक्त bisect () फ़ंक्शन सम्मिलन बिंदु खोजने के लिए उपयोगी हैं लेकिन सामान्य खोज कार्यों के लिए उपयोग करने के लिए मुश्किल या अजीब हो सकते हैं। निम्नलिखित पांच कार्य दिखाते हैं कि क्रमबद्ध सूचियों के लिए उन्हें मानक लुकअप में कैसे परिवर्तित करें:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

तो मामूली संशोधन के साथ आपका कोड होना चाहिए:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

सरलतम है कि बिसेक्ट का उपयोग करें और यह देखने के लिए एक स्थिति वापस जांचें कि आइटम वहां है या नहीं:

def binary_search(a,x,lo=0,hi=-1):
    i = bisect(a,x,lo,hi)
    if i == 0:
        return -1
    elif a[i-1] == x:
        return i-1
    else:
        return -1

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

मूल प्रकार

स्ट्रिंग्स या इन्ट्स जैसे मूल प्रकारों के लिए यह बहुत आसान है - आपको बस की आवश्यकता है bisect मॉड्यूल और एक क्रमबद्ध सूची है:

>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False

आप डुप्लीकेट खोजने के लिए इसका भी उपयोग कर सकते हैं:

...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']

जाहिर है, अगर आप वांछित अगर उस सूचकांक के मूल्य के बजाय सूचकांक वापस कर सकते हैं।

वस्तुओं

कस्टम प्रकारों या ऑब्जेक्ट्स के लिए, चीजें थोड़ा सा ट्रिकियर होती हैं: आपको सही ढंग से तुलना करने के लिए बिसेक्ट प्राप्त करने के लिए समृद्ध तुलना विधियों को लागू करना सुनिश्चित करना होगा।

>>> import bisect
>>> class Tag(object):  # a simple wrapper around strings
...     def __init__(self, tag):
...         self.tag = tag
...     def __lt__(self, other):
...         return self.tag < other.tag
...     def __gt__(self, other):
...         return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']

यह कम से कम पायथन 2.7 -> 3.3 में काम करना चाहिए


यह कोड एक पुनरावर्ती तरीके से पूर्णांक सूचियों के साथ काम करता है। सबसे सरल केस परिदृश्य की तलाश में है, जो है: सूची लंबाई 2 से कम है। इसका मतलब है कि उत्तर पहले से ही है और सही उत्तर की जांच के लिए एक परीक्षण किया जाता है। यदि नहीं, तो मध्यम मान सेट किया गया है और सही होने के लिए परीक्षण किया गया है, यदि फ़ंक्शन को फिर से कॉल करके बायसेक्शन नहीं किया जाता है, लेकिन ऊपरी या निचली सीमा के रूप में मध्य मान को बाएं या दाएं स्थानांतरित करके सेट किया जाता है

def binary_search(intList, intValue, lowValue, highValue):
    if(highValue - lowValue) &lt 2:
        return intList[lowValue] == intValue or intList[highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue)/2)
    if intList[middleValue] == intValue:
        return True
    if intList[middleValue] > intValue:
        return binary_search(intList, intValue, lowValue, middleValue - 1)
   return binary_search(intList, intValue, middleValue + 1, highValue)

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi
    hi = hi if hi is not None else len(a)  # hi defaults to len(a)   
    pos = bisect_left(a, x, lo, hi)  # find insertion position
    return (pos if pos != hi and a[pos] == x else -1)  # don't walk off the end

def binary_search_length_of_a_list(single_method_list):
    index = 0
    first = 0
    last = 1

    while True:
        mid = ((first + last) // 2)
        if not single_method_list.get(index):
            break
        index = mid + 1
        first = index
        last = index + 1
    return mid

  • s एक सूची है।
  • binary(s, 0, len(s) - 1, find) प्रारंभिक कॉल है।
  • फ़ंक्शन क्वेरी किए गए आइटम की अनुक्रमणिका देता है। यदि ऐसी कोई वस्तु नहीं है तो यह -1 लौटाती है।

    def binary(s,p,q,find):
        if find==s[(p+q)/2]:
            return (p+q)/2
        elif p==q-1 or p==q:
            if find==s[q]:
                return q
            else:
                return -1
        elif find < s[(p+q)/2]:
            return binary(s,p,(p+q)/2,find)
        elif find > s[(p+q)/2]:
            return binary(s,(p+q)/2+1,q,find)
    




bisection