Получить начальные и конечные индексы длинной полосы повторений в списке

Question

Я собираю что-то, где я хочу показать самую длинную полосу побед команды и дату начала и окончания этой конкретной полосы. Так, например, если у меня есть следующие два списка:

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.

Кроме того, только для полноты картины, оптимизированная версия Colonel Beauvel's answer для минимизации выполнения байт-код (медленно в CPython) в пользу более исполнения на уровне C (быстрый в CPython):

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] 

Для записи, спасибо к различным битам накладных расходов, связанных с попытками избежать создания list/tuple s, содержащих всю полосу в виде группы, когда нам нужно только начало и конец, мои два альтернативных решения работают медленнее в основном по всем данным реального мира; тестовый пример, включающий рандомизированные длины штрихов, всего 450 тыс. записей, на ipython3 (Python 3.5 x86-64 для Linux), на моей машине потребовалось около 35 мс для обработки с оптимизированной версией ответа полковника, ~ 50 мс с моим сначала, tee, используя решение, и ~ 77 мс с моим вторым, deque с использованием решения.