pyplot - title matplotlib python




Il modo più veloce per verificare se un valore esiste in un elenco (8)

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

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

O usare __contains__ :

sequence.__contains__(value)

demo:

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

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.


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.


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)

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


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.


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.





list