次のような辞書があります。
{'abc':100,'xyz':200,'def':250 .............}
これは、エンティティの名前をキーとし、そのエンティティの数を値とする辞書です。辞書から上位 10 個の要素を返す必要があります。
ヒープを記述してこれを行うことはできますが、特定の値が等しくなるため、値とキーのマッピングをどのように行うかはわかりません。
これを行うための他のデータ構造はありますか?
ベストアンサー1
heapqおそらく次のような操作を行うことになります:
heap = [(-value, key) for key,value in the_dict.items()]
largest = heapq.nsmallest(10, heap)
largest = [(key, -value) for value, key in largest]
heapq最小ヒープのみを実装しているため、値を反転して、大きい値が小さくなるようにする方がよいことに注意してください。
このソリューションは、ヒープのサイズが小さい場合には遅くなります。次に例を示します。
>>> import random
>>> import itertools as it
>>> def key_generator():
... characters = [chr(random.randint(65, 90)) for x in range(100)]
... for i in it.count():
... yield ''.join(random.sample(characters, 3))
...
>>> the_dict = dict((key, random.randint(-500, 500)) for key, _ in zip(key_generator(), range(3000)))
>>> def with_heapq(the_dict):
... items = [(-value, key) for key, value in the_dict.items()]
... smallest = heapq.nsmallest(10, items)
... return [-value for value, key in smallest]
...
>>> def with_sorted(the_dict):
... return sorted(the_dict.items(), key=(lambda x: x[1]), reverse=True)[:10]
...
>>> import timeit
>>> timeit.timeit('with_heapq(the_dict)', 'from __main__ import the_dict, with_heapq', number=1000)
0.9220538139343262
>>> timeit.timeit('with_sorted(the_dict)', 'from __main__ import the_dict, with_sorted', number=1000)
1.2792410850524902
3000 個の値の場合、の代わりにsortedとなるバージョンよりもわずかに高速になります。辞書のサイズを 10000 に増やすと、バージョンはさらに高速になります。O(nlogn)O(n + mlogn)heapq
>>> timeit.timeit('with_heapq(the_dict)', 'from __main__ import the_dict, with_heapq', number=1000)
2.436316967010498
>>> timeit.timeit('with_sorted(the_dict)', 'from __main__ import the_dict, with_sorted', number=1000)
3.585728168487549
タイミングは、実行しているマシンによっても異なる可能性があります。自分のケースではどのソリューションが最適かをプロファイルする必要があります。効率が重要でない場合は、sortedよりシンプルなバージョンを使用することをお勧めします。