Maneira mais rápida de verificar se existe um valor em uma lista

Qual é a maneira mais rápida de saber se existe um valor em uma lista (uma lista com milhões de valores) e qual é o seu índice?

Eu sei que todos os valores na lista são únicos, como neste exemplo.

O primeiro método que eu tento é (3,8 segundos no meu código real):

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

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

O segundo método que eu tento é (2x mais rápido: 1,9 segundos para o meu código real):

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

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

Métodos propostos pelo usuário do Stack Overflow (2,74 s para o meu código real):

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

No meu código real, o primeiro método leva 3,81 segundos e o segundo método 1,88 segundos. É uma boa melhoria, mas:

Sou iniciante em Python / script e existe uma maneira mais rápida de fazer as mesmas coisas e economizar mais tempo de processamento?

Explicações mais específicas para minha aplicação:

Na API do Blender, posso acessar uma lista de partículas:

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

De lá, eu posso acessar a localização de uma partícula:

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

E para cada partícula, testo se existe um vizinho pesquisando cada local da partícula da seguinte maneira:

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

7 in a

A maneira mais clara e rápida de fazer isso.

Você também pode considerar usar a set, mas a construção desse conjunto a partir da sua lista pode levar mais tempo do que o teste mais rápido da associação economizará. A única maneira de ter certeza é avaliar bem. (isso também depende de quais operações você precisa)

Conforme declarado por outros, inpode ser muito lento para listas grandes. Aqui estão algumas comparações das performances de in, sete bisect. Observe que o tempo (em segundo) está na escala do log.

Código para teste:

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

Você pode colocar seus itens em um set. As pesquisas de conjuntos são muito eficientes.

Tentar:

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

editar Em um comentário, você diz que deseja obter o índice do elemento. Infelizmente, os conjuntos não têm noção de posição do elemento. Uma alternativa é pré-classificar sua lista e usar a pesquisa binária toda vez que você precisar encontrar um elemento.

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

Uso

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

Eu acredito que esta é a maneira mais rápida de saber se um valor escolhido está em uma matriz.

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"

Isso só será uma boa idéia se a não mudar e, portanto, podemos executar a parte dict () uma vez e usá-la repetidamente. Se um mudar, forneça mais detalhes sobre o que você está fazendo.

A pergunta original era:

Qual é a maneira mais rápida de saber se existe um valor em uma lista (uma lista com milhões de valores) e qual é o seu índice?

Portanto, há duas coisas a encontrar:

1. é um item da lista e
2. qual é o índice (se estiver na lista).

Para isso, modifiquei o código @xslittlegrass para calcular índices em todos os casos e adicionei um método adicional.

Resultados

Os métodos são:

1. in - basicamente se x em b: retorna b.index (x)
2. try - try / catch em b.index (x) (ignora a necessidade de verificar se x em b)
3. set - basicamente se x no conjunto (b): retorna b.index (x)
4. bisect - ordena b com seu índice, procura binária por x em ordenada (b). Observe o mod de @xslittlegrass que retorna o índice no b classificado, em vez do b original)
5. reverse - forma um dicionário de pesquisa inversa d para b; então d [x] fornece o índice de x.

Os resultados mostram que o método 5 é o mais rápido.

Curiosamente, os métodos try e set são equivalentes no tempo.

Código de teste

import random
import bisect
import matplotlib.pyplot as plt
import math
import timeit
import itertools

def wrapper(func, *args, **kwargs):
    " Use to produced 0 argument function for call it"
    # Reference https://www.pythoncentral.io/time-a-python-function/
    def wrapped():
        return func(*args, **kwargs)
    return wrapped

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

def method_try(a,b,c):
    for i, x in enumerate(a):
        try:
            c[i] = b.index(x)
        except ValueError:
            c[i] = -1

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

def method_bisect(a,b,c):
    " Finds indexes using bisection "

    # Create a sorted b with its index
    bsorted = sorted([(x, i) for i, x in enumerate(b)], key = lambda t: t[0])

    for i,x in enumerate(a):
        index = bisect.bisect_left(bsorted,(x, ))
        c[i] = -1
        if index < len(a):
            if x == bsorted[index][0]:
                c[i] = bsorted[index][1]  # index in the b array

    return c

def method_reverse_lookup(a, b, c):
    reverse_lookup = {x:i for i, x in enumerate(b)}
    for i, x in enumerate(a):
        c[i] = reverse_lookup.get(x, -1)
    return c

def profile():
    Nls = [x for x in range(1000,20000,1000)]
    number_iterations = 10
    methods = [method_in, method_try, method_set_in, method_bisect, method_reverse_lookup]
    time_methods = [[] for _ in range(len(methods))]

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

        for i, func in enumerate(methods):
            wrapped = wrapper(func, a, b, c)
            time_methods[i].append(math.log(timeit.timeit(wrapped, number=number_iterations)))

    markers = itertools.cycle(('o', '+', '.', '>', '2'))
    colors = itertools.cycle(('r', 'b', 'g', 'y', 'c'))
    labels = itertools.cycle(('in', 'try', 'set', 'bisect', 'reverse'))

    for i in range(len(time_methods)):
        plt.plot(Nls,time_methods[i],marker = next(markers),color=next(colors),linestyle='-',label=next(labels))

    plt.xlabel('list size', fontsize=18)
    plt.ylabel('log(time)', fontsize=18)
    plt.legend(loc = 'upper left')
    plt.show()

