素早くdict（）を大量のキーでソートするには？

Question

TLEは常にPythonを使用してSBANK SPOJで発生します。それを解決するには、dict()にはKEYS（最大 - 100000）の莫大な数がありますが、dict()をソートする必要があります。私のコードで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：ジャスティンピールのヒントによると、私は以下の私のコードを更新し、それでも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. Python 2.5を使用してください。これはPython 3.2よりはるかに高速です。これは、PythonでSPOJで利用できるもう1つのオプションです。一人の人間だけがPython 3.2を使って十分に速い解を得ることができました
2. カウントには基本ディクテーションを使用してください。あなたはcollectionsモジュールからdefaultdictで取得することもできますが、基本的なdictは私にとってより高速でした。
3. キー項目のペアではなく、辞書のキーのみをソートします。キーとアイテムのペアを形成するには時間がかかりすぎる。また、それは最速の方法であるので、keys = mydict.keys(); keys.sort()を使用してください。
4. psycoを使用してください（ほとんどの場合、PythonでSPOJの問題が発生します）
5. Pythonで入出力を行うための最も速い方法を学びます。ヒント：たとえば、入力行ごとに反復しているわけではありません。
6. 各パートを追加した後（入力の取得、カウント、出力の実行）に送信して、現在の場所を確認してください。これはSPOJにとって非常に貴重なことです。あなたのコードを実行しているSPOJコンピュータはあなたの現在のコンピュータよりかなり遅い可能性が非常に高く、SPOJにとって十分速い場合は自分のコンピュータの実行時間に基づいて判断するのが難しいかもしれません。

Answer 2

dict sが、彼らはO（1）を挿入し、アクセスを得るを提供することが可能であるかである、ソートされていません。 （内部的には、これらはハッシュテーブルとして実装されていますが、Python仕様ではこれが必須かどうかはわかりませんが）あなたが100,000の要素をソートすると、多少時間がかかることがあり、注意するよう

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

しかし、：

あなたはソート順にdictのキーを反復処理する場合は、使用することができます。

代わりに、ソートされたdictの実装では、辞書と並んでキーの順序付きリストを保持し、すべてでソートせずにキーによる高速ルックアップと順番をサポートすることができます一度。もちろん、ソートされた順序をサポートするには、挿入時にキーをソートする必要があるため、挿入はO（1）になりません。

編集：あなたは、Python 2.7またはPythonの3.xを使用している場合はパーdsolimanoのコメント、ビルトインOrderedDictクラスは、挿入順に受注反復ということがあります。これは挿入を速くしますが、必要なものを実行しない可能性があります（必要な項目の順序によって異なります）。

Answer 3

のPython 3.1が利用可能であるので、collections.Counterは、その目的のために良いです：

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