リスト内の反復配列のインデックスを効率的に見つける方法はありますか？

Question

私はPythonで大きな数字のリストを持っています。同じ数字がn回以上繰り返されるリストのセクションを見つける関数を書いてみたいと思います。たとえば、nが3の場合、関数は次の例の結果を返します。

例= [1,2,1,1,1,1,2,3]に適用すると例[2：6]はすべて同じ値を含むシーケンスであるため、[（2,6）]を返す必要があります。

例= [0,0,0,7,3,2,2,2,2,1]に適用すると、関数は[（0,3）、（5,9）]を返さなければなりません[0：3]とexample [5：9]には同じ値の繰り返しシーケンスが含まれています。

example = [1,2,1,2,1,2,1,2,1,2]に適用すると、3つ以上の要素のシーケンスが存在しないため、関数は[]を返す必要があります。同じ番号。

私は、私が望むものを得るためにループの束を書くことができると知っていますが、それは非効率的であり、私が望むものを得るためのより簡単なオプションがあるかどうか疑問に思っていました。

Answer 1

使用itertools.groupbyとenumerate：

>>> from itertools import groupby 
>>> n = 3 
>>> x = [1,2,1,1,1,1,2,3] 
>>> grouped = (list(g) for _,g in groupby(enumerate(x), lambda t:t[1])) 
>>> [(g[0][0], g[-1][0] + 1) for g in grouped if len(g) >= n] 
[(2, 6)] 
>>> x = [0,0,0,7,3,2,2,2,2,1] 
>>> grouped = (list(g) for _,g in groupby(enumerate(x), lambda t:t[1])) 
>>> [(g[0][0], g[-1][0] + 1) for g in grouped if len(g) >= n] 
[(0, 3), (5, 9)] 

GROUPBYを理解するために：ちょうど各反復は、新しいレイジー反復可能とともに、グループにイテラブルの要素を使用したキーの値を返すことを実現グループ全体を反復処理します。

>>> list(groupby(enumerate(x), lambda t:t[1])) 
[(0, <itertools._grouper object at 0x7fc90a707bd0>), (7, <itertools._grouper object at 0x7fc90a707ad0>), (3, <itertools._grouper object at 0x7fc90a707950>), (2, <itertools._grouper object at 0x7fc90a707c10>), (1, <itertools._grouper object at 0x7fc90a707c50>)] 

Answer 2

あなたは現在のアルゴリズムに従って、単一のループでこれを行うことができます。

def find_pairs (array, n): 
    result_pairs = [] 
    prev = idx = 0 
    count = 1 
    for i in range (0, len(array)): 
     if(i > 0): 
      if(array[i] == prev): 
       count += 1 
      else: 
       if(count >= n): 
        result_pairs.append((idx, i)) 
       else: 
        prev = array[i] 
        idx = i 
       count = 1 
     else: 
      prev = array[i] 
      idx = i 
    return result_pairs 

をそして、あなたはこのように関数を呼び出す：find_pairs(list, n)。これは複雑さO（len（array））があるので、このタスクを実行する最も効率的な方法です。私は理解するのはかなり簡単だと思いますが、疑問がある場合はただ聞いてください。

Answer 3

これを使用できます。あなたの質問はnの役割に関してあいまいであることに注意してください。ここでは、一連のnの値が一致していると仮定します。それは、少なくとものn + 1値を持つべきである場合は、>によって>=を置き換える：

def monotoneRanges(a, n): 
    idx = [i for i, v in enumerate(a) if not i or a[i-1] != v] + [len(a)] 
    return [r for r in zip(idx, idx[1:]) if r[1] >= r[0]+n] 

# example call 
res = monotoneRanges([0,0,0,7,3,2,2,2,2,1], 3) 

print(res) 

出力：

[(0, 3), (5, 9)]