profile()

Parece que seu aplicativo pode obter vantagens com o uso de uma estrutura de dados do Bloom Filter.

Em resumo, uma consulta ao filtro de bloom pode informar rapidamente se um valor NÃO está DEFINITIVAMENTE presente em um conjunto. Caso contrário, você pode fazer uma pesquisa mais lenta para obter o índice de um valor que POSSÍVEL PODE ESTAR na lista. Portanto, se seu aplicativo tende a obter o resultado "não encontrado" com muito mais frequência do que o resultado "encontrado", é possível acelerar a velocidade adicionando um filtro Bloom.

Para obter detalhes, a Wikipedia fornece uma boa visão geral de como os Filtros Bloom funcionam, e uma pesquisa na Web por "biblioteca de filtros python bloom" fornecerá pelo menos algumas implementações úteis.

Esteja ciente de que o inoperador testa não apenas igualdade ( ==), mas também identidade ( is), a inlógica para lists é aproximadamente equivalente à seguinte (na verdade, é escrita em C e não em Python, pelo menos em 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

Na maioria das circunstâncias, esse detalhe é irrelevante, mas em algumas circunstâncias ele pode surpreender um novato em Python, por exemplo, numpy.NANtem a propriedade incomum de não ser igual a si mesmo :

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

Para distinguir entre esses casos incomuns, você pode usar any()como:

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

Observe que a inlógica para lists com any()seria:

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

No entanto, devo enfatizar que este é um caso extremo e, para a grande maioria dos casos, o inoperador é altamente otimizado e exatamente o que você deseja, é claro (com um listou com um set).

Ou use __contains__:

sequence.__contains__(value)

Demo:

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

A solução do @Winston Ewert gera uma grande aceleração para listas muito grandes, mas essa resposta do stackoverflow indica que a construção try: / except: / else: será mais lenta se a ramificação de exceção for frequentemente alcançada. Uma alternativa é tirar proveito do .get()método para o ditado:

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

index = dict((y, x) for x, y in enumerate(a))

b = index.get(7, None)
if b is not None:
    "Do something with variable b"

O .get(key, default)método é apenas para o caso em que você não pode garantir que uma chave esteja no ditado. Se a chave estiver presente, ela retornará o valor (como seria dict[key]), mas, quando não estiver, .get()retornará o valor padrão (aqui None). Nesse caso, é necessário garantir que o padrão escolhido não esteja a.

Este não é o código, mas o algoritmo para pesquisas muito rápidas.

Se sua lista e o valor que você procura são todos números, isso é bastante direto. Se strings: olhe para o fundo:

• - Seja "n" o comprimento da sua lista
• -Etapa opcional: se você precisar do índice do elemento: adicione uma segunda coluna à lista com o índice atual de elementos (0 a n-1) - veja mais adiante
• Peça sua lista ou uma cópia dela (.sort ())
• Repetir:
  • Compare seu número com o n / 2 ° elemento da lista
    • Se maior, faça um loop novamente entre os índices n / 2-n
    • Se menor, faça um loop novamente entre os índices 0-n / 2
    • Se o mesmo: você o encontrou
• Continue restringindo a lista até encontrá-la ou ter apenas 2 números (abaixo e acima do que você está procurando)
• Ele encontrará qualquer elemento em no máximo 19 etapas para uma lista de 1.000.000 (log (2) n para ser mais preciso)

Se você também precisar da posição original do seu número, procure-o na segunda coluna do índice.

Se sua lista não for feita de números, o método ainda funcionará e será mais rápido, mas pode ser necessário definir uma função que possa comparar / ordenar seqüências de caracteres.

Obviamente, isso precisa do investimento do método classificado (), mas se você continuar reutilizando a mesma lista para verificação, pode valer a pena.

Como a pergunta nem sempre deve ser entendida como a maneira técnica mais rápida - eu sempre sugiro a maneira mais direta e rápida de entender / escrever: uma lista de compreensão, uma linha

[i for i in list_from_which_to_search if i in list_to_search_in]

Eu tinha um list_to_search_incom todos os itens e queria retornar os índices dos itens no list_from_which_to_search.

Isso retorna os índices em uma boa lista.

Existem outras maneiras de verificar esse problema - no entanto, as compreensões da lista são rápidas o suficiente, aumentando o fato de escrevê-lo rápido o suficiente para resolver um problema.

Para mim, foram 0,030 seg (real), 0,026 seg (usuário) e 0,004 seg (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

Código para verificar se existem dois elementos na matriz cujo produto é igual a k:

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