Tìm chỉ mục của mục thứ n trong danh sách

Question

Tôi muốn tìm chỉ mục về lần xuất hiện thứ n của một mục trong danh sách. ví dụ:

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

Chỉ số của thực tế là gì? Nếu tôi muốn sự xuất hiện thứ năm (4 nếu zero-lập chỉ mục), câu trả lời là 10.

tôi đã đi lên với:

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

Lưu ý rằng x.index trở sự xuất hiện đầu tiên hoặc sự xuất hiện đầu tiên sau khi một số điểm, và do đó theo như tôi có thể nói không phải là một giải pháp.

Ngoài ra còn có một giải pháp cho các trường hợp tương tự như trên, ví dụ: bằng cách sử dụng cumsum và where, nhưng tôi muốn biết liệu có một cách miễn phí không giải quyết được vấn đề không.

Tôi lo ngại về hiệu suất kể từ lần đầu tiên tôi gặp điều này trong khi triển khai Sieve of Eratosthenes cho vấn đề Project Euler, nhưng đây là một câu hỏi chung mà tôi gặp phải trong các tình huống khác.

EDIT: Tôi đã nhận được rất nhiều câu trả lời tuyệt vời, vì vậy tôi đã quyết định thực hiện một số thử nghiệm hiệu suất. Dưới đây là timeit thời gian thực hiện tính bằng giây đối với các danh sách có len số lần tìm kiếm sự thật 4000'th/1000'th. Các danh sách là ngẫu nhiên Đúng/Sai. Mã nguồn được liên kết bên dưới; đó là một cảm ứng lộn xộn. Tôi đã sử dụng các phiên bản ngắn/sửa đổi của tên của các áp phích để mô tả các chức năng ngoại trừ listcomp, đây là danh sách hiểu đơn giản ở trên.

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 

Giải pháp trình xử lý lặp của trình xử lý hầu như luôn là tốt nhất. Các giải pháp của taymon và graddy là tốt nhất cho hầu hết các tình huống, mặc dù phương pháp đọc danh sách có thể tốt hơn cho các mảng ngắn khi bạn muốn dụ n'th sao cho n cao hoặc danh sách trong đó có ít hơn n lần xuất hiện. Nếu có cơ hội có ít hơn n lần xuất hiện, kiểm tra ban đầu count sẽ tiết kiệm thời gian. Ngoài ra, graddy là hiệu quả hơn khi tìm kiếm các con số thay vì True/False ... không rõ ràng lý do tại sao. các giải pháp của eyquem về cơ bản tương đương với các giải pháp khác với chi phí cao hơn hoặc ít hơn; eyquem_occur tương đương với dung dịch của taymon, trong khi eyquem_occurrence tương tự như listcomp.

Answer 1

Câu trả lời từ @Taymon sử dụng list.index thật tuyệt vời.

FWIW, đây là cách tiếp cận chức năng sử dụng itertools module. Nó hoạt động với bất kỳ đầu vào có thể lặp lại nào, không chỉ danh sách:

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

Ví dụ này rất đẹp vì nó cho thấy cách kết hợp hiệu quả bộ công cụ chức năng của Python. Lưu ý, một khi đường ống được thiết lập, không có chuyến đi nào quanh vòng eval của Python - mọi thứ được thực hiện ở tốc độ C, với dấu chân bộ nhớ nhỏ, với đánh giá lười, không có bài tập biến, và với các thành phần có thể kiểm tra riêng. IOW, nó là tất cả các lập trình viên chức năng mơ về :-)

mẫu chạy:

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

Tôi không thể nói chắc chắn rằng đây là cách nhanh nhất, nhưng tôi tưởng tượng nó muốn được khá tốt:

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

Câu trả lời là i.

Answer 3

nếu hiệu quả là mối quan tâm tôi nghĩ rằng nó tốt hơn để lặp một cách bình thường (O (N)) thay vì danh sách hiểu mà mất O (L) trong đó L là chiều dài của danh sách

Ví dụ: Hãy xem xét một danh sách rất lớn và bạn muốn tìm sự xuất hiện đầu tiên N = 1 nó rõ ràng là tốt hơn để ngăn chặn ngay khi bạn tìm thấy sự xuất hiện đầu tiên

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

Answer 4

Nếu bạn đang quan tâm đến việc thực hiện, bạn là tốt nhất tắt nhìn thấy nếu có tối ưu hóa thuật toán bạn có thể làm. Ví dụ: nếu bạn gọi hàm này nhiều lần trên cùng một giá trị, bạn có thể muốn lưu lại các tính toán trước đó (ví dụ: khi bạn tìm thấy lần xuất hiện thứ 50 của một phần tử, bạn có thể tìm thấy bất kỳ lần xuất hiện nào trước đó trong thời gian O(1)).

Nếu không, bạn muốn đảm bảo kỹ thuật của bạn hoạt động trên các trình vòng lặp (lười).

Nhất * trong * tao nhã và hiệu suất-hạnh phúc cách tôi có thể nghĩ đến việc thực hiện nó là như sau:

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 

(nếu bạn thực sự quan tâm đến sự khác biệt về hiệu năng giữa enumerate và các kỹ thuật khác, bạn sẽ cần phải nghỉ mát để hồ sơ, đặc biệt là với các chức năng numPy, có thể dùng đến C)

để preprocess suối và hỗ trợ toàn bộ O(1) truy vấn:

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 5

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

Lưu ý: Đây Z là sự xuất hiện n'th,

Answer 6

Một giải pháp mà đầu tiên tạo ra một liệt kê đối tượng và trả về phần tử thứ n-1 của danh sách này: hàm xảy ra()

Và một giải pháp hoàn thành chương trình chức năng ers'dreams quá, tôi nghĩ rằng, sử dụng máy phát điện, bởi vì tôi yêu họ: chức năng xảy ra()

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) 

kết quả

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 

Giải pháp thứ hai có vẻ phức tạp nhưng nó không phải là thực sự. Nó không cần phải chạy hoàn toàn thông qua các iterable: quá trình dừng lại ngay sau khi sự xuất hiện mong muốn được tìm thấy.

Answer 7

Đây là một cách khác để tìm ra nth xảy ra x trong một danh sách 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 8

đây là một cách:
cho ví dụ trên:

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

chúng ta có thể định nghĩa một function 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] 

và nếu chúng ta áp dụng các chức năng:

nth_index = find_index(x, True, 4) 
print nth_index 

kết quả là:

10 

Answer 9

Tôi nghĩ rằng điều này sẽ làm việc.

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