Подтвердить что ты не робот

Найти индекс 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.

4b9b3361

ОТВЕТЫ

Ответ 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