python - किसी सूची में कोई मान मौजूद है या नहीं, यह जांचने का सबसे तेज़ तरीका

performance list (9)

जैसा कि दूसरों ने कहा है, बड़ी सूचियों के लिए बहुत धीमी हो सकती है। यहां set , set और bisect के प्रदर्शन की कुछ तुलनाएं दी गई हैं। ध्यान दें कि समय (दूसरे में) लॉग स्केल में है।

परीक्षण के लिए कोड:

import random
import bisect
import matplotlib.pyplot as plt
import math
import time

def method_in(a,b,c):
    start_time = time.time()
    for i,x in enumerate(a):
        if x in b:
            c[i] = 1
    return(time.time()-start_time)   

def method_set_in(a,b,c):
    start_time = time.time()
    s = set(b)
    for i,x in enumerate(a):
        if x in s:
            c[i] = 1
    return(time.time()-start_time)

def method_bisect(a,b,c):
    start_time = time.time()
    b.sort()
    for i,x in enumerate(a):
        index = bisect.bisect_left(b,x)
        if index < len(a):
            if x == b[index]:
                c[i] = 1
    return(time.time()-start_time)

def profile():
    time_method_in = []
    time_method_set_in = []
    time_method_bisect = []

    Nls = [x for x in range(1000,20000,1000)]
    for N in Nls:
        a = [x for x in range(0,N)]
        random.shuffle(a)
        b = [x for x in range(0,N)]
        random.shuffle(b)
        c = [0 for x in range(0,N)]

        time_method_in.append(math.log(method_in(a,b,c)))
        time_method_set_in.append(math.log(method_set_in(a,b,c)))
        time_method_bisect.append(math.log(method_bisect(a,b,c)))

    plt.plot(Nls,time_method_in,marker='o',color='r',linestyle='-',label='in')
    plt.plot(Nls,time_method_set_in,marker='o',color='b',linestyle='-',label='set')
    plt.plot(Nls,time_method_bisect,marker='o',color='g',linestyle='-',label='bisect')
    plt.xlabel('list size', fontsize=18)
    plt.ylabel('log(time)', fontsize=18)
    plt.legend(loc = 'upper left')
    plt.show()

मैं यह जानने का सबसे तेज़ तरीका खोज रहा हूं कि किसी सूची में कोई मान मौजूद है (इसमें लाखों मूल्यों वाली एक सूची) और इसकी अनुक्रमणिका क्या है? मुझे पता है कि सूची में सभी मूल्य मेरे उदाहरण की तरह अद्वितीय हैं।

पहली विधि मैं कोशिश करता हूं (3.8sec मेरे असली कोड में):

a = [4,2,3,1,5,6]

if a.count(7) == 1:
    b=a.index(7)
    "Do something with variable b"

दूसरी विधि मैं कोशिश करता हूं (2x तेज: 1.9sec मेरे असली कोड पर):

a = [4,2,3,1,5,6]

try:
    b=a.index(7)
except ValueError:
    "Do nothing"
else:
    "Do something with variable b"

उपयोगकर्ता से प्रस्तावित तरीके (2.74sec मेरे असली कोड पर):

a = [4,2,3,1,5,6]
if 7 in a:
    a.index(7)

मेरे वास्तविक कोड में, पहली विधि 3.81sec लेती है और दूसरी विधि 1.88sec लेती है। यह एक अच्छा सुधार है लेकिन:

मैं पाइथन / स्क्रिप्टिंग के साथ एक नौसिखिया हूं और मैं जानना चाहता हूं कि एक ही चीज करने के लिए सबसे तेज़ तरीका मौजूद है और अधिक प्रक्रिया समय बचाता है?

मेरे आवेदन के लिए अधिक विशिष्ट व्याख्या:

ब्लेंडर के एपीआई में कणों की एक सूची तक पहुंच सकते हैं:

particles = [1,2,3,4...etc.]

वहां से, मैं इसके स्थान तक पहुंच सकता हूं:

particles[x].location = [x,y,z]

और यदि प्रत्येक पड़ोसी के स्थान में खोज करके एक पड़ोसी मौजूद होता है तो मैं प्रत्येक कण के लिए परीक्षण करता हूं:

if [x+1,y,z] in particles.location
    "find the identity of this neighbour particles in x:the index 
    of the particles array"
    particles.index([x+1,y,z])

आप अपने सामान को एक set में डाल सकते हैं। सेट लुकअप बहुत ही कुशल हैं।

प्रयत्न:

s = set(a)
if 7 in s:
  # do stuff

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

ध्यान रखें कि ऑपरेटर न केवल समानता ( == ) का परीक्षण करता है बल्कि पहचान ( is ), list लिए तर्क में लगभग निम्न के बराबर है (यह वास्तव में सी में लिखा गया है और पाइथन नहीं, कम से कम सीपीथन में):

for element in s:
    if element is target:
        # fast check for identity implies equality
        return True
    if element == target:
        # slower check for actual equality
        return True
return False

ज्यादातर परिस्थितियों में यह विवरण अप्रासंगिक है, लेकिन कुछ परिस्थितियों में यह पाइथन नौसिखिया को आश्चर्यचकित कर सकता है, उदाहरण के लिए, numpy.NAN की असामान्य संपत्ति है जो स्वयं के बराबर नहीं है :

