python - पायथन में, आप एक क्रमबद्ध सूची में थ्रेसहोल्ड से अधिक पहले मान की अनुक्रमणिका कैसे प्राप्त करते हैं?




algorithm search (2)

आप itertools का उपयोग करके गणना / जनरेटर दृष्टिकोण से बेहतर समय प्राप्त कर सकते हैं; मुझे लगता है कि Itertools हम सभी में प्रदर्शन mongers के लिए, अंतर्निहित एल्गोरिदम के तेजी से कार्यान्वयन प्रदान करता है। लेकिन bisect अभी भी तेज हो सकता है।

from itertools import islice, dropwhile

threshold = 5
seq = [1,4,6,9,11]
first_val = islice(dropwhile(lambda x: x<=threshold, seq),0,1)
result = seq.index(first_val)

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

from bisect import bisect_right

def find_gt(a, x):
    'Find leftmost value(switching this to index) greater than x'
    return bisect_right(a, x)

दिलचस्प सवाल

पायथन में, आप एक क्रमबद्ध सूची में थ्रेसहोल्ड से अधिक पहले मान की अनुक्रमणिका कैसे प्राप्त करते हैं?

मैं ऐसा करने के कई तरीकों के बारे में सोच सकता हूं (रैखिक खोज, हाथ से लिखित डिकोटॉमी, ..), लेकिन मैं इसे करने का एक उचित तरीके से एक साफ तरीका तलाश रहा हूं। चूंकि यह शायद एक बहुत ही आम समस्या है, मुझे यकीन है कि अनुभवी सॉर्स मदद कर सकते हैं!

धन्यवाद!


bisect पर एक नज़र डालें।

import bisect

l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

bisect.bisect(l, 55) # returns 7

रैखिक खोज के साथ इसकी तुलना करें:

timeit bisect.bisect(l, 55)
# 375ns


timeit next((i for i,n in enumerate(l) if n > 55), len(l))
# 2.24us


timeit next((l.index(n) for n in l if n > 55), len(l))
# 1.93us




bisection