在列表中find第n个项目的索引

我想查找列表中第n个项目的索引。 例如,

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

什么是真正的指标? 如果我想要第五次出现(如果是零索引,则为第四次),答案是10。

我已经想出了:

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

请注意, x.index返回第一次出现或某个点后的第一次出现,因此,据我所知,不是一个解决scheme。

也有类似于上面的情况numpy的解决scheme,例如使用cumsumwhere ,但我想知道是否有一个numpy自由的方式来解决这个问题。

自从我第一次遇到这个问题以来,我担心的是性能问题,同时为EH 项目实施了Eratosthenes筛选,但这是我在其他情况下遇到的一个更普遍的问题。

编辑:我得到了很多很好的答案,所以我决定做一些性能testing。 以下列出了len元素search第4000个/ 1000个True的列表的时间执行时间(秒)。 该列表是随机的真/假。 下面链接的源代码; 这是一个混乱。 我使用海报名称的短/修改版本来描述listcomp之外的function,这是上面简单的列表理解。

 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解决scheme几乎总是最好的。 taymon's和graddy的解决scheme在大多数情况下是次最好的,但是当你想要第n个实例时,列表理解方法可以更好地适用于短arrays,使得n很高或列表中出现的次数less于n次。 如果出现less于n次的情况,初始count检查节省时间。 而且,当search数字而不是True / False时,graddy更有效率……不清楚原因是什么。 eyquem的解决scheme基本上等同于稍微多一点或less一些的开销; eyquem_occur与taymon的解决scheme大致相同,而eyquem_occurrence类似于listcomp。

@Taymon使用list.index的答案很好。

FWIW,这是一个使用itertools模块的function方法。 它适用于任何可迭代的input,而不仅仅是列表:

 >>> 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的function工具集。 注意,一旦stream水线设置完毕,Python的eval循环就不会出现,所有事情都以C语言实现,只需要很小的内存空间,懒惰的评估,没有可变的赋值以及单独的可testing组件。 IOW,这是一切function程序员的梦想:-)

样品运行:

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

我不能肯定地说这是最快的方法,但是我认为它会很好:

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

答案是i

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

注意:这里Z是第n次出现,

如果你关心性能,你最好看看是否有algorithm优化。 例如,如果你用相同的值多次调用这个函数,你可能希望caching以前的计算(例如,一旦你发现元素的第50次出现,你可以在O(1)时间内find任何以前的事件)。

否则,你想确保你的技术在(惰性)迭代器上工作。

我认为实现它的最优雅和性能快乐的方式是:

 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)

预处理整个stream并支持O(1)查询:

 from collections import * cache = defaultdict(list) for i,elem in enumerate(YOUR_LIST): cache[elem] += [i] # eg [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]} 

首先创build列表对象并返回此列表的第n-1个元素的解决scheme:function occurence()

还有一个解决scheme,也实现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 

第二个解决scheme看起来很复杂,但并不是真的。 它不需要完全遍历迭代器:只要find想要的事件,进程就会停止。

这里是另一种在列表itrbl查找xnth次出现的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 

如果效率是一个问题,我认为它更好地迭代通常(O(N)),而不是列表理解,其中L(L)其中L是列表的长度

例子:考虑一个非常大的列表,你想find第一个出现N = 1,只要你find第一个出现就明显停下来

 count = 0 for index,i in enumerate(L): if i: count = count + 1 if count==N: return index 

这里是一个方法:
对于上面的例子:

 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