在列表中统计字符串或浮点数的频率

Question

我有一个列表。它很大，有超过1百万条目。我想计算其中每个字符串的频率。它将数字作为字符串存储从1到1000。我尝试了以下方法，但它运行了几个小时：

d = {b:a.count(b) for b in a}
n, m = d.keys(), d.values()
print n, m

- Abhinav Kumar

---

问题在于，要构建那个dict，您需要执行n次（列表a的长度）成本为n的操作（a.count(b)必须遍历所有a以搜索b）。这意味着构建它需要与n^2成比例的时间。如果您有100万条目的列表，则需要执行约(10^6)^2 = 10^12次操作。即使单个操作是机器指令，构建它也需要大约10^3秒的时间。实际上，每个操作可能需要一些（或至少十几个）机器指令，因此您需要等待数小时/天。 - Bakuriu

Answer 1

请使用collections.Counter替代：

from collections import Counter
d = Counter(a)

n, m = d.keys(), d.values()
print n, m

- David Robinson

Answer 2

在这种情况下，使用字典会更加容易。 向字典中插入内容非常快速，从字典中检索数据同样也很快。

以下是一个完全按照此方法操作的示例程序：

import datetime
import random
def create_string(choice, size):
    str = ''
    for i in range(size):
         str = str + random.choice(choice)
    return str

def count_all(strings):
    count_dict = {}
    for i in strings:
        if i not in count_dict:
            count_dict[i] = 1
        else:
            count_dict[i] = count_dict[i] + 1
    return count_dict

if __name__ == '__main__':
    all_strings = []
    for i in range(1000000):
        all_strings.append(create_string(['a','b','c'], 4))

    start = datetime.datetime.now()
    c_dict = count_all(all_strings)
    end = datetime.datetime.now()
    print 'Took:', end - start
    print 'The count of aacc is ', c_dict['aacc']

它的表现如何？

./speed_test.py
Took: 0:00:00.219815
The count of aacc is  12317

还不错，对吧？ 作为解决Ant提到的问题的另一种选择，在计数时要消除重复项。我们可以使用一个集合：

d = {b:a.count(b) for b in set(a)}

根据我的测试，这种方法不如使用字典的方法快，但是少于一秒，已经足够好了。

- Avatar33

---

不要使用datetime来分析性能。使用timeit模块（可以使用iPython），因为它会正确地计算平均时间。如果您想进行单次基准测试，请使用time.perf_counter，如果您正在使用python3.3+，因为这是它的目的。 - Bakuriu

好的，谢谢。我最初确实使用了timeit，但由于它的设置和代码是以字符串形式传递的，我认为这会使示例变得不必要地复杂。 - Avatar33

Answer 3

因为你对每个字符串运行了a.count，所以速度很慢！

l = ['a', 'b', 'a']

然后在'a'上调用str.count两次，在'b'上调用1次。

当然，在'a'上第二次的结果将覆盖字典中的前一个，因此您甚至不会注意到它。

使用默认字典代替。

from collections import defaultdict
d = defaultdict(int)
for obj in your_list:
    d[obj] += 1

或者，再次来自collections模块，Counter http://docs.python.org/2/library/collections.html#counter-objects。

- Ant