Bir değer bir listede var olup olmadığını kontrol etmek için en hızlı yolu

bir listede bir değerin olup olmadığını (içinde milyonlarca değere sahip bir liste) ve dizininin ne olduğunu bilmek için en hızlı yolu arıyorum? Listedeki tüm değerlerin örneğim gibi benzersiz olduğunu biliyorum.

denediğim ilk yöntem (gerçek kodumda 3.8 sn):

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

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

denediğim İkinci yöntem (2x faster: gerçek kodumda 1.9 sn):

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

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

Stackoverflow kullanıcıdan Önerilen yöntemler (gerçek kodumda 2.74 sn):

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

gerçek kodumda, ilk yöntem 3.81 saniye sürer ve İkinci yöntem 1.88 saniye sürer. İyi bir gelişme ama:

Python / scripting ile yeni başlayanım ve aynı şeyleri yapmak ve daha fazla işlem süresi kazanmak için en hızlı bir yol olup olmadığını bilmek istiyorum?

benim uygulama için daha spesifik explication:

Blender a API

parçacıkların bir listesine erişebilirsiniz:

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

oradan, onun konumuna erişebilirsiniz:

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

ve bir komşu arayarak varsa her parçacık için test her bir parçacığın bulunduğu yerde:

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])
538
tarihinde sordu Pleasant94 2011-09-27 19:23:26
kaynak

11 ответов

7 in a

bunu yapmak için en net ve en hızlı yolu.

bir set kullanmayı da düşünebilirsiniz, ancak listenizden bu seti oluşturmak, daha hızlı üyelik testinden daha fazla zaman alabilir. Emin olmanın tek yolu iyi davranmaktır. (bu da hangi işlemleri gerektirdiğine bağlıdır)

1074
cevap Rafe Kettler 2011-09-27 19:57:30
kaynak

diğerleri tarafından belirtildiği gibi, in büyük listeler için çok yavaş olabilir. İşte in , set ve bisect performansları bazı karşılaştırmalar vardır . Not: zaman (ikinci) günlük ölçeğinde olduğunu.

enter image description here

test kodu:

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()
113
cevap xslittlegrass 2018-04-04 06:28:15
kaynak
def check_availability(element, collection: iter):
    return element in collection

'

check_availability('a', [1,2,3,4,'a','b','c'])

bunun, seçilen bir değerin bir dizide olup olmadığını öğrenmenin en hızlı yolu olduğuna inanıyorum.

29
cevap Tiago Moutinho 2018-08-11 15:52:39
kaynak

bir içine öğeleri koyabilirsiniz set . Set aramaları çok etkilidir.

deneyin:

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

Düzenle bir yorumda elemanın dizinini almak istediğinizi söylüyorsunuz. Ne yazık ki, kümelerin öğe konumu kavramı yoktur. Bir alternatif listenizi önceden sıralamak ve daha sonra ikili arama bir öğe bulmak için her zaman kullanmaktır.

23
cevap NPE 2017-05-23 15:02:48
kaynak
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"

bu sadece bir değişiklik olmazsa iyi bir fikir olacaktır ve böylece dict() bölümünü bir kez yapabilir ve tekrar tekrar kullanabiliriz. Bir değişiklik yaparsa, ne yaptığınızı daha fazla ayrıntı verin.

14
cevap Winston Ewert 2011-09-27 20:26:35
kaynak

uygulamanız bir Bloom filtre veri yapısı kullanımından avantaj elde edebilirsiniz gibi geliyor.

Kısacası, bir bloom filtre look-up bir değer kesinlikle bir sette mevcut değilse çok hızlı bir şekilde söyleyebilirim. Aksi takdirde, muhtemelen listede olabilecek bir değerin dizinini almak için daha yavaş bir görünüm yapabilirsiniz. Uygulamanız "bulunamadı" sonucunu çok daha sık almaya eğilimliyse, "bulunan" sonuç, bir çiçek ekleyerek bir hız görebilirsiniz Filtre.

