Найти индекс n-го элемента в списке
Я хочу найти индекс n-го вхождения элемента в список. например,
x=[False,True,True,False,True,False,True,False,False,False,True,False,True]
Каков индекс n'th true? Если бы я хотел пятое вхождение (четвертое, если нулевое индексирование), ответ будет равен 10.
Я придумал:
indargs = [ i for i,a in enumerate(x) if a ]
indargs[n]
Обратите внимание, что x.index возвращает первое вхождение или первое вхождение после некоторой точки, и, насколько я могу судить, это не решение.
Существует также решение в numpy для случаев, аналогичных описанным выше, например. используя cumsum и where, но я хотел бы знать, существует ли беспутный способ решить проблему.
Меня беспокоит производительность, так как я впервые столкнулся с этим, когда реализовал сито Eratosthenes для проблемы Project Euler, но это более общий вопрос, с которым я столкнулся в других ситуациях.
EDIT: у меня много отличных ответов, поэтому я решил сделать некоторые тесты производительности. Ниже timeit время выполнения в секундах для списков с len nelements, которые ищут 4000'th/1000th True. Списки имеют случайное значение True/False. Исходный код, указанный ниже; это прикосновение грязное. Я использовал короткие/измененные версии имен плакатов, чтобы описать функции, кроме listcomp, что является простым пониманием перечня выше.
True Test (100'th True in a list containing True/False)
nelements eyquem_occur eyquem_occurrence graddy taymon listcomp hettinger26 hettinger
3000: 0.007824 0.031117 0.002144 0.007694 0.026908 0.003563 0.003563
10000: 0.018424 0.103049 0.002233 0.018063 0.088245 0.003610 0.003769
50000: 0.078383 0.515265 0.002140 0.078074 0.442630 0.003719 0.003608
100000: 0.152804 1.054196 0.002129 0.152691 0.903827 0.003741 0.003769
200000: 0.303084 2.123534 0.002212 0.301918 1.837870 0.003522 0.003601
True Test (1000'th True in a list containing True/False)
nelements eyquem_occur eyquem_occurrence graddy taymon listcomp hettinger26 hettinger
3000: 0.038461 0.031358 0.024167 0.039277 0.026640 0.035283 0.034482
10000: 0.049063 0.103241 0.024120 0.049383 0.088688 0.035515 0.034700
50000: 0.108860 0.516037 0.023956 0.109546 0.442078 0.035269 0.035373
100000: 0.183568 1.049817 0.024228 0.184406 0.906709 0.035135 0.036027
200000: 0.333501 2.141629 0.024239 0.333908 1.826397 0.034879 0.036551
True Test (20000'th True in a list containing True/False)
nelements eyquem_occur eyquem_occurrence graddy taymon listcomp hettinger26 hettinger
3000: 0.004520 0.004439 0.036853 0.004458 0.026900 0.053460 0.053734
10000: 0.014925 0.014715 0.126084 0.014864 0.088470 0.177792 0.177716
50000: 0.766154 0.515107 0.499068 0.781289 0.443654 0.707134 0.711072
100000: 0.837363 1.051426 0.501842 0.862350 0.903189 0.707552 0.706808
200000: 0.991740 2.124445 0.498408 1.008187 1.839797 0.715844 0.709063
Number Test (750'th 0 in a list containing 0-9)
nelements eyquem_occur eyquem_occurrence graddy taymon listcomp hettinger26 hettinger
3000: 0.026996 0.026887 0.015494 0.030343 0.022417 0.026557 0.026236
10000: 0.037887 0.089267 0.015839 0.040519 0.074941 0.026525 0.027057
50000: 0.097777 0.445236 0.015396 0.101242 0.371496 0.025945 0.026156
100000: 0.173794 0.905993 0.015409 0.176317 0.762155 0.026215 0.026871
200000: 0.324930 1.847375 0.015506 0.327957 1.536012 0.027390 0.026657
Решение Hettinger itertools почти всегда лучше. решения taymon и graddy лучше всего подходят для большинства ситуаций, хотя подход к пониманию списка может быть лучше для коротких массивов, если вы хотите, чтобы n-й экземпляр такой, чтобы n был высоким или списки, в которых меньше n вхождений. Если есть вероятность того, что будет меньше n вхождений, начальная проверка count экономит время. Кроме того, graddy более эффективен при поиске чисел вместо True/False... непонятно, почему это так. решения eyquem по существу эквивалентны другим с немного более или менее накладными расходами; eyquem_occur примерно такая же, как и решение таймона, а eyquem_occurrence похожа на listcomp.
Ответы
Ответ 1
Ответ от @Taymon с использованием list.index был отличным.
FWIW, здесь используется функциональный подход с использованием модуля itertools. Он работает с любым итерируемым входом, а не только с списками:
>>> from itertools import compress, count, imap, islice
>>> from functools import partial
>>> from operator import eq
>>> def nth_item(n, item, iterable):
indicies = compress(count(), imap(partial(eq, item), iterable))
return next(islice(indicies, n, None), -1)
Пример хорош, потому что он показывает, как эффективно комбинировать набор инструментов Python. Обратите внимание, что после настройки конвейера нет никаких отключений в циклах eval loop Python - все делается на скорости C, с небольшим объемом памяти, с ленивой оценкой без назначений переменных и с отдельными тестируемыми компонентами. IOW, это все, о чем мечтают программисты-программисты: -)
Пример прогона:
>>> x = [False,True,True,False,True,False,True,False,False,False,True,False,True]
>>> nth_item(50, True, x)
-1
>>> nth_item(0, True, x)
1
>>> nth_item(1, True, x)
2
>>> nth_item(2, True, x)
4
>>> nth_item(3, True, x)
6
Ответ 2
Я не могу сказать наверняка, что это самый быстрый способ, но я думаю, что это будет очень хорошо:
i = -1
for j in xrange(n):
i = x.index(True, i + 1)
Ответ i.
Ответ 3
Если эффективность является проблемой, я думаю, что лучше ее итерации нормально (O (N)) вместо понимания списка, которое принимает O (L), где L - длина списка
Пример: рассмотрим очень огромный список и вы хотите найти первое появление N = 1, очевидно, что лучше остановиться, как только вы найдете первое вхождение
count = 0
for index,i in enumerate(L):
if i:
count = count + 1
if count==N:
return index
Ответ 4
Если вы заинтересованы в производительности, вам лучше понять, есть ли алгоритмическая оптимизация, которую вы можете сделать. Например, если вы вызываете эту функцию много раз по тем же значениям, вы можете захотеть кэшировать предыдущие вычисления (например, если вы обнаружите 50-е появление элемента, вы можете найти любое предыдущее вхождение в O(1) время).
В противном случае вы хотите убедиться, что ваша техника работает на (ленивых) итераторах.
Самый * в * элегантный и эффективный способ, я могу думать о его реализации, как:
def indexOfNthOccurrence(N, element, stream):
"""for N>0, returns index or None"""
seen = 0
for i,x in enumerate(stream):
if x==element:
seen += 1
if seen==N:
return i
(если вам действительно нужна разница в производительности между перечислением и другими методами, вам нужно прибегнуть к профилированию, особенно с функциями numpy, которые могут прибегать к C)
Для предварительной обработки всего потока и поддержки O(1) запросов:
from collections import *
cache = defaultdict(list)
for i,elem in enumerate(YOUR_LIST):
cache[elem] += [i]
# e.g. [3,2,3,2,5,5,1]
# 0 1 2 3 4 5 6
# cache: {3:[0,2], 1:[6], 2:[1,3], 5:[4,5]}
Ответ 5
[y for y in enumerate(x) if y[1]==True][z][0]
Примечание: здесь Z - это n-я степень,
Ответ 6
Решение, которое сначала создает объект списка и возвращает элемент nth-1 этого списка: function eventence()
И решение, которое, как я полагаю, также выполняет функциональные программисты, использует генераторы, потому что я их люблю: function происходить()
S = 'stackoverflow.com is a fantastic amazing site'
print 'object S is string %r' % S
print "indexes of 'a' in S :",[indx for indx,elem in enumerate(S) if elem=='a']
def occurence(itrbl,x,nth):
return [indx for indx,elem in enumerate(itrbl)
if elem==x ][nth-1] if x in itrbl \
else None
def occur(itrbl,x,nth):
return (i for pos,i in enumerate(indx for indx,elem in enumerate(itrbl)
if elem==x)
if pos==nth-1).next() if x in itrbl\
else None
print "\noccurence(S,'a',4th) ==",occurence(S,'a',4)
print "\noccur(S,'a',4th) ==",occur(S,'a',4)
результат
object S is string 'stackoverflow.com is a fantastic amazing site'
indexes of 'a' in S : [2, 21, 24, 27, 33, 35]
occur(S,'a',4th) == 27
occurence(S,'a',4th) == 27
Второе решение кажется сложным, но на самом деле это не так. Это не нужно запускать полностью через iterable: процесс останавливается, как только обнаружено необходимое обнаружение.
Ответ 7
Вот еще один способ найти nth появление x в списке itrbl:
def nthoccur(nth,x,itrbl):
count,index = 0,0
while count < nth:
if index > len(itrbl) - 1:
return None
elif itrbl[index] == x:
count += 1
index += 1
else:
index += 1
return index - 1
Ответ 8
вот путь:
для примера выше:
x=[False,True,True,False,True,False,True,False,False,False,True,False,True]
мы можем определить функцию find_index
def find_index(lst, value, n):
c=[]
i=0
for element in lst :
if element == value :
c .append (i)
i+=1
return c[n]
и если мы применим функцию:
nth_index = find_index(x, True, 4)
print nth_index
результат:
10
Ответ 9
Я думаю, что это должно сработать.
def get_nth_occurrence_of_specific_term(my_list, term, n):
assert type(n) is int and n > 0
start = -1
for i in range(n):
if term not in my_list[start + 1:]:
return -1
start = my_list.index(term, start + 1)
return start
