在Python中统计字符串中的重复字符

Question

我想统计一个字符串中每个字符出现的次数。除了逐个比较字符串中的字符从A到Z并增加计数器，还有其他特别的方法吗？

更新（参考Anthony的回答）：到目前为止你建议的每个字符我都得写26次。有没有更简单的方法？

Answer 1

性能大比拼

count_chars(s)

=> 2.960809530000006

^{想要快速了解的可以直接看最后的 TL;DR 图表}

因为我“没什么更好的事情做”（其实是工作太多了），我决定来做个性能对比。我收集了一些比较合理或有趣的答案，并在CPython 3.5.1上做了一些简单的 timeit 测试。我只用了一种字符串作为测试输入，这在我的情况下是个典型的例子：

>>> s = 'ZDXMZKMXFDKXZFKZ'
>>> len(s)
16

请注意，结果可能会因为不同的输入而有所不同，比如字符串的长度、不同字符的数量，或者每个字符出现的平均次数。

---

别重复造轮子

Python已经为我们简化了很多。collections.Counter 类正好做了我们想要的事情，而且功能还很多。它的用法是这里提到的所有方法中最简单的。

摘自 @oefe，不错的发现

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Counter 功能强大，所以它的执行时间也相对较长。

字典，懂了吗？

我们试试用简单的 dict 来实现。首先，使用字典推导来声明性地做。

这是我自己想出来的……

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

这个方法会从头到尾遍历 s，并统计每个字符在 s 中出现的次数。由于 s 中有重复字符，上面的方式会多次查找同一个字符。结果自然是一样的。所以我们只需对每个字符统计一次出现次数。

这是我自己想出来的，@IrshadBhat 也是这样做的

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

这样更好。但我们仍然需要遍历字符串来统计出现次数。每个不同的字符都要查找一次。这意味着我们要多次读取字符串。我们可以做得更好！但为此，我们得放下我们的声明式思维，转向命令式思维。

特殊代码

也就是 得抓住它们！

灵感来自 @anthony

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

好吧，试试看。如果你深入研究Python的源代码（我不能确定，因为我从未真正做过），你会发现当你使用 except ExceptionType 时，Python需要检查抛出的异常是否真的是 ExceptionType 或其他类型。为了好玩，我们来看看如果省略这个检查，捕获所有异常需要多长时间。

由 @anthony 制作

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

这样确实节省了一些时间，所以可能有人会想用这个作为某种优化。
别这么做！ 其实可以试试。现在就去做：

_{插曲 1}

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

你看到了吗？它捕获了 KeyboardInterrupt，还有其他一些异常。实际上，它捕获了所有的异常，包括你可能从未听说过的，比如 SystemExit。

_{插曲 2}

import sys
try:
  print("Goodbye. I'm going to die soon.")
  sys.exit()
except:
  print('BACK FROM THE DEAD!!!')

现在回到统计字母、数字和其他字符上。

追赶

异常并不是解决问题的好方法。你得费劲去追赶它们，当你终于追上时，它们又会让你失望，仿佛是你的错。幸运的是，一些勇敢的人为我们铺平了道路，让我们在这个小练习中可以不使用异常。

dict 类有一个很好的方法——get——它允许我们从字典中获取一个项目，就像 d[k] 一样。只不过当键 k 不在字典中时，它可以返回一个默认值。我们就用这个方法，而不是去处理异常。

感谢 @Usman

>>> timeit('''
... d = {}
... for c in s:
...   d[c] = d.get(c, 0) + 1
... ''', globals=locals())
3.2133633289995487

几乎和基于集合的字典推导一样快。在更大的输入下，这个方法可能会更快。

用对工具

对于至少有点了解Python的程序员来说，首先想到的可能是 defaultdict。它的功能和上面的版本差不多，只不过你给它的是一个值的 工厂。这可能会带来一些开销，因为每个缺失的键都需要单独“构造”一个值。我们来看看它的表现。

希望 @AlexMartelli 不会因为 from collections import defaultdict 而对我不满

>>> timeit('''
... dd = defaultdict(int)
... for c in s:
...   dd[c] += 1
... ''', globals=locals())
3.3430528169992613

表现还不错。我认为执行时间的增加是为了提高可读性而付出的小代价。不过，我们也要关注性能，不能止步于此。让我们进一步预填充字典为零。这样我们就不需要每次都检查项目是否已经存在。

