如何快速排序拥有大量键的dict()?

2 投票

3 回答

3795 浏览

提问于 2025-04-16 13:47

在使用Python做SBANK这个题目时，总是出现超时错误（TLE）。为了能解决这个问题，我需要对一个字典（dict）进行排序，但这个字典的键（KEYS）数量非常多，最多可以有100000个。用我代码里的sorted()函数排序效果不明显。有没有什么更快的解决办法？谢谢大家的帮助。

我的代码如下：

for j in range(n): # n is the number of keys
        account = sys.stdin.readline().rstrip()
        dic.setdefault(account, 0)
        dic[account] += 1
sorted(dic) # **this sort take a lot of time**

编辑1：根据Justin Peel的建议，我更新了我的代码，但还是出现了超时错误（TLE）。我该怎么办呢？

import sys
import psyco # import psyco module to speed up
psyco.full()
nCase = int(sys.stdin.readline().split()[0])
for i in range(nCase):
    n = int(sys.stdin.readline().split()[0])
    dic = dict()
    lst = list()
    for j in range(n):
        account = sys.stdin.readline().rstrip()
        dic.setdefault(account, 0)
        dic[account] += 1
    sys.stdin.readline()
    lst = dic.keys() # store keys in list
    lst.sort()
    for account in lst:
        sys.stdout.write('%s %s\n' % (account, dic[account]))

大数据处理数据结构排序算法算法优化字典排序性能提升超时错误

3 个回答

自从Python 3.1发布以来，collections.Counter这个工具就非常适合用来做这个事情：

collections.Counter(map(str.rstrip, sys.stdin)).most_common()

回答于 2025-04-16 由 Python大师

分享举报

dict（字典）是无序的，这样它们才能在插入和获取数据时都能做到很快（大约是O(1)的时间）。其实，字典内部是用哈希表来实现的，虽然我不确定这是否是Python的规定。

如果你想按顺序遍历字典里的键，可以使用：

for key in sorted(the_dict.iterkeys()):
    value = the_dict[key]
    # do something

不过，正如你所提到的，给10万个元素排序可能需要一些时间。

另外，你也可以自己写一个（或者在网上找）有序字典的实现，这种字典会同时保持一个有序的键列表，并且支持通过键快速查找，同时可以按顺序遍历，而不需要一次性排序。当然，为了保持有序，插入时就需要对键进行排序，所以插入的速度就不会是O(1)了。

补充：根据dsolimano的评论，如果你使用的是Python 2.7或Python 3.x，内置有一个叫OrderedDict的类，它会按照插入的顺序来遍历。这种方式插入速度很快，但可能不符合你想要的顺序（这取决于你想要的项目顺序）。

回答于 2025-04-16 由 Python大师

分享举报

我解决了这个问题。这里有一些小建议：

使用 Python 2.5。它比 Python 3.2 快很多，而 Python 3.2 是在 SPOJ 上可用的另一个选项。只有一个人能用 Python 3.2 得到足够快的解决方案。
用基本的字典来计数。你也可以用 collections 模块里的 defaultdict，但我发现基本字典更快。
只对字典的键进行排序，而不是键值对。形成键值对的过程太慢了。而且，使用 keys = mydict.keys(); keys.sort() 是最快的做法。
使用 psyco（几乎总是适用于 Python 的 SPOJ 问题）。
学习在 Python 中进行输入和输出的最快方法。提示：这不是逐行处理每一行输入。
在你添加每个部分（获取输入、计数、输出）后尝试提交，看看你的时间表现如何。这在 SPOJ 上是非常有价值的。运行你代码的 SPOJ 计算机可能比你现在的电脑慢得多，因此仅凭你自己电脑上代码的运行时间很难判断它是否足够快。

回答于 2025-04-16 由 Python大师

分享举报

如何快速排序拥有大量键的dict()?

3 个回答

撰写回答