python - 如何用海量键快速对 dict() 进行排序？

Question

TLE 总是发生在 SBANK SPOJ使用 python 。为了解决这个问题，我必须对 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:根据 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]))

Answer 1

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

如果你想按排序顺序迭代 dict 的键，你可以使用:

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

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

作为替代方案，您可以编写(或在 Internet 上找到)排序的 dict 实现，该实现将键的有序列表与字典一起保存，并支持按键快速查找和按顺序迭代无需一次全部排序。当然，为了支持排序顺序，需要在插入时对键进行排序，因此插入不会是 O(1)。

编辑:根据 dsolimano的评论，如果您使用的是 Python 2.7 或 Python 3.x，则有一个内置的 OrderedDict 类可以按插入顺序对迭代进行排序。这可以保持快速插入，但可能无法满足您的需要(取决于您想要的项目顺序)。