如何用大量的键快速地对dict()进行排序？

Question

TLE总是发生在使用python的SBANK SPOJ中。为了解决这个问题，我必须对dict()进行排序，尽管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**

EDIT1:According到Justin的提示，我在下面更新我的代码，但仍然返回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]))

Answer 1

我解决了这个问题。以下是一些建议：

1. 使用Python2.5。它比Python3.2快得多，后者是Python在SPOJ上可用的另一个选项。只有一个人能够使用Python3.2获得足够快的解决方案
2. 只是用一个基本的方法来计数。您也可以从集合模块中获得defaultdict，但是基本的dict对我来说更快。
3. 只对迪克的键进行排序，而不是对键项对进行排序。形成密钥对需要花费太长的时间。另外，请使用keys = mydict.keys(); keys.sort()，因为这是最快的方法。
4. 使用精神病学(在Python中几乎总是使用SPOJ问题)
5. 学习用Python进行输入和输出的最快方法。提示:例如，它并不是迭代每一行输入。
6. 试着在添加了每个部分(输入、计数、输出)之后提交，以了解您的时间在哪里。这是在SPOJ上做的一件非常有价值的事情。运行代码的SPOJ计算机很可能比当前计算机慢得多，如果对SPOJ来说足够快，则很难根据您自己计算机的代码运行时间来确定它。

Answer 2

dict没有排序，这就是它们如何提供O(1)插入和获取访问的方式。(我相信，在内部，它们是作为哈希表实现的，尽管我不确定这是Python规范所要求的)。

如果要按排序顺序迭代dict的键，可以使用：

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

但是，正如您注意到的，对10万个元素进行排序可能需要一些时间。

作为另一种选择，您可以编写(或在互联网上找到)排序的dict实现，这些实现与字典一起保留一个有序的键列表，并支持按键快速查找，并按照顺序进行迭代，而不必一次排序。当然，为了支持排序顺序，键需要在插入时进行排序，所以插入不会是O(1)。

编辑：按德索里马诺的注释，如果您使用的是Python2.7或Python3.x，则有一个内置的OrderedDict类，它按照插入顺序排序迭代，这样可以保持插入速度，但可能无法完成所需的操作(取决于所需项的顺序)。

Answer 3

由于Python3.1是可用的，所以collections.Counter很适合这个目的：

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