Подсчет скользящим окном

Question

Предположим, что у меня есть data -- итератор, для которого я хочу посчитать k последовательных элементов итерируемого объекта как (elem_1, elem_2, ..., elem_k) и записать в словарь для каждого такого "окна" количество раз, которое оно встретилось, каким образом можно эффективнее всего это сделать? За O(n).

Пример: "abcabc", k = 3, получаем:
(a,b,c), (b,c,a), (c,a,b), (a,b,c) в итоге должен выйти такой словарь:
(a,b,c) : 2, (b,c,a) : 1, (c,a,b) : 1.

Answer 1

не знаю то что надо или нет?

st = "abcabc"
k = 3
def funk(st, k):
    myD = dict()
    for i in range(len(st) - k + 1):
        myD[tuple(st[i:i+3])] = myD.get(tuple(st[i:i+3]), 0) + 1 # получаем значание из словаря, если ключа нет, то 0 + 1 = 1, если есть, то + 1
    return myD

print(funk(st, k))

Answer 2

Как вариант:

a, b, c = 1, 2, 3
data = (a,b,c), (b,c,a), (c,a,b), (a,b,c)
_dict = {}

for i in data:
    _dict[i] = _dict.get(i, 0)
    _dict[i] += 1
    
print(_dict)
# {(1, 2, 3): 2, (2, 3, 1): 1, (3, 1, 2): 1}

Answer 3

s = 'abcabc'
stat = dict()
s = tuple(list(s))

k = 3
for p in (s[i:i+k] for i in range(0, len(s)-k+1)):
    stat[p] = stat.get(p, 0) + 1

Реализация для итератора, без предварительного вычитывания в память list(data)(тоже O(kN)).

def impl_it(data, k):
  stat = dict()
  win = []
  for _ in range(k):
    win.append(next(data))

  key = tuple(win)
  stat[key] = stat.get(key, 0) + 1
  for el in data:
    win = win[1:]
    win.append(el)

    key = tuple(win) # O(k)
    stat[key] = stat.get(key, 0) + 1
  return stat

Из-за необходимости строить ключ/считать хеш, O(k) внутри цикла не устранима, так что замена окна на какой-нибудь deque для оптимизации win[1:] ситуации не улучшит.

Answer 4

Вот так вот:

import collections

a = "abcabc"
k = 3

print(dict(collections.Counter(zip(*[a[i:] for i in range(k)]))))

Вариант без slicing:

import collections, itertools

a = "abcabc"
k = 3

print(dict(collections.Counter(zip(*[itertools.islice(a, i, len(a)) for i in range(k)]))))

БЛОГ НА HUSL

Подсчет скользящим окном

Ответы (4 шт):