Какой самый быстрый способ узнать, существует ли значение в списке (список с миллионами значений) и каков его индекс?
Я знаю, что все значения в списке уникальны, как в этом примере.
Первый метод, который я пробую (3.8 секунды в моем реальном коде):.
a = [4,2,3,1,5,6]
if a.count(7) == 1:
b=a.index(7)
"Do something with variable b"
Второй метод, который я пробую (в 2 раза быстрее: 1.9 сек в моем реальном коде):.
a = [4,2,3,1,5,6]
try:
b=a.index(7)
except ValueError:
"Do nothing"
else:
"Do something with variable b"
Предложенные методы от пользователя Stack Overflow (2,74 секунды для моего реального кода):.
a = [4,2,3,1,5,6]
if 7 in a:
a.index(7)
В моем реальном коде первый метод занимает 3,81 сек, а второй - 1,88 сек. Это хорошее улучшение, но..:
Я новичок в Python/скриптинге, есть ли более быстрый способ сделать то же самое и сэкономить больше времени на обработку?
Более конкретная экспликация для моего приложения:
В API Blender я могу получить доступ к списку частиц:
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])
7 in a
Самый простой и быстрый способ.
Вы также можете рассмотреть возможность использования set
, но создание этого набора из вашего списка может занять больше времени, чем сэкономит более быстрое тестирование членства. Единственный способ быть уверенным - это хорошо провести сравнительный анализ. (это также зависит от того, какие операции вам нужны)
Как говорят другие, " В " может быть очень медленным для больших списков. Вот некоторые сравнения выступлений на в
, Set
и пополам
. Обратите внимание на время (в секундах) находится в логарифмической шкале.
Код для тестирования:
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()
Вы можете поместить свои элементы в set
. Поиск по множеству очень эффективен.
Попробуйте:
s = set(a)
if 7 in s:
# do stuff
edit В комментарии вы говорите, что хотели бы получить индекс элемента. К сожалению, у множеств нет понятия позиции элемента. Альтернативой может быть предварительная сортировка списка, а затем использование бинарного поиска каждый раз, когда вам нужно найти элемент.
def check_availability(element, collection: iter):
return element in collection
Использование
check_availability('a', [1,2,3,4,'a','b','c'])
Я считаю, что это самый быстрый способ узнать, находится ли выбранное значение в массиве.
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"
Это будет хорошая идея, если не't изменить и, таким образом, мы можем сделать дикт() один раз и затем использовать его повторно. Если же изменение, пожалуйста более подробно о том, что вы делаете.
Это звучит как ваше приложение может получить преимущество от использования Блум структуры данных фильтра.
Короче говоря, Блум-фильтр поиска вам могу сказать очень быстро, если значение явно не присутствует в наборе. В противном случае, вы можете делать медленный взгляд-чтобы получить индекс значение, возможно, мог бы быть в списке. Так что если ваше приложение стремится получить то "не нашли" в результате гораздо чаще, чем в "нашли" в результате, вы можете увидеть ускорить путем добавления фильтра Блума.
Подробные сведения Википедию обеспечивает хороший обзор как фильтры Блума работы, и веб-поиска "в библиотеке фильтр на Python Блум", которая обеспечит хотя бы пару полезных реализаций.
Имейте в виду, что в
оператор проверяет не только равенства ( = =
), но и личность (это
), в
логика `списка является примерно равно следующие (Это'ов на самом деле написано в C, а не на Python, хотя, по крайней мере в с CPython):
для элемента в S: если элементом является цель:
быстрый проверку на идентичность подразумевает равенство
возвращать true если элемент == цель:
медленнее проверять фактическое равенство
возвращать true возвращение ложным
В большинстве случаев эта деталь не имеет никакого значения, но в некоторых обстоятельствах он может оставить на Python новичок удивляет, например, библиотеки numpy.Нань имеет необычное свойство не равных себе:
>>> import numpy
>>> numpy.NAN == numpy.NAN
False
>>> numpy.NAN is numpy.NAN
True
>>> numpy.NAN in [numpy.NAN]
True
Чтобы различать эти необычные случаи можно использовать любой () как:
>>> lst = [numpy.NAN, 1 , 2]
>>> any(element == numpy.NAN for element in lst)
False
>>> any(element is numpy.NAN for element in lst)
True
Обратите внимание на в
логика списка
любой () будет:
any(element is target or element == target for element in lst)
Тем не менее, я должен подчеркнуть, что это крайний случай, и для подавляющего большинства случаев " в "оператора" оптимизировать " именно то, что вы хотите, конечно (либо с список
или множество
).
Или использовать __содержит__
:
sequence.__contains__(value)
Демо:
>>> l=[1,2,3]
>>> l.__contains__(3)
True
>>>
Это не код, а алгоритм очень быстрый поиск.
Если ваш список и значение, которое вы ищете, все цифры, это довольно просто. Если строки: посмотрите внизу:
Если вы также нуждаетесь в исходное положение, что искать его во втором столбце индекса.
Если ваш список состоит не из чисел, метод все еще работает и будет быстрым, но вы, возможно, потребуется определить функцию, которая может сравнить/строки заказа.
Конечно, это требует инвестиций отсортированный() метод, но если вы будете повторно использовать тот же список для проверки, может быть стоит.
@Уинстон Эверт'ный раствор дает большую скорость для очень больших списков, но в этом сайте StackOverflow ответ указывает, что попробовать:/кроме:/другое: строительство будет замедляться, если за исключением филиала часто достигается. В качестве альтернативы можно воспользоваться .получить()
метод дикт:
`` а = [4,2,3,1,5,6]
индекс = дикт((Г, X) для X, Y в перечислении(а))
показатель B=.вам(7, нет) если б не нет: "и что-то делать с переменной b"и ``
Этот .вам(ключ, значение по умолчанию) метод-это только для случая, когда вы можете'т гарантия на ключи в dict. Если клавиша * - * присутствует, то она возвращает значение (как бы
словарь[ключ]), но когда это не.получить()
возвращает значение по умолчанию (здесь нет
). Вы должны убедиться в этом случае, что выбранный по умолчанию не будет в "а".
Исходный вопрос был:
какой самый быстрый способ узнать, если значение существует в списке (список с миллионами значений в нем) и что его индекс?
Таким образом, есть две вещи, чтобы найти:
К этому, я изменил код @xslittlegrass для вычисления индексов во всех случаях, и добавил дополнительный метод.
Результаты
Методы:
Результаты показывают, что Способ 5 самый быстрый.
Интересно попробовать и комплект методы эквивалентного времени.
Тест Код
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()
Этот работал для меня: (понимание списка, один-лайнер)
[list_to_search_in.index(i) for i in list_from_which_to_search if i in list_to_search_in]
У меня был list_to_search_in
со всеми пунктами, и хотел вернуть индексами элементов в list_from_which_to_search`.
Это возвращает индексы в хороший список.
Для меня это был 0.030 сек (реальных), 0.026 сек (пользователей) и 0.004 сек (ому).
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
Код, чтобы проверить, существуют ли в массиве два элемента, произведение которых равно к:
n = len(arr1)
for i in arr1:
if k%i==0:
print(i)