Kolejność elementów listy spełniających warunek

Question

Załóżmy Mam listę tego typu:

# 0 1 2 3 4 5 6 7 8 9 10 11 -- list index 
li=[-1, -1, 2, 2, -1, 1, 1, 1, 1, 1, -1, -1 ] 

Chcę znaleźć każdego indeksu, dla którego wartość jest taka sama dla n następujących indeksów.

mogę to zrobić (mozolnie) w ten sposób:

def sub_seq(li,n): 
    ans={} 
    for x in set(li): 
     ans[x]=[i for i,e in enumerate(li[:-n+1]) if all(x==y for y in li[i:i+n])] 

    ans={k:v for k,v in ans.items() if v} 

    return ans 

li=[-1, -1, 2, 2, -1, 1, 1, 1, 1, 1, -1, -1] 
for i in (5,4,3,2): 
    print i, sub_seq(li,i)  

Wydruki:

5 {1: [5]} 
4 {1: [5, 6]} 
3 {1: [5, 6, 7]} 
2 {1: [5, 6, 7, 8], 2: [2], -1: [0, 10]} 

Czy istnieje lepszy sposób to zrobić?

Answer 1

Analizowanie danych jest zwykle łatwiejsze, jeśli najpierw przekształcisz je w wygodną formę. W tym przypadku, run-length-encoding byłby dobry punkt wyjścia:

from itertools import groupby, accumulate 
from collections import defaultdict 

def sub_seq(li, n): 
    d = defaultdict(list) 
    rle = [(k, len(list(g))) for k, g in groupby(li)] 
    endpoints = accumulate(size for k, size in rle) 
    for end_index, (value, count) in zip(endpoints, rle): 
     for index in range(end_index - count, end_index - n + 1): 
      d[value].append(index) 
    return dict(d) 

Answer 2

Osobiście uważam, że jest to trochę bardziej czytelne, konstruuje mniej obiektów, a ja przypuszczam, że działa szybciej.

li=[-1, -1, 2, 2, -1, 1, 1, 1, 1, 1, -1, -1 ] 

results = [] 
i = 0 
while i < len(li): 
    j = i + 1 
    while j < len(li) and li[i] == li[j]: 
     j += 1 
    results.append((i,li[i],j-i)) 
    i = j 

print results #[(0, -1, 2), (2, 2, 2), (4, -1, 1), (5, 1, 5), (10, -1, 2)] 

Answer 3

Jak Raymond Hettinger wskazuje w swej odpowiedzi, groupby ułatwia sprawdzić kolejne wartości. Jeśli również wyliczyć listę, można zachować odpowiednie indeksy i dodać je do słownika (używam defaultdict aby funkcję jak najkrótsze):

from itertools import groupby 
from operator import itemgetter 
from collections import defaultdict 

li = [-1, -1, 2, 2, -1, 1, 1, 1, 1, 1, -1, -1] 

def sub_seq(li, n): 
    res = defaultdict(list) 
    for k, g in groupby(enumerate(li), itemgetter(1)): 
     l = list(map(itemgetter(0), g)) 
     if n <= len(l): res[k] += l[0:len(l)-n+1] 
    return res 

for i in (5,4,3,2): 
    print i, sub_seq(li,i) 

która drukuje:

5 defaultdict(<type 'list'>, {1: [5]}) 
4 defaultdict(<type 'list'>, {1: [5, 6]}) 
3 defaultdict(<type 'list'>, {1: [5, 6, 7]}) 
2 defaultdict(<type 'list'>, {1: [5, 6, 7, 8], 2: [2], -1: [0, 10]})