>>> import numpy
>>> numpy.NAN == numpy.NAN
False
>>> numpy.NAN is numpy.NAN
True
>>> numpy.NAN in [numpy.NAN]
True

इन असामान्य मामलों के बीच अंतर करने के लिए आप any() जैसे उपयोग कर सकते हैं:

>>> lst = [numpy.NAN, 1 , 2]
>>> any(element == numpy.NAN for element in lst)
False
>>> any(element is numpy.NAN for element in lst)
True

any() साथ list एस के लिए तर्क in ध्यान दें:

any(element is target or element == target for element in lst)

हालांकि, मुझे जोर देना चाहिए कि यह एक बढ़िया मामला है, और अधिकांश मामलों in ऑपरेटर में अत्यधिक अनुकूलित किया गया है और बिल्कुल वही है जो आप निश्चित रूप से चाहते हैं (या तो list साथ या set साथ)।

यह कोड नहीं है, लेकिन बहुत तेजी से खोज के लिए एल्गोरिदम

यदि आपकी सूची और जिस मूल्य को आप ढूंढ रहे हैं वह सभी संख्याएं हैं, तो यह बहुत सरल है, यदि स्ट्रिंग्स: नीचे देखें:

-लेट "एन" आपकी सूची की लंबाई हो
- वैकल्पिक कदम: यदि आपको तत्व की अनुक्रमणिका की आवश्यकता है: तत्वों की वर्तमान अनुक्रमणिका (0 से n-1) के साथ सूची में दूसरा स्तंभ जोड़ें - बाद में देखें
अपनी सूची या इसकी एक प्रति ऑर्डर करें (.sort ())
फन्दा बनाना:
- सूची के एन / 2 वें तत्व में अपनी संख्या की तुलना करें
  - यदि बड़ा हो, तो सूचकांक n / 2-n के बीच फिर से लूप करें
  - यदि छोटे, सूचकांक 0-एन / 2 के बीच फिर से लूप
  - यदि वही: आपको यह मिला
सूची को तब तक सीमित रखें जब तक आपको यह न मिल जाए या केवल 2 संख्याएं हों (नीचे जो आप ढूंढ रहे हैं उसके ऊपर)
यह 1.000.000 (लॉग (2) एन की सूची के लिए सबसे अधिक 19 चरणों में कोई तत्व पाएगा सटीक होना)

अगर आपको अपनी संख्या की मूल स्थिति की भी आवश्यकता है, तो इसे दूसरे, इंडेक्स कॉलम में देखें

यदि आपकी सूची संख्याओं से नहीं बनाई गई है, तो विधि अभी भी काम करती है और सबसे तेज़ होगी, लेकिन आपको उस फ़ंक्शन को परिभाषित करने की आवश्यकता हो सकती है जो तारों की तुलना / ऑर्डर कर सकती है

बेशक इसे क्रमबद्ध () विधि के निवेश की आवश्यकता है, लेकिन यदि आप जांच के लिए एक ही सूची का पुन: उपयोग करते रहें, तो यह इसके लायक हो सकता है

मेरे लिए यह 0.030 (वास्तविक), 0.026s (उपयोगकर्ता) और 0.004s (sys) था।

try:
print("Started")
x = ["a", "b", "c", "d", "e", "f"]

i = 0

while i < len(x):
    i += 1
    if x[i] == "e":
        print("Found")
except IndexError:
    pass

ऐसा लगता है कि आपके एप्लिकेशन को ब्लूम फ़िल्टर डेटा संरचना के उपयोग से लाभ प्राप्त हो सकता है।

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

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

a = [4,2,3,1,5,6]

index = dict((y,x) for x,y in enumerate(a))
try:
   a_index = index[7]
except KeyError:
   print "Not found"
else:
   print "found"

यह केवल एक अच्छा विचार होगा यदि कोई नहीं बदलता है और इस प्रकार हम एक बार dict () भाग कर सकते हैं और फिर बार-बार इसका उपयोग कर सकते हैं। यदि कोई बदलता है, तो आप जो भी कर रहे हैं उस पर अधिक जानकारी प्रदान करें।

7 in a

इसे करने का सबसे तेज़ और तेज़ तरीका।

आप एक set का उपयोग करने पर भी विचार कर सकते हैं, लेकिन आपकी सूची से उस सेट को बनाने में तेजी से सदस्यता परीक्षण से अधिक समय लग सकता है। निश्चित होने का एकमात्र तरीका अच्छी तरह से बेंचमार्क करना है। (यह भी निर्भर करता है कि आपको किन ऑपरेशन की आवश्यकता है)

मैं इसके बजाय setdefault विधि का उपयोग करने की सिफारिश करेंगे। ऐसा लगता है जैसे यह सब कुछ आप चाहते हैं।

>>> d = {'foo':'bar'}
>>> q = d.setdefault('foo','baz') #Do not override the existing key
>>> print q #The value takes what was originally in the dictionary
bar
>>> print d
{'foo': 'bar'}
>>> r = d.setdefault('baz',18) #baz was never in the dictionary
>>> print r #Now r has the value supplied above
18
>>> print d #The dictionary's been updated
{'foo': 'bar', 'baz': 18}