2011-12-01 26 views
37

Chcę znaleźć indeks n-tego wystąpienia elementu na liście. np.Znajdź indeks pierwszego elementu na liście.

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

Jaki jest indeks n-tego prawdziwego? Gdybym chciał piąte wystąpienie (4th jeśli zero-indeksowane), odpowiedź jest 10.

mam wymyślić:

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

pamiętać, że x.index zwraca pierwsze wystąpienie lub pierwszego wystąpienia po jakimś punkt, a zatem, o ile mogę powiedzieć, nie jest rozwiązaniem.

Istnieje również rozwiązanie numpy dla przypadków podobnych do powyższych, np. przy użyciu cumsum i where, ale chciałbym wiedzieć, czy istnieje wolny od numerek sposób rozwiązania problemu.

Jestem zaniepokojony występem odkąd pierwszy raz to zetknąłem podczas implementacji Sieve of Eratostenes dla problemu Project Euler, ale jest to bardziej ogólne pytanie, które napotkałem w innych sytuacjach.

EDYCJA: Otrzymałem wiele wspaniałych odpowiedzi, więc zdecydowałem się przeprowadzić testy wydajności. Poniżej znajdują się czasy wykonania timeit w sekundach dla list z elementami len szukającymi wartości 4000'th/1000'th True. Listy są losowe Prawda/Fałsz. Kod źródłowy powiązany poniżej; to jest dotkliwy bałagan. Użyłem krótkich/zmodyfikowanych wersji nazw plakatów do opisania funkcji z wyjątkiem listcomp, co jest prostym rozumieniem listy powyżej.

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 

Rozwiązanie itertools firmy Hettinger jest prawie zawsze najlepsze. Rozwiązania taymon i graddy są najlepsze dla większości sytuacji, chociaż podejście do rozumienia list może być lepsze dla krótkich tablic, gdy chcesz n-tej instancji takiej, że n jest wysoka lub list, w której jest mniej niż n wystąpień. Jeśli jest szansa, że ​​wystąpiło mniej niż n wystąpień, początkowa kontrola count oszczędza czas. Ponadto graddy's jest bardziej efektywny przy wyszukiwaniu liczb zamiast True/False ... nie jest jasne, dlaczego tak się dzieje. Rozwiązania eyquem są w istocie równoważne z innymi z nieco mniejszym lub większym nakładem; eyquem_occur jest w przybliżeniu taki sam jak rozwiązanie taymon, a eyquem_occurrence jest podobne do listcomp.

+0

EDYCJA: Mój poprzedni komentarz zakładał, że zadałeś inne pytanie, a nie składnię. Przepraszam. Nie jestem facetem z Python, ale wydaje mi się, że powinienem móc policzyć do dowolnej liczby zdarzeń za pomocą pętli for, zwiększając licznik za każdym razem. Zamocuj to w pętli while. Tak więc, podczas gdy (amountOfTrues varatis

+3

+1 za zaległy zapis na temat porównań odpowiedzi. Dobra robota! –

Odpowiedz

34

Odpowiedź od @Taymon przy użyciu list.index była świetna.

FWIW, tutaj jest funkcjonalne podejście przy użyciu itertools module. Współpracuje z dowolnego wejścia iterowalny, nie tylko wymienia:

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

Przykładem jest dobre, bo to pokazuje się, jak skutecznie łączyć funkcjonalny zestaw narzędzi Pythona. Zauważ, że po skonfigurowaniu potoku nie ma żadnych podróży wokół pętli ewaluacyjnej Pythona - wszystko odbywa się z prędkością C, z niewielkim zasięgiem pamięci, z leniwą oceną, bez przypisań zmiennych i oddzielnie testowalnymi komponentami. IOW, to wszystko programiści funkcjonalne pomarzyć :-)

run Próbka:

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

Podoba mi się, chociaż byłbym skłonny podzielić pierwsze subcalculation out jako "def item_indices (iterable, item):" więc mógłbym dać mu docstring. – ncoghlan

+0

Awesome. Dlaczego nie jest to wbudowana metoda 'list'? – keflavich

+0

Sidenote: czy można zainstalować itertools 2.7 w python 2.6? Czy istnieją podstawowe niezgodności? Może powinienem zadać to jako inne pytanie ... – keflavich

27

nie mogę powiedzieć na pewno, że jest to najszybszy sposób, ale mogę sobie wyobrazić, że to będzie bardzo dobre: ​​

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

Odpowiedź jest i.

+0

Dobra racja ... to chyba bardziej skuteczne w większości przypadków niż pełne zrozumienie listy. – keflavich

+3

+1 Dobra robota. To jest czyste rozwiązanie, które maksymalnie wykorzystuje argument * start * do * list.index * :-) –

+0

Podoba mi się twój styl - wydaje się krótko zakodowany :) – Ralf

2

jeśli wydajność jest problemem i że jej lepiej iteracyjne normalnie (O (n)) zamiast listowego który zaczyna O (L), w którym L oznacza długość listy

Przykład: Rozważmy bardzo długiej listy i chcesz znaleźć pierwsze wystąpienie n = 1 to oczywiście lepiej, aby zatrzymać jak najszybciej znaleźć pierwsze wystąpienie

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

Jeżeli obawiasz się o wydajności, jesteś najlepszy off widząc jeśli istnieją algorytmiczne optymalizacje możesz zrobić. Na przykład, jeśli wywołujesz tę funkcję wiele razy na tych samych wartościach, możesz chcieć buforować poprzednie obliczenia (np. Po znalezieniu 50. wystąpienia elementu, możesz znaleźć poprzednie wystąpienie w czasie O(1)).

W przeciwnym razie chcesz się upewnić, że twoja technika działa na (leniwych) iteratorach.

Najbardziej * w * elegancki i wydajności szczęśliwy sposób mogę myśleć o jego realizacji jest:

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 

(jeśli troszczą się o różnicy pomiędzy wydajnością enumerate i innych technik, będziesz trzeba uciekać się do profilowania, zwłaszcza z numPy funkcji, które mogą odwoływać się do C)

aby Preprocesuj cały strumień i wsparcia O(1) zapytania:

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]} 
2
[y for y in enumerate(x) if y[1]==True][z][0] 

Uwaga: Tu Z jest occurance n'th,

+0

Bardzo elegancki. Wersja nieco jaśniejsza według mojego gustu: [i for i, e in enumerate (x) if e == True] [z]. – markolopa

2

rozwiązanie, które tworzy pierwszy list obiekt i zwraca element n-1 z tej listy: funkcja wystąpienie()

I rozwiązanie, które spełnia funkcjonalny program ers'dreams też, jak sądzę, za pomocą generatorów, bo je kocham: funkcja wystąpić()

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) 

wynik

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 

Drugie rozwiązanie wydaje się skomplikowane, ale to naprawdę nie jest. Nie musi przebiegać całkowicie przez iterację: proces zatrzymuje się, gdy tylko zostanie wykryte oczekiwane zdarzenie.

2

Oto kolejny sposób na znalezienie nth wystąpienie x na liście 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 
0

Oto sposób:
dla powyższego przykładu:

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

możemy zdefiniować funkcja 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] 

i jeśli zastosujemy funkcję:

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

wynik brzmi:

10 
0

myślę, że to powinno działać.

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 
Powiązane problemy