次のような辞書があります。
{'abc':100,'xyz':200,'def':250 .............}
エンティティの名前としてキーを持つ辞書であり、値はそのエンティティの数です。辞書から上位 10 個の要素を返す必要があります。
それを行うためにヒープを書くことはできますが、特定の値が等しくなるため、値からキーへのマッピングを行う方法がわかりません。
これを行うための他のデータ構造はありますか?
質問する
22262 次
8 に答える
23
あなたを使用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
sorted値が 3000 の場合、バージョンよりわずかに高速O(nlogn)ですO(n + mlogn)。dict のサイズを 10000 に増やすと、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効率が重要でない場合は、よりシンプルなバージョンを使用することをお勧めします。
于 2013-02-10T07:23:04.797 に答える
2
数値が 2 位であると仮定して、上位 10 個の要素を取得するには、次のようにします。
from operator import itemgetter
topten = sorted(mydict.items(), key=itemgetter(1), reverse = True)[0:10]
値で並べ替えたい場合は、キーを に変更しkey=itemgetter(1,0)ます。
データ構造に関しては、ヒープはあなたが望むもののように聞こえます。それらをタプルとして保持し、数値項を比較してください。
于 2013-02-10T06:54:03.197 に答える
1
ディクショナリが一定のままである場合は、直接またはcollections.Counterを介してheapqを作成しようとする代わりに、値をキーとして逆順に使用してディクショナリ項目をソートし、そこから最初の 10 個の要素を取得することができます。タプルから辞書を再作成する必要があります
>>> some_dict = {string.ascii_lowercase[random.randint(0,23):][:3]:random.randint(100,300) for _ in range(100)}
>>> some_dict
{'cde': 262, 'vwx': 175, 'xyz': 163, 'uvw': 288, 'qrs': 121, 'mno': 192, 'ijk': 103, 'abc': 212, 'wxy': 206, 'efg': 256, 'opq': 255, 'tuv': 128, 'jkl': 158, 'pqr': 291, 'fgh': 191, 'lmn': 259, 'rst': 140, 'hij': 192, 'nop': 202, 'bcd': 258, 'klm': 145, 'stu': 293, 'ghi': 264, 'def': 260}
>>> sorted(some_dict.items(), key = operator.itemgetter(1), reverse = True)[:10]
[('stu', 293), ('pqr', 291), ('uvw', 288), ('ghi', 264), ('cde', 262), ('def', 260), ('lmn', 259), ('bcd', 258), ('efg', 256), ('opq', 255)]
ヒープを作成するために heapq を使用している場合は、nlogn操作が必要です。要素を挿入してヒープを構築している場合、またはリストをヒープ化する場合は、最上位の要素をフェッチlognする操作が続きます。mlognm
アイテムを並べ替える場合、Python の並べ替えアルゴリズムはO(nlogn)最悪の場合 ( TIM Sortを参照) であることが保証されており、最初の 10 個の要素をフェッチすることは一定の操作になります。
于 2013-02-10T06:50:02.893 に答える
0
バクリウの答えは正しいです（heapq.nlargestを使用してください）。
しかし、使用する適切なアルゴリズムに興味がある場合、クイックセレクトはクイックソートと同様の原理を使用し、同じ人物であるCARHoareによって発明されました。
ただし、配列を完全に並べ替えていない点が異なります。終了後、上位n個の要素を要求した場合、それらは配列の最初のn個の位置にありますが、必ずしも並べ替えられた順序である必要はありません。
クイックソートと同様に、ピボット要素を選択し、すべてのa [：j]がa [j]以下になり、すべてのa [j + 1：]がa[j]より大きくなるように配列をピボットすることから始めます。
次に、j == nの場合、最大の要素はa [：j]です。j> nの場合、クイックセレクトはピボットの左側の要素でのみ再帰的に呼び出されます。また、j <nの場合、ピボットの右側の要素でクイックセレクトが呼び出され、それらからn--j-1個の最大の要素が抽出されます。
クイックセレクトは配列の片側でのみ再帰的に呼び出されるため（両方で再帰的に呼び出されるクイックソートとは異なり）、線形時間で機能します（入力がランダムに順序付けられ、繰り返されるキーがない場合）。これは、再帰呼び出しをwhileループに変えるのにも役立ちます。
ここにいくつかのコードがあります。それを理解しやすくするために、外側のwhileループの不変条件は、要素xs [：lo]がn個の最大のリストに含まれることが保証され、要素xs [hi：]がn個の最大に含まれないことが保証されることです。
import random
def largest_n(xs, n):
lo, hi = 0, len(xs)
while hi > n:
i, j = lo, hi
# Pivot the list on xs[lo]
while True:
while i < hi and xs[i] >= xs[lo]:
i += 1
j -= 1
while j >= lo and xs[j] < xs[lo]:
j -= 1
if i > j:
break
xs[i], xs[j] = xs[j], xs[i]
# Move the pivot to xs[j]
if j > lo:
xs[lo], xs[j] = xs[j], xs[lo]
# Repeat on one side or the other based on the location of the pivot.
if n <= j:
hi = j
else:
lo = j + 1
return xs[:n]
for k in xrange(100):
xs = range(1000)
random.shuffle(xs)
xs = largest_n(xs, 10)
assert sorted(xs) == range(990, 1000)
print xs
于 2013-02-10T08:31:59.123 に答える
0
以下はどうですか、O(len(xs))のはずです。
最初の n 個の要素を、残りの要素のうち最大のものと交換するだけです。
def largest_n(xs, n):
for i in range(n):
for j in range(i+1,len(xs)):
if xs[j] > xs [i]:
xs[i], xs[j] = xs[j], xs[i]
return xs[:n]
于 2014-04-22T13:54:33.333 に答える
0
次のような dict を想像してみてください ( a-za=1 と z=26 のマッピング):
>>> d={k:v for k,v in zip((chr(i+97) for i in range(26)),range(1,27))}
>>> d
{'g': 7, 'f': 6, 'e': 5, 'd': 4, 'c': 3, 'b': 2, 'a': 1, 'o': 15, 'n': 14, 'm': 13, 'l': 12, 'k': 11, 'j': 10, 'i': 9, 'h': 8, 'w': 23, 'v': 22, 'u': 21, 't': 20, 's': 19, 'r': 18, 'q': 17, 'p': 16, 'z': 26, 'y': 25, 'x': 24}
今、あなたはこれを行うことができます:
>>> v=list(d.values())
>>> k=list(d.keys())
>>> [k[v.index(i)] for i in sorted(d.values(),reverse=True)[0:10]]
['z', 'y', 'x', 'w', 'v', 'u', 't', 's', 'r', 'q']
また、マッピングの一部の値が等しくなると述べました。ここで、マッピング 1 ～ 26dの文字が含まれるように更新しましょう。A-Z
>>> d.update({k:v for k,v in zip((chr(i+65) for i in range(26)),range(1,27))})
との両方が次の場所A-Zにa-zマップされ1-26ます。
>>> d
{'G': 7, 'F': 6, 'E': 5, 'D': 4, 'C': 3, 'B': 2, 'A': 1, 'O': 15, 'N': 14, 'M': 13, 'L': 12, 'K': 11, 'J': 10, 'I': 9, 'H': 8, 'W': 23, 'V': 22, 'U': 21, 'T': 20, 'S': 19, 'R': 18, 'Q': 17, 'P': 16, 'Z': 26, 'Y': 25, 'X': 24, 'g': 7, 'f': 6, 'e': 5, 'd': 4, 'c': 3, 'b': 2, 'a': 1, 'o': 15, 'n': 14, 'm': 13, 'l': 12, 'k': 11, 'j': 10, 'i': 9, 'h': 8, 'w': 23, 'v': 22, 'u': 21, 't': 20, 's': 19, 'r': 18, 'q': 17, 'p': 16, 'z': 26, 'y': 25, 'x': 24}
したがって、マッピングが重複している場合、適切な結果は次の値を持つキーのリストを返すことだけです。
>>> [[k[x] for x,z in enumerate(v) if z==i ] for i in sorted(d.values(),reverse=True)[0:10]]
[['Z', 'z'], ['Z', 'z'], ['Y', 'y'], ['Y', 'y'], ['X', 'x'], ['X', 'x'], ['W', 'w'], ['W', 'w'], ['V', 'v'], ['V', 'v']]
ここで heapq を使用できます。
[[k[x] for x,z in enumerate(v) if z==i ] for i in heapq.nlargest(10,v)]
重複した結果で何をしたいかを述べていないので、結果リストが N の長さのままである間、それらの重複を排除したいと思うでしょう。
これはそれを行います：
def topn(d,n):
res=[]
v=d.values()
k=d.keys()
sl=[[k[x] for x,z in enumerate(v) if z==i] for i in sorted(v)]
while len(res)<n and sl:
e=sl.pop()
if e not in res:
res.append(e)
return res
>>> d={k:v for k,v in zip((chr(i+97) for i in range(26)),range(1,27))}
>>> d.update({k:v for k,v in zip((chr(i+65) for i in range(0,26,2)),range(1,27,2))})
>>> topn(d,10)
[['z'], ['Y', 'y'], ['x'], ['W', 'w'], ['v'], ['U', 'u'], ['t'], ['S', 's'], ['r'], ['Q', 'q']]
于 2013-02-10T07:33:42.457 に答える