我正在尝试使用 O(n) 复杂度的算法来查找任何给定文本中每个符号的频率。我的算法看起来像：
s = len(text)
P = 1.0/s
freqs = {}
for char in text:
try:
freqs[char]+=P
except:
freqs[char]=P
但我怀疑这个字典方法是否足够快，因为它取决于字典方法的底层实现。这是最快的方法吗？
更新：如果使用集合和整数，速度不会增加。这是因为该算法已经具有 O(n) 复杂度，因此不可能有本质的加速。
例如，1MB 文本的结果：
without collections:
real 0m0.695s
with collections:
real 0m0.625s
注意：表中的时间不包括加载文件所需的时间。
| approach | american-english, | big.txt, | time w.r.t. defaultdict |
| | time, seconds | time, seconds | |
|----------------+-------------------+---------------+-------------------------|
| Counter | 0.451 | 3.367 | 3.6 |
| setdefault | 0.348 | 2.320 | 2.5 |
| list | 0.277 | 1.822 | 2 |
| try/except | 0.158 | 1.068 | 1.2 |
| defaultdict | 0.141 | 0.925 | 1 |
| numpy | 0.012 | 0.076 | 0.082 |
| S.Mark's ext. | 0.003 | 0.019 | 0.021 |
| ext. in Cython | 0.001 | 0.008 | 0.0086 |
#+TBLFM: $4=$3/@7$3;%.2g
使用的文件：'/usr/share/dict/american-english'和'big.txt'.
比较“Counter”、“setdefault”、“list”、“try/except”、“defaultdict”、“numpy”、“cython”和@S.Mark 解决方案的脚本位于http://gist。 github.com/347000
最快的解决方案是用 Cython 编写的 Python 扩展：
import cython
@cython.locals(
chars=unicode,
i=cython.Py_ssize_t,
L=cython.Py_ssize_t[0x10000])
def countchars_cython(chars):
for i in range(0x10000): # unicode code points > 0xffff are not supported
L[i] = 0
for c in chars:
L[c] += 1
return {unichr(i): L[i] for i in range(0x10000) if L[i]}
* python (dict) : 0.5 seconds
* python (list) : 0.5 (ascii) (0.2 if read whole file in memory)
* perl : 0.5
* python (numpy): 0.07
* c++ : 0.05
* c : 0.008 (ascii)
输入数据：
$ tail /usr/share/dict/american-english
éclat's
élan
élan's
émigré
émigrés
épée
épées
étude
étude's
études
$ du -h /usr/share/dict/american-english
912K /usr/share/dict/american-english
#!/usr/bin/env python3.1
import collections, fileinput, textwrap
chars = (ch for word in fileinput.input() for ch in word.rstrip())
# faster (0.4s) but less flexible: chars = open(filename).read()
print(textwrap.fill(str(collections.Counter(chars)), width=79))
运行：
$ time -p python3.1 count_char.py /usr/share/dict/american-english
计数器（{'e'：87823，'s'：86620，'i'：66548，'a'：62778，'n'：56696，'r'：
56286，'t'：51588，'o'：48425，'l'：39914，'c'：30020，'d'：28068，'u'：25810，
“'”：24511，'g'：22262，'p'：20917，'m'：20747，'h'：18453，'b'：14137，'y'：
12367，'f'：10049，'k'：7800，'v'：7573，'w'：6924，'z'：3088，'x'：2082，'M'：
1686，'C'：1549，'S'：1515，'q'：1447，'B'：1387，'j'：1376，'A'：1345，'P'：
974，“L”：912，“H”：860，“T”：858，“G”：811，“D”：809，“R”：749，“K”：656，“E”：
618，'J'：539，'N'：531，'W'：507，'F'：502，'O'：354，'I'：344，'V'：330，'Z'：
150，“Y”：140，“é”：128，“U”：117，“Q”：63，“X”：42，“è”：29，“ö”：12，“ü”：12，
'ó': 10, 'á': 10, 'ä': 7, 'ê': 6, 'â': 6, 'ñ': 6, 'ç': 4, 'å': 3, 'û ': 3, 'í':
2, 'ô': 2, 'Å': 1})
实数 0.44
用户 0.43
系统 0.01
time -p perl -MData::Dumper -F'' -lanwe'$c{$_}++ for (@F);
END{ $Data::Dumper::Terse = 1; $Data::Dumper::Indent = 0; print Dumper(\%c) }
' /usr/share/dict/american-english
输出：
{'S' => 1515,'K' => 656,'' => 29,'d' => 28068,'Y' => 140,'E' => 618,'y' => 12367,' g' => 22262,'e' => 87823,'' => 2,'J' => 539,'' => 241,'' => 3,'' => 6,'' => 4, '' => 128,'D' => 809,'q' => 1447,'b' => 14137,'z' => 3088,'w' => 6924,'Q' => 63,'' => 10,'M' => 1686,'C' => 1549,'' => 10,'L' => 912,'X' => 42,'P' => 974,'' => 12 ,'\'' => 24511,'' => 6,'a' => 62778,'T' => 858,'N' => 531,'j' => 1376,'Z' => 150, '你' => 25810,'k' =>7800,'t' => 51588,'' => 6,'W' => 507,'v' => 7573,'s' => 86620,'B' => 1387,'H' => 860, 'c' => 30020,'' => 12,'I' => 344,'' => 3,'G' => 811,'U' => 117,'F' => 502,'' = > 2,'r' => 56286,'x' => 2082,'V' => 330,'h' => 18453,'f' => 10049,'' => 1,'i' => 66548 ,'A' => 1345,'O' => 354,'n' => 56696,'m' => 20747,'l' => 39914,'' => 7,'p' => 20917,' R' => 749,'o' => 48425}'c' => 30020,'' => 12,'I' => 344,'' => 3,'G' => 811,'U' => 117,'F' => 502,'' = > 2,'r' => 56286,'x' => 2082,'V' => 330,'h' => 18453,'f' => 10049,'' => 1,'i' => 66548 ,'A' => 1345,'O' => 354,'n' => 56696,'m' => 20747,'l' => 39914,'' => 7,'p' => 20917,' R' => 749,'o' => 48425}'c' => 30020,'' => 12,'I' => 344,'' => 3,'G' => 811,'U' => 117,'F' => 502,'' = > 2,'r' => 56286,'x' => 2082,'V' => 330,'h' => 18453,'f' => 10049,'' => 1,'i' => 66548 ,'A' => 1345,'O' => 354,'n' => 56696,'m' => 20747,'l' => 39914,'' => 7,'p' => 20917,' R' => 749,'o' => 48425}66548,'A' => 1345,'O' => 354,'n' => 56696,'m' => 20747,'l' => 39914,'' => 7,'p' => 20917, 'R' => 749,'o' => 48425}66548,'A' => 1345,'O' => 354,'n' => 56696,'m' => 20747,'l' => 39914,'' => 7,'p' => 20917, 'R' => 749,'o' => 48425}
实数 0.51
用户 0.49
系统 0.02
基于Ants Aasma 的回答（修改为支持 unicode）：
#!/usr/bin/env python
import codecs, itertools, operator, sys
import numpy
filename = sys.argv[1] if len(sys.argv)>1 else '/usr/share/dict/american-english'
# ucs2 or ucs4 python?
dtype = {2: numpy.uint16, 4: numpy.uint32}[len(buffer(u"u"))]
# count ordinals
text = codecs.open(filename, encoding='utf-8').read()
a = numpy.frombuffer(text, dtype=dtype)
counts = numpy.bincount(a)
# pretty print
counts = [(unichr(i), v) for i, v in enumerate(counts) if v]
counts.sort(key=operator.itemgetter(1))
print ' '.join('("%s" %d)' % c for c in counts if c[0] not in ' \t\n')
输出：
("Å" 1) ("í" 2) ("ô" 2) ("å" 3) ("û" 3) ("ç" 4) ("â" 6) ("ê" 6) ("ñ" 6) ("ä" 7) ("á" 10) ("ó" 10) ("ö" 12) ("ü" 12) ("è" 29) ("X" 42) ("Q" 63) ("U" 117) ("é" 128) ("Y" 140) ("Z" 150) ("V" 330) ("I" 344) ("O" 354) ("F" 502) ("W" 507) ("N" 531) ("J" 539) ("E" 618) ("K" 656) ("R" 749) ("D" 809) ("G" 811) ("T" 858) ("H" 860) ("L" 912) ("P" 974) ("A" 1345) ("j" 1376) ("B" 1387) ("q" 1447) ("S" 1515) ("C" 1549) ("M" 1686) ("x" 2082) ("z" 3088) ("w" 6924) ("v" 7573) ("k" 7800) ("f" 10049) ("y" 12367) ("b" 14137) ("h" 18453) ("m" 20747) ("p" 20917) ("g" 22262) ("'" 24511) ("u" 25810) ("d" 28068) ("c" 30020) ("l" 39914) ("o" 48425) ("t" 51588) ("r" 56286) ("n" 56696) ("a" 62778) ("i" 66548) ("s" 86620) ("e" 87823)
real 0.07
user 0.06
sys 0.01
// $ g++ *.cc -lboost_program_options
// $ ./a.out /usr/share/dict/american-english
#include <iostream>
#include <fstream>
#include <cstdlib> // exit
#include <boost/program_options/detail/utf8_codecvt_facet.hpp>
#include <boost/tr1/unordered_map.hpp>
#include <boost/foreach.hpp>
int main(int argc, char* argv[]) {
using namespace std;
// open input file
if (argc != 2) {
cerr << "Usage: " << argv[0] << " <filename>\n";
exit(2);
}
wifstream f(argv[argc-1]);
// assume the file has utf-8 encoding
locale utf8_locale(locale(""),
new boost::program_options::detail::utf8_codecvt_facet);
f.imbue(utf8_locale);
// count characters frequencies
typedef std::tr1::unordered_map<wchar_t, size_t> hashtable_t;
hashtable_t counts;
for (wchar_t ch; f >> ch; )
counts[ch]++;
// print result
wofstream of("output.utf8");
of.imbue(utf8_locale);
BOOST_FOREACH(hashtable_t::value_type i, counts)
of << "(" << i.first << " " << i.second << ") ";
of << endl;
}
结果：
$ cat output.utf8
(í 2) (O 354) (P 974) (Q 63) (R 749) (S 1,515) (ñ 6) (T 858) (U 117) (ó 10) (ô 2) (V 330) (W 507) (X 42) (ö 12) (Y 140) (Z 150) (û 3) (ü 12) (a 62,778) (b 14,137) (c 30,020) (d 28,068) (e 87,823) (f 10,049) (g 22,262) (h 18,453) (i 66,548) (j 1,376) (k 7,800) (l 39,914) (m 20,747) (n 56,696) (o 48,425) (p 20,917) (q 1,447) (r 56,286) (s 86,620) (t 51,588) (u 25,810) (Å 1) (' 24,511) (v 7,573) (w 6,924) (x 2,082) (y 12,367) (z 3,088) (A 1,345) (B 1,387) (C 1,549) (á 10) (â 6) (D 809) (E 618) (F 502) (ä 7) (å 3) (G 811) (H 860) (ç 4) (I 344) (J 539) (è 29) (K 656) (é 128) (ê 6) (L 912) (M 1,686) (N 531)
// $ gcc -O3 cc_ascii.c -o cc_ascii && time -p ./cc_ascii < input.txt
#include <stdio.h>
enum { N = 256 };
size_t counts[N];
int main(void) {
// count characters
int ch = -1;
while((ch = getchar()) != EOF)
++counts[ch];
// print result
size_t i = 0;
for (; i < N; ++i)
if (counts[i])
printf("('%c' %zu) ", (int)i, counts[i]);
return 0;
}
如何避免循环内的浮动操作并在一切完成后执行？
这样，您每次都可以+1，而且应该更快。
并按照 S.Lott 的建议更好地使用 collections.defaultdict。
freqs=collections.defaultdict(int)
for char in text:
freqs[char]+=1
或者您可能想尝试，python 2.7+ 中的collections.Counter
>>> collections.Counter("xyzabcxyz")
Counter({'y': 2, 'x': 2, 'z': 2, 'a': 1, 'c': 1, 'b': 1})
或者
您可以尝试psyco，它为 python 进行即时编译。你有循环，所以我认为你会通过psyco获得一些性能提升
编辑1：
我做了一些基于big.txt (~6.5 MB) 的基准测试，peter norvig将其用于拼写校正器
Text Length: 6488666
dict.get : 11.9060001373 s
93 chars {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8, ....
if char in dict : 9.71799993515 s
93 chars {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8, ....
dict try/catch : 7.35899996758 s
93 chars {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8, ....
collections.default : 7.29699993134 s
93 chars defaultdict(<type 'int'>, {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8, ....
CPU 规格：1.6GHz Intel Mobile Atom CPU
据此，dict.get最慢和collections.defaultdict最快，try/except也是最快的。
编辑2：
添加了collections.Counter基准测试，它比我的笔记本电脑慢dict.get，耗时 15 秒
collections.Counter : 15.3439998627 s
93 chars Counter({u' ': 1036511, u'e': 628234, u't': 444459, u'a': 395872, u'o': 382683, u'n': 362397, u'i': 348464,
我已经为 Python 编写了 Char Counter C Extension ，看起来比 300倍快150 倍collections.Countercollections.default(int)
C Char Counter : 0.0469999313354 s
93 chars {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8,
这是字符计数器 C 扩展代码
static PyObject *
CharCounter(PyObject *self, PyObject *args, PyObject *keywds)
{
wchar_t *t1;unsigned l1=0;
if (!PyArg_ParseTuple(args,"u#",&t1,&l1)) return NULL;
PyObject *resultList,*itemTuple;
for(unsigned i=0;i<=0xffff;i++)char_counter[i]=0;
unsigned chlen=0;
for(unsigned i=0;i<l1;i++){
if(char_counter[t1[i]]==0)char_list[chlen++]=t1[i];
char_counter[t1[i]]++;
}
resultList = PyList_New(0);
for(unsigned i=0;i<chlen;i++){
itemTuple = PyTuple_New(2);
PyTuple_SetItem(itemTuple, 0,PyUnicode_FromWideChar(&char_list[i],1));
PyTuple_SetItem(itemTuple, 1,PyInt_FromLong(char_counter[char_list[i]]));
PyList_Append(resultList, itemTuple);
Py_DECREF(itemTuple);
};
return resultList;
}
其中 char_counter 和 char_list 在模块级别是 malloc 的，所以每次函数调用时都不需要 malloc。
char_counter=(unsigned*)malloc(sizeof(unsigned)*0x10000);
char_list=(wchar_t*)malloc(sizeof(wchar_t)*0x10000);
它返回一个带有元组的列表
[(u'T', 16282), (u'h', 287323), (u'e', 628234), (u' ', 1036511), (u'P', 8946), (u'r', 303977), (u'o', 382683), ...
要转换为 dict 格式，就可以了dict()。
dict(CharCounter(text))
PS：基准包括转换为 dict 的时间
CharCounter只接受 Python Unicode String u""，如果文本是 utf8 ，需要.decode("utf8")提前做。
输入支持 Unicode，直到基本多语言平面 (BMP) - 0x0000 到 0xFFFF
不，这不是最快的，因为您知道字符的范围有限，您可以使用列表和直接索引，使用字符的数字表示来存储频率。
这是非常非常难以击败dict的。由于 Python 中的几乎所有内容都是基于 dict 的，因此它进行了高度调整。
我不熟悉python，但是对于查找频率，除非您知道频率范围（在这种情况下您可以使用数组），否则字典是要走的路。
如果您知道 unicode、ASCII 等范围内的字符，则可以定义具有正确数量值的数组。
但是，这会将其空间复杂度从 O(n) 更改为 O(可能的 n)，但是您将获得从 O(n*(字典提取/插入时间)) 到 O(n) 的时间复杂度改进。
如果您真的关心速度，您可以考虑先用整数计算字符，然后通过（浮点）除法获得频率。
以下是数字：
python -mtimeit -s'x=0' 'x+=1'
10000000 loops, best of 3: 0.0661 usec per loop
python -mtimeit -s'x=0.' 'x+=1.'
10000000 loops, best of 3: 0.0965 usec per loop
好吧，你可以用老式的风格来做......因为我们知道没有太多不同的字符并且它们是连续的，我们可以使用普通数组（或此处的列表）并使用字符序号进行索引：
s = 1.0*len(text)
counts = [0]*256 # change this if working with unicode
for char in text:
freqs[ord(char)]+=1
freqs = dict((chr(i), v/s) for i,v in enumerate(counts) if v)
这可能会更快，但只是通过一个常数因素，两种方法应该具有相同的复杂性。
在古腾堡计划的《爱丽丝梦游仙境》（163793 个字符）和“The Bible, Douay-Rheims Version”（5649295 个字符）上使用此代码：
from collections import defaultdict
import timeit
def countchars():
f = open('8300-8.txt', 'rb')
#f = open('11.txt')
s = f.read()
f.close()
charDict = defaultdict(int)
for aChar in s:
charDict[aChar] += 1
if __name__ == '__main__':
tm = timeit.Timer('countchars()', 'from countchars import countchars')
print tm.timeit(10)
我得到：
2.27324003315 #Alice in Wonderland
74.8686217403 #Bible
两本书的字符数0.029之比为 ，时间之比为0.030，因此，算法为 O(n)，常数因子非常小。我应该认为，对于大多数（所有？）目的来说足够快。
如果数据采用单字节编码，您可以使用 numpy 来加速计数过程：
import numpy as np
def char_freq(data):
counts = np.bincount(np.frombuffer(data, dtype=np.byte))
freqs = counts.astype(np.double) / len(data)
return dict((chr(idx), freq) for idx, freq in enumerate(freqs) if freq > 0)
一些快速的基准测试表明，这比聚合到 defaultdict(int) 快大约 10 倍。
为了避免除了开销之外的尝试，您可以使用默认字典。
小加速将是dict.setdefault方法的使用，这样你就不会为每个新遇到的角色付出相当大的代价：
for char in text:
freq[char] = freq.setdefault(char, 0.0) + P
作为旁注：裸露except:被认为是非常糟糕的做法。