向 @sqram 致敬

>>> timeit('''
... d = dict.fromkeys(s, 0)
... for c in s:
...   d[c] += 1
... ''', globals=locals())
2.6081761489986093

很好。速度是 Counter 的三倍多，但仍然足够简单。就我个人而言，如果你不想后续添加新字符，这是我最喜欢的方法。即使你想添加，也可以做到，只是比其他版本稍微不方便一些：

d.update({ c: 0 for c in set(other_string) - d.keys() })

实用性胜于纯粹性 (除非它真的不实用)

现在我们来看看另一种计数器。@IdanK 提出了一个有趣的想法。我们可以用 list 来代替哈希表（也就是字典 dict），这样可以避免哈希冲突的风险和随之而来的开销。我们还可以避免哈希键的开销，以及额外的未占用表空间。字符的ASCII值将作为索引，它们的计数将作为值。正如 @IdanK 指出的，这个列表可以让我们以常数时间访问字符的计数。我们只需使用内置函数 ord 将每个字符从 str 转换为 int。这将为我们提供一个列表的索引，然后我们可以用它来增加字符的计数。我们的做法是：初始化列表为零，完成工作后再将列表转换为 dict。这个 dict 只会包含那些计数不为零的字符，以便与其他版本兼容。

顺便提一下，这种技术在一种称为计数排序的线性时间排序算法中使用。它非常高效，但被排序的值的范围有限，因为每个值都必须有自己的计数器。要对32位整数序列进行排序，需要4.3亿个计数器。

>>> timeit('''
... counts = [0 for _ in range(256)]
... for c in s:
...   counts[ord(c)] += 1
... d = {chr(i): count for i,count in enumerate(counts) if count != 0}
... ''', globals=locals())
25.438595562001865

哎呀！这可不太好！让我们看看如果省略构建字典的步骤需要多长时间。

>>> timeit('''
... counts = [0 for _ in range(256)]
... for c in s:
...   counts[ord(c)] += 1
... ''', globals=locals())
10.564866792999965

仍然不太好。但是，[0 for _ in range(256)] 是什么？我们不能更简单地写吗？比如 [0] * 256？这样更简洁。但这样会更快吗？

>>> timeit('''
... counts = [0] * 256
... for c in s:
...   counts[ord(c)] += 1
... ''', globals=locals())
3.290163638001104

显著快了。现在我们把字典放回去。

>>> timeit('''
... counts = [0] * 256
... for c in s:
...   counts[ord(c)] += 1
... d = {chr(i): count for i,count in enumerate(counts) if count != 0}
... ''', globals=locals())
18.000623562998953

几乎慢了六倍。为什么会这么慢？因为当我们 enumerate(counts) 时，我们必须检查256个计数中的每一个，看看它是否为零。但我们已经知道哪些计数是零，哪些不是。

>>> timeit('''
... counts = [0] * 256
... for c in s:
...   counts[ord(c)] += 1
... d = {c: counts[ord(c)] for c in set(s)}
... ''', globals=locals())
5.826531438000529

对于这么小的输入，可能不会有太大改善。而且它仅适用于8位的EASCII字符。哦，天哪！

最终赢家是……

>>> timeit('''
... d = {}
... for c in s:
...   if c in d:
...     d[c] += 1
...   else:
...     d[c] = 1
... ''', globals=locals())
1.8509794599995075

没错。即使你每次都得检查 c 是否在 d 中，对于这个输入来说，这也是最快的方法。没有预填充 d 会让它更快（再次强调，对于 这个输入）。它比 Counter 或 defaultdict 更冗长，但效率更高。

---

就这些了，朋友们

这个小练习教会我们一个道理：在优化时，始终测量性能，最好使用你预期的输入。优化常见情况。不要因为某个方法的渐进复杂度较低就认为它实际上更高效。最后但同样重要的是，要考虑可读性。尽量在“计算机友好”和“人类友好”之间找到一个折衷。

---

更新

我收到了 @MartijnPieters 的消息，Python 3中有一个函数 collections._count_elements。

Help on built-in function _count_elements in module _collections:

_count_elements(...)
    _count_elements(mapping, iterable) -> None

    Count elements in the iterable, updating the mappping

