Самый быстрый способ проверить, существует ли значение в списке

Question

Какой самый быстрый способ узнать, существует ли значение в списке (список с миллионами значений в нем) и каков его индекс?

Я знаю, что все значения в списке уникальны, как в этом примере.

Первый метод, который я пробую, - это (3,8 с в моем реальном коде):

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

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

Второй метод, который я пробую: (в два раза быстрее: для моего реального кода 1,9 с):

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

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

Предлагаемые методы от переполнения стека (2,74 с для моего реального кода):

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

В моем реальном коде первый метод занимает 3,81 секунды, а второй - 1,88 секунды. Это хорошее улучшение, но:

Я новичок в Python / scripting, и есть ли более быстрый способ сделать то же самое и сэкономить больше времени на обработку?

Более конкретное объяснение для моего приложения:

В Blender API я могу получить доступ к списку частиц:

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 particle in x:the particle's index
    in the array"
    particles.index([x+1,y,z])

Answer 1

7 in a

Самый простой и быстрый способ сделать это.

Вы также можете рассмотреть возможность использования set, но создание этого набора из вашего списка может занять больше времени, чем сэкономит более быстрое тестирование членства.Единственный способ быть уверенным - это хорошо оценивать.(это также зависит от того, какие операции вам требуются)

Answer 2

Как утверждают другие, in может быть очень медленным для больших списков.Вот несколько сравнений исполнений для in, 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()

Answer 3

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

Использование

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

Я считаю, что это самый быстрый способ узнать, находится ли выбранное значение в массиве.

Answer 4

Вы можете положить свои вещи в set.Наборы поиска очень эффективны.

Попробуйте:

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

edit В комментарии вы говорите, что хотите получить индекс элемента.К сожалению, наборы не имеют понятия положения элемента.Альтернативой является предварительная сортировка списка и затем использование бинарный поиск каждый раз, когда вам нужно найти элемент.

Answer 5

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 () один раз, а затем использовать ее повторно.Если a изменится, пожалуйста, предоставьте более подробную информацию о том, что вы делаете.

Answer 6

Похоже, что ваше приложение может получить преимущество от использования структуры данных Bloom Filter.

Короче говоря, просмотр фильтра Блума может очень быстро сказать вам, если значение ОПРЕДЕЛЕННО НЕ присутствует в наборе.В противном случае вы можете выполнить поиск медленнее, чтобы получить индекс значения, которое МОЖЕТ БЫТЬ в списке.Так что, если ваше приложение имеет тенденцию получать результат «не найден» гораздо чаще, чем результат «найден», вы можете увидеть ускорение, добавив фильтр Блума.

Для получения подробной информации, Википедия предоставляет хороший обзоркак работают фильтры Bloom, и веб-поиск «библиотеки фильтров Python Bloom» обеспечит как минимум пару полезных реализаций.

Answer 7

Имейте в виду, что оператор in проверяет не только равенство (==), но и тождество (is), логика in для list s приблизительно эквивалентна следующее (хотя на самом деле оно написано на C, а не на Python, по крайней мере, на 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

В большинстве случаев эта деталь не имеет значения, но в некоторых случаях она может удивить новичка в Python, например, 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 

Обратите внимание, логика in для list s с any() будет:

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

Однако я должен подчеркнуть, что это крайний случай, и в подавляющем большинстве случаев оператор in высоко оптимизирован и, разумеется, именно то, что вы хотите (либо с list, либо с set ).

Answer 8

Или используйте __contains__:

sequence.__contains__(value)

Демо:

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

Answer 9

Это не код, а алгоритм очень быстрого поиска.

Если ваш список и значение, которое вы ищете, все числа, это довольно просто. Если строки: посмотрите внизу:

• - пусть "n" будет длиной вашего списка
• -Дополнительный шаг: если вам нужен индекс элемента: добавьте второй список в список с текущим индексом элементов (от 0 до n-1) - см. Позже
• Заказать свой список или его копию (.sort ())
• Цикл:
  • Сравните ваш номер с n / 2-м элементом списка
    • Если больше, повторить цикл между индексами n / 2-n
    • Если меньше, повторите цикл между индексами 0-n / 2
    • Если то же самое: вы нашли это
• Продолжайте сужать список, пока не найдете его или не получите только 2 числа (ниже и выше того, который вы ищете)
• Это найдет любой элемент в не более 19 шагов для списка 1.000.000 (log (2) n, если быть точным)

Если вам также нужна исходная позиция вашего номера, найдите ее во втором столбце индекса.

Если ваш список не состоит из чисел, метод все еще работает и будет самым быстрым, но вам может потребоваться определить функцию, которая может сравнивать / упорядочивать строки.

Конечно, это требует вложений метода sorted (), но если вы продолжаете использовать один и тот же список для проверки, это может стоить.

Answer 10

present = False
searchItem = 'd'
myList = ['a', 'b', 'c', 'd', 'e']
if searchItem in myList:
   present = True
   print('present = ', present)
else:
   print('present = ', present)