主页 / 问题 / 1183241
Accepted
Владислав Харламов
Asked:2020-09-28 01:29:37 +0000 UTC2020-09-28 01:29:37 +0000 UTC

滑动窗口计数

  • 772

假设我有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。

python

4 个回答

  1. Best Answer
    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

    由于需要建key/计算hash，所以循环内部的O(k)在所难免，所以用一些deque替换window来优化win[1:]情况并不会改善。

    • 4

  2. 我不知道需要什么？

    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))
    • 1

  3. 作为一种选择：

    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}
    • 1

  4. 像这样：

    import collections

a = "abcabc"
k = 3

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

    不切片选项：

    import collections, itertools

a = "abcabc"
k = 3

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

相关问题