这个函数是用C实现的，所以应该更快，但这种额外的性能是有代价的。代价是与Python 2以及未来版本的不兼容，因为我们使用的是一个私有函数。

根据 文档：

[...] 以一个下划线开头的名称（例如 _spam）应该被视为API的非公开部分（无论是函数、方法还是数据成员）。它应该被视为实现细节，可能会在没有通知的情况下发生变化。

话虽如此，如果你仍然想每次节省620纳秒：

>>> timeit('''
... d = {}
... _count_elements(d, s)
... ''', globals=locals())
1.229239897998923

---

更新 2： 大字符串

我觉得重新在一些较大的输入上运行测试可能是个好主意，因为16个字符的字符串实在太小了，所有可能的解决方案都比较快(1000次迭代在30毫秒以内)。

我决定使用 莎士比亚全集 作为测试语料库，这变成了一个相当大的挑战（因为它超过5MiB）。我只用了前100,000个字符，并且不得不将迭代次数从1,000,000限制到1,000。

import urllib.request
url = 'https://ocw.mit.edu/ans7870/6/6.006/s08/lecturenotes/files/t8.shakespeare.txt'
s = urllib.request.urlopen(url).read(100_000)

collections.Counter 在小输入上真的很慢，但情况发生了变化

Counter(s)

=> 7.63926783799991

简单的 Θ(n²) 时间字典推导根本行不通

{c: s.count(c) for c in s}

=> 15347.603935000052s (tested on 10 iterations; adjusted for 1000)

聪明的 Θ(n) 时间字典推导运行良好

{c: s.count(c) for c in set(s)}

=> 8.882608592999986

异常处理笨重且慢

d = {}
for c in s:
  try:
    d[c] += 1
  except KeyError:
    d[c] = 1

=> 21.26615508399982

省略异常类型检查并没有节省时间（因为异常只会抛出几次）

d = {}
for c in s:
  try:
    d[c] += 1
  except:
    d[c] = 1

=> 21.943328911999743

dict.get 看起来不错，但运行缓慢

d = {}
for c in s:
  d[c] = d.get(c, 0) + 1

=> 28.530086210000007

collections.defaultdict 也不快

dd = defaultdict(int)
for c in s:
  dd[c] += 1

=> 19.43012963199999

dict.fromkeys 需要读取（非常长的）字符串两次

d = dict.fromkeys(s, 0)
for c in s:
  d[c] += 1

=> 22.70960557699999

用 list 代替 dict 既不优雅也不快

counts = [0 for _ in range(256)]
for c in s:
  counts[ord(c)] += 1

d = {chr(i): count for i,count in enumerate(counts) if count != 0}

=> 26.535474792000002

省略最终转换为 dict 并没有帮助

counts = [0 for _ in range(256)]
for c in s:
  counts[ord(c)] += 1

=> 26.27811567400005

无论你如何构建 list，都不会成为瓶颈

counts = [0] * 256
for c in s:
  counts[ord(c)] += 1

=> 25.863524940000048

counts = [0] * 256
for c in s:
  counts[ord(c)] += 1

d = {chr(i): count for i,count in enumerate(counts) if count != 0}

=> 26.416733378000004

如果你以“聪明”的方式将 list 转换为 dict，速度会更慢（因为你要遍历字符串两次）

counts = [0] * 256
for c in s:
  counts[ord(c)] += 1

d = {c: counts[ord(c)] for c in set(s)}

=> 29.492915620000076

dict.__contains__ 变体对于小字符串可能很快，但对于大字符串就不那么快了

d = {}
for c in s:
  if c in d:
    d[c] += 1
  else:
    d[c] = 1

=> 23.773295123000025

collections._count_elements 的速度和 collections.Counter 差不多（后者内部使用 _count_elements）

d = {}
_count_elements(d, s)

=> 7.5814381919999505

最终结论： 使用 collections.Counter，除非你不能或不想这样做 :)

---

附录： NumPy

numpy 包提供了一个方法 numpy.unique，几乎可以完成我们想要的事情。

这个方法的工作方式与上述所有方法非常不同：

• 它首先使用快速排序对输入的副本进行排序，在最坏情况下是O(n²)的时间操作，尽管平均情况下是O(n log n)，最好情况下是O(n)。

