列表中满足条件的元素序列

Question

假设我有一个这种类型的列表:

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

我希望查找每个索引，该索引的值与接下来n个索引处的值相同。

我可以采用以下方式（虽然费力）：

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)    

输出：

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

有没有更好的方法来做这件事？

- user688635

---

你的意思是更好指的是减少 CPU 时间，还是指可读性更好？ - Patashu

我想要一个符合惯用语和易读性的程序。 - user688635

列表的值是否仅限于整数-1、1、2，还是可以是任何值或任何类型？ - dansalmo

它们可以是任何可哈希的值，例如整数、浮点数和字符串类型。但不能是子列表或类似的数据类型。 - user688635

Answer 1

如果您首先将数据转换为方便的形式，则分析数据通常更容易。在这种情况下，游程长度编码将是一个很好的起点：

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)

- Raymond Hettinger

---

我该如何将索引滚动到groupby返回的元组中？ - user688635

注意：itertools.accumulate() 适用于 Python 3.2+（文档提供了等效的代码）。NumPy 有等效的 numpy.cumsum()。 - Eric O. Lebigot

Answer 2

正如 Raymond Hettinger 在他的回答中指出的那样，groupby 使得检查连续值变得更容易。如果您还枚举列表，就可以保留相应的索引并将其添加到字典中（我使用 defaultdict 来使函数尽可能短）。

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)

哪个会打印：

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

- A. Rodas

Answer 3

我个人认为这种写法更易读，创建的对象更少，而且速度应该会更快。

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

- placeybordeaux

---

这确实给了我不同的结果。也就是说，对我来说知道x[i+j]==y[i+j+1]在3个不同的索引处得到满足非常重要，不一定要重叠。如果我正在寻找一个长度为3的序列，那么是否存在一个长度为2的序列并不重要。 - user688635

filter(lambda x: x[2] > n,results) 或者在将结果添加到列表之前进行检查。 - placeybordeaux