使用字典在Python中计算字频率效率

Question

我的任务是找到列表中每个单词的频率。有两种方法。

方法1

def f(words):
    wdict = {}
    for word in words:
        if word not in wdict:
            wdict[word] = 0
        wdict[word] += 1
    return wdict

方法2

def g(words):
    wdict = {}
    for word in words:
        try:
            wdict[word] += 1
        except KeyError:
            wdict[word] = 1

为什么方法2有效？在这两种情况下，哈希函数调用的数量是否与此http://blackecho.github.io/blog/programming/2016/03/23/python-underlying-data-structures.html相反？

Answer 1

这取决于输入。如果平均而言大多数单词已经在dict中，那么你就不会有很多例外。如果大多数单词是唯一的，则异常的开销将使第二种方法变慢。

Answer 2

让我们模拟一些案例。

示例：“一只鸟飞”

words = ["A", "bird", "is", flying"]

在你的第一个方法中：对于每个单词，它将在字典中搜索3次，这样它将访问总共3 * len(words)或3 * 4 = 12

在第二种方法中，如果没有找到它将只搜索2次;否则1次：所以2 * 4 = 8

理论上两者都具有相同的时间复杂度。

更新：

感谢Thierry Lathuille指出。实际上，方法1应该比方法2更有效.Python字典使用散列映射，因此访问密钥复杂度将是O（n），但在平均情况下它是O（1）。和cpython实现非常有效。另一方面，try / catch异常处理很慢。

你可以在方法1中使用defaultdict来获得更干净的代码。

Answer 3

有两个主要区别：

• 方法1将对每个单词执行in操作，而方法2将尽可能直接更新。
• 每当Method1插入一个新单词时，计数稍后会更新。 Method2开始计为1。

它最终取决于输入，但如果有足够的重复次数，则操作将会减少。

例： 让我们通过这里的代码来获得一般的想法（而不是实际的操作）。

['a', 'a']

方法1 1 - 'a'不在wdict中 - 是的 2 - 分配'a' 3 - 更新'a' 4 - 'a'不在词典中 - 错误 5 - 更新'a'

方法2 1 - 访问'a' 2 - 错误 3 - 直接将“a”分配给1 4 - 更新'a'（第二个'a'）

虽然这些步骤并不完全是执行时所执行的操作量，但它们表明Method2更精简并且经历了更少的“步骤”。

Answer 4

这个答案有几种方法。您可以使用循环并仍然获得预期的答案。我专注于两种方法：

列表理解

wordstring = 'it was the best of times it was the worst of times '
wordstring += 'it was the age of wisdom it was the age of foolishness'
wordlist = wordstring.split()
# Count each word
wordfreq = [wordlist.count(w) for w in wordlist] # a list comprehension
# Convert to set to remove repetitions
frequencies=set(zip(wordlist, wordfreq))
print(frequencies)

输出：

{('of', 4), ('best', 1), ('the', 4), ('worst', 1), ('age', 2), ('wisdom', 1), ('it', 4), ('was', 4), ('times', 2), ('foolishness', 1)}

方法二：标准库

import collections
wordstring = 'it was the best of times it was the worst of times '
wordstring += 'it was the age of wisdom it was the age of foolishness'
wordlist = wordstring.split()
# Count frequency
freq=collections.Counter(wordlist)
print(freq)

输出：

Counter({'it': 4, 'was': 4, 'the': 4, 'of': 4, 'times': 2, 'age': 2, 'best': 1, 'worst': 1, 'wisdom': 1, 'foolishness': 1})

选择的方法取决于您正在使用的文本的大小。上述方法适用于小文本大小。