• 然后它创建一个“掩码”数组，在相同值的运行开始的索引处标记 True，即在值与前一个值不同的索引处。重复的值在掩码中产生 False。例如：[5,5,5,8,9,9] 产生的掩码是 [True, False, False, True, True, False]。

• 然后使用这个掩码从排序后的输入中提取唯一值——在下面的代码中是 unique_chars。在我们的例子中，它们将是 [5, 8, 9]。

• 掩码中 True 值的位置被提取到一个数组中，并在这个数组的末尾附加输入的长度。对于上面的例子，这个数组将是 [0, 3, 4, 6]。

• 对于这个数组，计算其元素之间的差值，例如 [3, 1, 2]。这些就是排序数组中元素的计数——在下面的代码中是 char_counts。

• 最后，我们通过将 unique_chars 和 char_counts 组合创建一个字典：{5: 3, 8: 1, 9: 2}。

import numpy as np

def count_chars(s):
  # The following statement needs to be changed for different input types.
  # Our input `s` is actually of type `bytes`, so we use `np.frombuffer`.
  # For inputs of type `str`, change `np.frombuffer` to `np.fromstring`
  #  or transform the input into a `bytes` instance.
  arr = np.frombuffer(s, dtype=np.uint8)

  unique_chars, char_counts = np.unique(arr, return_counts=True)

  return dict(zip(unique_chars, char_counts))

---

对于测试输入（莎士比亚全集的前100,000个字符），这个方法的表现优于这里测试的任何其他方法。但请注意，在不同的输入上，这种方法的性能可能会比其他方法差。输入的预排序性和每个元素的重复次数是影响性能的重要因素。

如果你考虑使用这个方法，因为它比 collections.Counter 快两倍多，请考虑以下几点：

• collections.Counter 的时间复杂度是线性的。numpy.unique 在最好的情况下也是线性的，最坏情况下是平方级别。

• 速度提升并不显著——在长度为100,000的输入上，你每次节省约3.5毫秒。

• 使用 numpy.unique 显然需要 numpy。

考虑到这些，使用 Counter 是合理的，除非你需要非常快。在这种情况下，你最好知道自己在做什么，否则使用 numpy 可能会比不使用它更慢。

---

附录 2： 一个有点用的图

我在 莎士比亚全集 的前缀上运行了上述13种不同的方法，并制作了一个交互式图表。请注意，在图表中，前缀和持续时间都以对数尺度显示（使用的前缀长度呈指数增长）。点击图例中的项目可以在图表中显示/隐藏它们。

^{点击打开！}

Answer 2

import collections

d = collections.defaultdict(int)
for c in thestring:
    d[c] += 1

一个 collections.defaultdict 就像一个普通的 dict（其实是它的子类），但它有个特别的地方：当你想查找一个条目但没有找到时，它不会直接告诉你没有，而是会自动创建这个条目，并通过你提供的一个不带参数的函数来插入这个条目。最常用的有 defaultdict(int)，用于计数（或者说是用来创建一个多重集合，也就是袋子数据结构），还有 defaultdict(list)，它让你不再需要使用 .setdefault(akey, []).append(avalue) 这种麻烦的写法。

所以，一旦你创建了这个 d，它就像一个字典一样，把每个字符映射到它出现的次数，你当然可以用任何你喜欢的方式来输出它。例如，可以先输出出现频率最高的字符：

for c in sorted(d, key=d.get, reverse=True):
  print '%s %6d' % (c, d[c])

Answer 3

我最开始的想法是这样做：

chars = "abcdefghijklmnopqrstuvwxyz"
check_string = "i am checking this string to see how many times each character appears"

for char in chars:
  count = check_string.count(char)
  if count > 1:
    print char, count

不过，这其实不是个好主意！这样做会让你扫描字符串26次，也就是说你可能会比其他一些答案多做26倍的工作。你真的应该这样做：

count = {}
for s in check_string:
  if s in count:
    count[s] += 1
  else:
    count[s] = 1

for key in count:
  if count[key] > 1:
    print key, count[key]

这样可以确保你只扫描一次字符串，而不是26次。

另外，Alex的回答非常棒——我之前对collections模块不太熟悉。以后我会用到它。他的回答比我的更简洁，技术上也更优秀。我建议你使用他的代码，而不是我的。