我想计算每个字符在字符串中重复的次数.除了从AZ比较字符串的每个字符并递增计数器之外,还有什么特别的方法吗？
更新(参考安东尼的答案):无论你有什么建议,我要写26次.有没有更简单的方法？
import collections
d = collections.defaultdict(int)
for c in thestring:
d[c] += 1
A collections.defaultdict就像a dict(实际上是它的子类),但是当找到一个条目而没有找到它时,它会通过调用提供的0参数可调用来实现并插入它而不是报告它.最受欢迎的是defaultdict(int),用于计数(或者,等效地,制作多重编辑AKA包数据结构),并且defaultdict(list),它永远不需要使用.setdefault(akey, []).append(avalue)和类似的尴尬习语.
因此,一旦你完成了这个d,就像一个类似于字典的容器,将每个角色映射到它出现的次数,当然,你可以以任何你喜欢的方式发出它.例如,最受欢迎的角色首先:
for c in sorted(d, key=d.get, reverse=True): print '%s %6d' % (c, d[c])
Python 2.7+包含collections.Counter类:
import collections results = collections.Counter(the_string) print(results)
我的第一个想法是这样做:
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 count.has_key(s):
count[s] += 1
else:
count[s] = 1
for key in count:
if count[key] > 1:
print key, count[key]
这可以确保您只通过一次,而不是26次.
另外,Alex的答案很棒 - 我不熟悉收藏模块.我将来会用它.他的答案比我的更简洁,技术更优越.我建议在我的代码上使用他的代码.
因为我"没什么好做的"(理解:我做了很多工作),我决定做一些表演比赛.我收集了最明智或最有趣的答案,并timeit在CPython 3.5.1中做了一些简单的操作.我只用一个字符串测试它们,这是我案例中的典型输入:
>>> s = 'ZDXMZKMXFDKXZFKZ' >>> len(s) 16
请注意,不同输入的结果可能会有所不同,可能是字符串的长度不同,或者字符的数量不同,或者每个字符的平均出现次数不同.
Python让我们变得简单.该collections.Counter课程完全符合我们的要求,而且还有更多.到目前为止,它的使用是这里提到的所有方法中最简单的.
取自@oefe,很好找
>>> timeit('Counter(s)', globals=locals())
8.208566107001388
Counter 更进一步,这就是为什么需要这么长时间.
让我们尝试使用简单的dict代替.首先,让我们使用dict理解以声明方式进行.
我自己想出来了......
>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002
这将s从头到尾进行,对于每个角色,它将计算其出现次数s.由于s包含重复字符,因此上述方法会s多次搜索
相同的字符.结果自然总是一样的.因此,让我们计算每个角色只出现一次的次数.
我自己想出了这个,@ IrshadBhat也是如此
>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232
更好.但我们仍然需要搜索字符串来计算出现次数.一个搜索 每个不同的角色.这意味着我们将不止一次地读取字符串.我们可以做得更好!但是,为此,我们必须摆脱我们的宣示主义的高级马,并进入一种势在必行的心态.
AKA 得抓住他们!
灵感来自@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
它确实节省了一些时间,因此人们可能会试图将其用作某种优化.
不要那样做!或者实际上.现在做:
INTERLUDE 1
import time
while True:
try:
time.sleep(1)
except:
print("You're trapped in your own trap!")
你看？它KeyboardInterrupt除了其他东西之外还有其他功能.事实上,它捕获了所有例外.包括你可能没有听说过的,比如SystemExit.
INTERLUDE 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提出了一些有趣的东西.dict我们可以避免散列冲突的风险以及随之而来的分辨率开销,而不是使用散列表(也称为字典).我们还可以避免散列密钥和额外未占用的表空间的开销.我们可以用一个list.字符的ASCII值将是索引,它们的计数将是值.正如@IdanK所指出的,这个列表让我们可以不间断地访问角色的数量.我们所要做的就是使用内置函数将每个字符转换str为
.这将为我们提供一个列表索引,然后我们将使用它来增加字符的数量.所以我们做的是:我们用零初始化列表,完成工作,然后将列表转换为.这将仅包含那些具有非零计数的字符,以使其符合其他版本.intorddictdict
作为旁注,这种技术用于线性时间排序算法,称为 计数排序或计数排序.它非常有效,但排序的值范围有限,因为每个值都必须有自己的计数器.要对32位整数序列进行排序,需要43亿个计数器.
>>> 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向我通知了collections._count_elements
Python 3中可用的功能.
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
我认为在一些较大的输入上重新运行测试可能是一个好主意,因为16个字符的字符串是如此小的输入,所有可能的解决方案都相当快 (在30毫秒内1000次迭代).
我决定使用莎士比亚的全集作为测试语料库,结果证明这是一个很大的挑战(因为它的大小超过了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
NaïveΘ (n 2)时间词典理解根本不起作用
{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除非你不能或不想:)这是我能想到的最短,最实用的,无需导入额外的模块.
text = "hello cruel world. This is a sample text" d = dict.fromkeys(text, 0) for c in text: d[c] += 1
print d ['a']将输出2
它也很快.
京公网安备 11010802040832号 | 京ICP备19059560号-6 