Найти индекс n-го элемента в списке - PullRequest
39 голосов
/ 01 декабря 2011

Я хочу найти индекс 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.

Ответы [ 11 ]

0 голосов
/ 15 ноября 2012

вот способ:
для примера выше:

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
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...