リスト内の最も長いストリークの開始と終了のインデックスを取得

Question

私はチームの勝利の最長のストリークとこの特定のストリークの開始日と終了日を示すために何かをまとめています。私は、次の2つのリストを持っているのであれば、たとえば、：

streak = ["W", "W", "W", "L","W", "W", "W", "W", "W", "L"] 
dates = ["2016-06-15", "2016-06-14", "2016-06-13", "2016-06-10", "2016-06-09", "2016-06-08", "2016-06-05", "2016-06-03", "2016-06-02", "2016-06-02"] 

私は私のような何かを行うことができ、最長連勝取得したい場合は、：

from itertools import groupby 
longest = sorted([list(y) for x, y in groupby(streak)], key = len)[-1] 
print longest 
["W", "W", "W", "W", "W"] 

を今私のアイデアはなら、私が知っているようでした（これは、この場合にはので、何とかこの最長ストリークの開始と終了インデックスを取得するために）良く行うことができます。

start, end = get_indices(streak, longest) # 8, 4 
print "The longest streak of {}{} was from {} to {}.".format(len(longest), longest[0], dates[start], dates[end]) 
"The longest streak of 5W was from 2016-06-02 to 2016-06-09. 

はどうすればこれを行うことができますか？あるいは、これを行うより良い方法があります。例えば、リストを一緒に圧縮して、それを使って何かするのですか？

Answer 1

アカウントにコードを取ると、あなたはまだitertoolsで先に行くと、負け犬takewhileを使用することができます。一時（ただし、ノートを減らす

from itertools import takewhile, groupby 
import itertools 

L = [list(y) for x, y in groupby(streak)] 
l = sorted(L, key=len)[-1] 

ix = len(list(itertools.chain.from_iterable(takewhile(lambda x: x!=l, L)))) 

print("the longest streak goes from " + dates[ix+len(l)] + " to " + dates[ix]) 
#the longest streak goes from 2016-06-02 to 2016-06-09 

Answer 2

代替ソリューション、真剣RAM制約または不当に巨大な縞が発生しない限り、生成一時的な代替案よりも一時的なものが速い）。

from itertools import groupby, tee, zip_longest 
from operator import itemgetter, sub 

def longeststreak(streaks, dates): 
    # Create parallel iterators over the first index of each new group 
    s, e = tee(map(next, map(itemgetter(1), groupby(range(len(streaks)), key=streaks.__getitem__)))) 
    # Advance end iterator so we can zip at offset to create start/end index pairs 
    next(e, None) 
    # Find greatest difference between start and end 
    longend, longstart = max(zip_longest(e, s, fillvalue=len(streaks)), key=lambda es: sub(*es)) 
    # return dates for those indices (must subtract one from end since end index is exclusive) 
    return dates[longend-1], dates[longstart] 

それとも別の方法：両方のケースで

from collections import deque 
from itertools import groupby 
from operator import itemgetter, sub 

def longeststreak(streaks, dates): 
    # Generator of grouped indices for each streak 
    streakgroups = map(itemgetter(1), groupby(range(len(streaks)), streaks.__getitem__)) 
    # Get first and last index of each streak without storing intermediate indices 
    streakranges = ((next(iter(deque(g, 1)), start), start) for g in streakgroups for start in (next(g),)) 
    # As before, find greatest difference and return range 
    longend, longstart = max(streakranges, key=lambda es: sub(*es)) 
    # End index is inclusive in this design, so don't subtract 1 
    return dates[longend], dates[longstart] 

、PY2の場合は、インポートする必要があります必要はありません、ちょうど同じ結果を達成するためにイテレータ関連のツールを結合する他の方法を説明しますmapはfuture_builtins、前者はizip_longestです。レコードの

def longeststreak(streaks, dates): 
    # Use map with C-level builtins to reduce bytecode use 
    streakgroups = list(map(list, map(itemgetter(1), groupby(streaks)))) 
    # Use max with key instead of sorted followed by indexing at -1, to turn 
    # O(n log n) work into O(n) work 
    longeststreak = max(streakgroups, key=len) 
    # Replace lambda with C layer built-in comparator 
    ix = len(list(chain.from_iterable(takewhile(longeststreak.__ne__, streakgroups)))) 
    # Added -1 missing in original answer; end index should be exclusive, 
    # so we need to subtract 1; not noticeable on sample data because sample 
    # data had same data at end of longest streak and beginning of next 
    return dates[ix+len(longeststreak)-1], dates[ix] 

、感謝：

また、単に完全を期すため、Colonel Beauvel's answerの最適化されたバージョンは、（高速CPythonの中に）より多くのCレベルの実行の賛成で（遅いCPythonの中）バイトコードの実行を最小限に抑えますlist/tupleをグループとして作成することを避けるために必要なオーバーヘッドのさまざまなビットに、開始と終了のみが必要なときは、私の2つの代替ソリューションは基本的にすべての実世界データに対して遅く実行されます。私のマシン上でipython3（Python 3.5 x86-64 for Linux）にランダムなストリーク長さを含むテストケースがあり、最適化されたColonelの答え、〜50 msで処理するのに約35ミリ秒かかりましたまず、teeの溶液を使用し、〜77msを私の2番目の溶液で使用する。deque溶液を使用する。