python pyplot Il modo più veloce per verificare se un valore esiste in un elenco




title matplotlib python (10)

Sto cercando il modo più veloce per sapere se un valore esiste in una lista (una lista con milioni di valori al suo interno) e qual è il suo indice? So che tutti i valori nell'elenco sono unici come il mio esempio.

Il primo metodo che provo è (3.8sec nel mio codice reale):

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

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

Il secondo metodo che provo è (2x più veloce: 1.9sec sul mio vero codice):

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

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

Metodi proposti dall'utente StackOverflow (2.74sec sul mio codice reale):

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

Nel mio codice reale, il primo metodo accetta 3.81 sec e il secondo metodo accetta 1.88 sec. È un buon miglioramento ma:

Sono un principiante con Python / scripting e voglio sapere se esiste un modo più veloce per fare le stesse cose e risparmiare più tempo di elaborazione?

Una spiegazione più specifica per la mia domanda:

Nell'API del blender a può accedere a un elenco di particelle:

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

Da lì, posso accedere alla sua posizione:

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

E provo per ogni particella se esiste un vicino cercando nella posizione di ogni particella come:

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])

Come affermato da altri, in può essere molto lento per le liste di grandi dimensioni. Ecco alcuni confronti delle prestazioni per in , set e bisect . Notare che il tempo (in secondi) è nella scala di registro.

Codice per il test:

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()

Sembra che l'applicazione possa trarre vantaggio dall'uso di una struttura dati Bloom Filter.

In breve, una finestra di ricerca dei filtri di fioritura può dirti molto rapidamente se un valore è DEFINITAMENTE NON presente in un set. In caso contrario, è possibile eseguire una ricerca più lenta per ottenere l'indice di un valore che POSSIBILMENTE POTREBBE ESSERE nell'elenco. Quindi se la tua applicazione tende a ottenere il risultato "non trovato" molto più spesso del risultato "trovato", potresti vedere una accelerazione aggiungendo un filtro Bloom.

Per i dettagli, Wikipedia offre una buona panoramica di come funzionano i filtri Bloom e una ricerca sul web per "libreria filtro python bloom" fornirà almeno un paio di utili implementazioni.


def check_availability(element, collection: iter):
    return element in collection

uso

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

Credo che questo sia il modo più veloce per sapere se un valore scelto è in un array.


O usare __contains__ :

sequence.__contains__(value)

demo:

>>> l=[1,2,3]
>>> l.__contains__(3)
True
>>> 

codice per verificare se due elementi esistono in array il cui prodotto è uguale a k.

    n=len(arr1)
    for i in arr1:
        if k%i==0 :
            print(i)

Si noti che l'operatore in non solo prova l'uguaglianza ( == ) ma anche l'identità ( is ), la logica per la list s è approssimativamente equivalente alla seguente (in realtà è scritta in C e non in Python, almeno in CPython):

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

Nella maggior parte dei casi questo dettaglio è irrilevante, ma in alcune circostanze potrebbe lasciare un novizio Python sorpreso, per esempio, numpy.NAN ha l'insolita proprietà di non essere uguale a se stesso :

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

Per distinguere tra questi casi insoliti puoi usare any() come:

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

Notare che la logica per la list s con any() sarebbe:

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

Tuttavia, devo sottolineare che si tratta di un caso limite e che nella stragrande maggioranza dei casi l'operatore in è altamente ottimizzato e esattamente ciò che si desidera, ovviamente (con una list o con un set ).


questo non è il codice, ma l'algoritmo per la ricerca molto veloce

se la tua lista e il valore che stai cercando sono tutti numeri, questo è piuttosto semplice, se le stringhe: guarda in basso:

  • -let "n" è la lunghezza della tua lista
  • -opzione facoltativa: se hai bisogno dell'indice dell'elemento: aggiungi una seconda colonna alla lista con l'indice corrente degli elementi (da 0 a n-1) - vedi più avanti
  • ordina il tuo elenco o una copia di esso (.sort ())
  • loop through:
    • confronta il tuo numero con l'n / 2 ° elemento della lista
      • se è più grande, ricomincia da capo tra gli indici n / 2-n
      • se è più piccolo, ricomincia da capo tra gli indici 0-n / 2
      • se lo stesso: lo hai trovato
  • continua a restringere l'elenco finché non lo hai trovato o hai solo 2 numeri (sotto e sopra quello che stai cercando)
  • questo troverà qualsiasi elemento in al massimo 19 passi per un elenco di 1.000.000 (log (2) n per essere precisi)

se hai anche bisogno della posizione originale del tuo numero, cercalo nella seconda colonna dell'indice

se la tua lista non è fatta di numeri, il metodo funziona ancora e sarà più veloce, ma potrebbe essere necessario definire una funzione che può confrontare / ordinare le stringhe

ovviamente questo richiede l'investimento del metodo sorted (), ma se continui a riutilizzare lo stesso elenco per il controllo, potrebbe valerne la pena


Puoi mettere i tuoi oggetti in un set . Le ricerche di set sono molto efficienti.

Provare:

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

modifica In un commento dici di voler ottenere l'indice dell'elemento. Sfortunatamente, i set non hanno la nozione di posizione dell'elemento. Un'alternativa è preordinare l'elenco e quindi utilizzare la ricerca binaria ogni volta che è necessario trovare un elemento.


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"

Questa sarà solo una buona idea se non cambia e quindi possiamo fare la parte dict () una volta e poi usarla ripetutamente. Se un cambiamento cambia, ti preghiamo di fornire maggiori dettagli su ciò che stai facendo.


Per me era 0.030s (reale), 0.026s (utente) e 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






list