Найти индекс n-го элемента в списке

Question

Я хочу найти индекс n-го вхождения элемента в список. например,

x=[False,True,True,False,True,False,True,False,False,False,True,False,True]

Каков индекс n-й истины? Если бы я хотел пятое вхождение (4-е, если индексировано нулями), ответ - 10.

Я придумал:

indargs = [ i for i,a in enumerate(x) if a ]
indargs[n]

Обратите внимание, что x.index возвращает первое вхождение или первое вхождение после некоторой точки, и поэтому, насколько я могу судить, не является решением.

Существует также решение numpy для случаев, аналогичных приведенным выше, например, используя cumsum и where, но я хотел бы знать, есть ли способ решения проблемы без ошибок.

Я обеспокоен производительностью с тех пор, как впервые столкнулся с этим при реализации Решета Эратосфена для проблемы Project Euler , но это более общий вопрос, с которым я сталкивался в других ситуациях.

РЕДАКТИРОВАТЬ: я получил много хороших ответов, поэтому я решил сделать несколько тестов производительности. Ниже приведены timeit времена выполнения в секундах для списков с len элементами, ища 4000-ю / 1000-ю Истину. Списки случайные 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

Решение itertools от Hettinger почти всегда является лучшим. Решения Тэймона и Грэдди следующие лучше всего подходят для большинства ситуаций, хотя подход к пониманию списков может быть лучше для коротких массивов, когда вы хотите, чтобы n-й экземпляр был таким, чтобы n был большим, или списки, в которых было меньше n случаев. Если существует вероятность того, что количество событий меньше n, первоначальная проверка count экономит время. Кроме того, Graddy более эффективен при поиске чисел вместо True / False ... не понятно, почему это так. решения eyquem по существу эквивалентны другим с чуть более или менее накладными расходами; eyquem_occur примерно совпадает с решением таймона, а eyquem_occurrence аналогичен listcomp.

Answer 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 в Python не происходит - все выполняется на скорости C, с небольшим объемом памяти, с ленивой оценкой, без присвоений переменных и с отдельно тестируемыми компонентами. И это все, о чем мечтают функциональные программисты: -)

Пример прогона:

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

Answer 2

Не могу с уверенностью сказать, что это самый быстрый способ, но я думаю, это было бы неплохо:

i = -1
for j in xrange(n):
    i = x.index(True, i + 1)

Ответ i.

Answer 3

Вот еще один способ найти 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

Answer 4

Решение, которое сначала создает объект списка и возвращает элемент nth-1 этого списка: function occurence ()

И решение, которое исполняет мечты функциональных программистов, я думаю, с использованием генераторов, потому что я их люблю: function emer ()

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

Второе решение кажется сложным, но на самом деле это не так. Он не должен проходить полностью через итерацию: процесс останавливается, как только будет найден искомый случай.

Answer 5

[y for y in enumerate(x) if y[1]==True][z][0]

Примечание: здесь Z - n-тое вхождение,

Answer 6

Если вас интересует производительность, лучше всего посмотреть, есть ли алгоритмическая оптимизация, которую вы можете сделать. Например, если вы вызываете эту функцию много раз для одних и тех же значений, вы можете кэшировать предыдущие вычисления (например, когда вы найдете 50-е вхождение элемента, вы можете найти любое предыдущее вхождение в O(1) time).

В противном случае вы хотите убедиться, что ваша техника работает на (ленивых) итераторах.

Самый * в * элегантный и приятный для исполнения способ, который я могу себе представить, это:

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

Answer 7

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

Answer 8

Вы можете использовать count :

from itertools import count

x = [False, True, True, False, True, False, True, False, False, False, True, False, True]


def nth_index(n, item, iterable):
    counter = count(1)
    return next((i for i, e in enumerate(iterable) if e == item and next(counter) == n), -1)


print(nth_index(3, True, x))

выход

4

Идея состоит в том, что из-за природы короткого замыкания e == item and next(counter) == n) выражение next(counter) == n вычисляется только при e == item, поэтому вы учитываете только элементы равные item.

Answer 9

Вы можете использовать next с enumerate и выражением генератора. itertools.islice позволяет нарезать итерацию по мере необходимости.

from itertools import islice

x = [False,True,True,False,True,False,True,False,False,False,True,False,True]

def get_nth_index(L, val, n):
    """return index of nth instance where value in list equals val"""
    return next(islice((i for i, j in enumerate(L) if j == val), n-1, n), -1)

res = get_nth_index(x, True, 3)  # 4

Если итератор исчерпан, то есть n -го вхождения указанного значения не существует, next может вернуть значение по умолчанию, в данном случае -1:

Answer 10

Я думаю, что это должно работать.

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