ayrıntılar için Wikipedia, Bloom filtrelerinin nasıl çalıştığına iyi bir genel bakış sağlar ve "python bloom filtre Kütüphanesi" için bir web araması en azından birkaç yararlı uygulama sağlayacaktır.

5
cevap matt2000 2016-01-28 01:46:39
kaynak

in operatörünün sadece eşitlik ( == ) değil, aynı zamanda kimlik ( is ), in mantığı list S için kabaca eşdeğerdir.

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

çoğu durumda bu ayrıntı alakasız, ancak bazı durumlarda bir Python acemi bırakabilir sürpriz, örneğin, numpy.NAN :

kendisine eşit olmamanın olağandışı özelliğine sahiptir
>>> import numpy
>>> numpy.NAN == numpy.NAN
False
>>> numpy.NAN is numpy.NAN
True
>>> numpy.NAN in [numpy.NAN]
True

gibi any() kullanabilirsiniz bu sıradışı durumlar arasında ayırt etmek:

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

not in list s any() için mantık olurdu:

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

Bununla birlikte, bunun bir kenar davası olduğunu ve büyük çoğunluğu için vurgulamalıyım in operatörü son derece optimize edilmiş ve elbette tam olarak ne istediğinizi ( list veya set ile ).

3
cevap Chris_Rands 2018-02-19 17:05:41
kaynak

bu kod değil, çok hızlı arama için algoritma

listeniz ve aradığınız değer tüm sayılardır, bu oldukça basittir, eğer dizeler: aşağıya bakın:

  • - "n" listenizin uzunluğu olsun
  • - isteğe bağlı adım: öğenin dizinine ihtiyacınız varsa: öğelerin geçerli diziniyle (0-n-1) listeye ikinci bir sütun ekleyin - daha sonra
  • bölümüne bakın
  • listenizi veya bunun bir kopyasını sipariş (.sıralama ())
  • döngü:
    • numaranızı listenin n/2. öğesine karşılaştırın
      • daha büyükse, n/2-n
      • indeksleri arasında tekrar döngü
      • daha küçükse, 0-n/2
      • indeksleri arasında tekrar döngü
      • eğer aynı: bunu buldum
  • listeyi bulana kadar daraltmaya devam edin ya da sadece 2 numara var (aşağıda ve aradığınız birinin üstünde)
  • bu 1.000.000 (log(2)n kesin olmak gerekirse)
  • bir liste için en fazla 19 adımda herhangi bir öğeyi bulacaksınız

numaranızın orijinal konumuna da ihtiyacınız varsa, ikinci, dizin sütununda

arayın

listeniz sayılardan yapılmazsa, yöntem hala çalışır ve en hızlı olacaktır, ancak bir işlev tanımlamanız gerekebilir hangi karşılaştırın / sipariş dizeleri

tabii ki bu sıralama() yönteminin yatırımına ihtiyaç duyar, ancak kontrol etmek için aynı listeyi yeniden kullanmaya devam ederseniz,

değerinde olabilir
1
cevap Adam 2015-09-24 19:28:47
kaynak

benim için 0.030 s(gerçek), 0.026 s(kullanıcı) ve 0.004 s(sys) idi.

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
1
cevap Tabin1000 2017-12-29 11:28:36
kaynak
present = False
searchItem = 'd'
myList = ['a', 'b', 'c', 'd', 'e']
if searchItem in myList:
   present = True
   print('present = ', present)
else:
   print('present = ', present)
0
cevap Hafizur Rahman 2018-04-09 02:55:04
kaynak

kodu, ürünü k'ye eşit olan dizide iki öğenin olup olmadığını kontrol etmek için.

    n=len(arr1)
    for i in arr1:
        if k%i==0 :
            print(i)
0
cevap ravi tanwar 2018-07-19 14:24:50
kaynak

Diğer sorular python performance list