如何高效地计算字符串中字符频率的前缀和？

Question

假设我有一个字符串

s = 'AAABBBCAB'

如何高效地计算字符串中每个字符出现次数的前缀和，即：

psum = [{'A': 1}, {'A': 2}, {'A': 3}, {'A': 3, 'B': 1}, {'A': 3, 'B': 2}, {'A': 3, 'B': 3}, {'A': 3, 'B': 3, 'C': 1}, {'A': 4, 'B': 3, 'C': 1}, {'A': 4, 'B': 4, 'C': 1}]

- planetp

---

你最终想要一个字典还是在读取每个字符时想要一个字典列表？ - Vanjith

@Vanjith 我想要一个正在运行的字符频率计数器。 - planetp

Answer 1

你可以使用 itertools.accumulate 和 collections.Counter 在一行代码中完成此操作：

from collections import Counter
from itertools import accumulate

s = 'AAABBBCAB'
psum = list(accumulate(map(Counter, s)))

这会给你一个Counter对象的列表。现在，要在O(1)时间内获取s的任何子字符串的频率，你只需相减计数器，例如：

>>> psum[6] - psum[1]  # get frequencies for s[2:7]
Counter({'B': 3, 'A': 1, 'C': 1})

- Eugene Yarmash

Answer 2

这是一个选项：

from collections import Counter

c = Counter()
s = 'AAABBBCAB'

psum = []
for char in s:
    c.update(char)
    psum.append(dict(c))

# [{'A': 1}, {'A': 2}, {'A': 3}, {'A': 3, 'B': 1}, {'A': 3, 'B': 2}, 
#  {'A': 3, 'B': 3}, {'A': 3, 'B': 3, 'C': 1}, {'A': 4, 'B': 3, 'C': 1},
#  {'A': 4, 'B': 4, 'C': 1}]

我使用collections.Counter来保持“累加和”，并将（结果的副本）添加到列表psum中。这样，我只需要对字符串s进行一次迭代。

如果你喜欢在结果中使用collections.Counter对象，你可以将最后一行改为：

psum.append(c.copy())

为了获得{{某个目标}},

[Counter({'A': 1}), Counter({'A': 2}), ...
 Counter({'A': 4, 'B': 4, 'C': 1})]

使用这个方法也可以达到同样的效果（accumulate的使用最初是在Eugene Yarmash的答案中提出的；我只是避免使用map而选择了生成器表达式）：

from itertools import accumulate
from collections import Counter

s = "AAABBBCAB"
psum = list(accumulate(Counter(char) for char in s))

---

为了完整起见（因为这里还没有“纯dict”的答案），如果您不想使用Counter或defaultdict，您也可以使用以下内容：

c = {}
s = 'AAABBBCAB'

psum = []
for char in s:
    c[char] = c.get(char, 0) + 1
    psum.append(c.copy())

尽管defaultdict通常比dict.get(key, default)更高效。

- hiro protagonist

---

我们甚至不需要 Counter，一个简单的 defaultdict 就可以了 @hiro-protagonist，请查看我下面的答案！ - Devesh Kumar Singh

你为什么说defaultdict比Counter更“简单”？在哪方面更简单？ - hiro protagonist

@DeveshKumarSingh 他们都是dict的子类；计数器的数据结构并不比dict更复杂。我错了吗？ - hiro protagonist

@DeveshKumarSingh，这些考虑是不恰当的。我已经指出了时间性能差异，但是OP应该自己做出决定。 - RomanPerekhrest

你的回答比这个回答晚，它与此答案具有完全相同的结构，但类型稍有不同，复杂度相同但输出更详细。你不应该在这里广告它。 - Eric Duminil

Answer 3

您实际上甚至不需要一个计数器，只需要一个defaultdict就足够了！

from collections import defaultdict

c = defaultdict(int)
s = 'AAABBBCAB'

psum = []

#iterate through the character
for char in s:
    #Update count for each character
    c[char] +=1
    #Add the updated dictionary to the output list
    psum.append(dict(c))

print(psum)

输出结果看起来像这样：

[{'A': 1}, {'A': 2}, {'A': 3}, {'A': 3, 'B': 1}, 
{'A': 3, 'B': 2}, {'A': 3, 'B': 3}, 
{'A': 3, 'B': 3, 'C': 1}, {'A': 4, 'B': 3, 'C': 1}, 
{'A': 4, 'B': 4, 'C': 1}]

- Devesh Kumar Singh

Answer 4

最简单的方法是使用collections模块中的Counter对象。

from collections import Counter

s = 'AAABBBCAB'

[ dict(Counter(s[:i]) for i in range(1,len(s))]

产生：

[{'A': 1},  {'A': 2},  {'A': 3},  {'A': 3, 'B': 1},  {'A': 3, 'B': 2},
{'A': 3, 'B': 3},  {'A': 3, 'B': 3, 'C': 1},  {'A': 4, 'B': 3, 'C': 1}]

- Christian Sloper

---

仅作为说明，Counter 是 dict 的一个子类，因此用普通的 dict 替换 Counter 的理由很少。 - chepner

我同意，但更符合用户指定的输出。我会自己保留计数器对象，因为它们除了作为字典外还有有用的功能。 - Christian Sloper

这是一条优雅的1行代码，因此加1分，但它是二次的而不是线性的。我怀疑 hiro protagonist 提出的类似解决方案更有效。 - John Coleman

Answer 5

在Python 3.8中，您可以使用列表推导式与赋值表达式（也称为“海象运算符”）：

>>> from collections import Counter
>>> s = 'AAABBBCAB'
>>> c = Counter()
>>> [c := c + Counter(x) for x in s]
[Counter({'A': 1}), Counter({'A': 2}), Counter({'A': 3}), Counter({'A': 3, 'B': 1}), Counter({'A': 3, 'B': 2}), Counter({'A': 3, 'B': 3}), Counter({'A': 3, 'B': 3, 'C': 1}), Counter({'A': 4, 'B': 3, 'C': 1}), Counter({'A': 4, 'B': 4, 'C': 1})]

- Eugene Yarmash