辞書内のリストの値を比較する

Question

バックグラウンドでは、上位50個の値を辞書に保存し、50個の値を1回保存するルーチンを作成しようとしています。

私は、辞書の内部で使用されるタプルの値を比較する方法を理解しようとしています。

辞書は、キーとしてintを含み、x、y、z座標のタプルおよびその位置に関連付けられたべき乗値で構成されます。したがって、このような何か：

int = 1    #all of these values will change with every iteration or new element 
x_pos = 10.0 
y_pos = 20.0 
z_pos = 30.0 
power = 9000.0 

dictTop50[int] = (x_pos,y_pos,z_pos,power) 

私が試した何が私の辞書のうちの最小値を取得するには、ヒープを使用することでしたが、私はその間違っているかもしれないと思います。さらに、私が見つけた新しい値を辞書の中にあるものとどうやって比較し、それらを置き換えることができるかは完全にはわかりません。ここではその時の私の試みは次のとおりです。擬似コードで

if (len(dictTop50) <= 50): 
    dictTop50[int] = (x_pos, y_pos, z_pos, power) 
elif (new power value bigger than any of the 50 other power values): 
    del dictTop50[heapq.nsmallest(1, dictTop50(), key=itemgetter(1))] 
    dictTop50[int] = (x_pos, y_pos, z_pos, power) 

：

if dictionary has 50 or less entries: 
    just add new value to the dictionary 
else if dictionary has more than 50 entries already and new value is greater than present value: 
    delete the dictionary entry with smallest power value 
    add new dictionary element with the highest power value 

申し訳ありませんが、これが長かったが、私は、スタックオーバーフロー上の他の多くの質問を通じてコーマきたし、まだ解決策を見つけることができませんでした。どんな提案も大歓迎です！

Answer 1

以下のコードでは、Patrick Haughの答えに似た戦略が使用されていますが、それは辞書も維持されます。パトリックの答えと同じように、タプルの先頭にパワー値を置くことで、ヒープによって正しくソートされるようにします。置き換えられたdict項目を削除するために必要なので、ヒープに行くタプルの最後に整数キーを追加します。

希望のサイズ制限に達したら、現在の最小の項目を確認するだけです。その最小のアイテムが新しいアイテムよりも小さい場合、それは置き換えられます。

updateコードをテストするために、私は偽データを作成する発電機datagenを作成しました。扱いやすい出力を維持するために、私はむしろ

0 (8200.0, 15.0, 4.0, 95.0) 
1 (3600.0, 32.0, 29.0, 18.0) 
2 (9500.0, 14.0, 87.0, 95.0) 
3 (7000.0, 12.0, 76.0, 55.0) 
4 (500.0, 4.0, 12.0, 28.0) 
5 (3000.0, 65.0, 78.0, 4.0) 
6 (7200.0, 26.0, 92.0, 84.0) 
7 (9000.0, 70.0, 54.0, 29.0) 
8 (5800.0, 76.0, 36.0, 1.0) 
9 (9800.0, 21.0, 90.0, 55.0) 
10 (4400.0, 36.0, 20.0, 28.0) 
11 (9800.0, 44.0, 14.0, 12.0) 
12 (4900.0, 13.0, 46.0, 45.0) 
13 (7800.0, 34.0, 6.0, 94.0) 
14 (5900.0, 69.0, 16.0, 49.0) 
15 (1100.0, 71.0, 38.0, 81.0) 
16 (8000.0, 47.0, 74.0, 25.0) 
17 (9100.0, 9.0, 6.0, 85.0) 
18 (3000.0, 99.0, 38.0, 11.0) 
19 (3000.0, 13.0, 49.0, 36.0) 
20 (5900.0, 82.0, 47.0, 21.0) 
replaced 500.0 
21 (4800.0, 46.0, 27.0, 86.0) 
replaced 1100.0 
22 (3500.0, 90.0, 88.0, 83.0) 
replaced 3000.0 
23 (1000.0, 78.0, 82.0, 22.0) 
24 (6900.0, 94.0, 32.0, 21.0) 
replaced 3000.0 
25 (6000.0, 49.0, 35.0, 82.0) 
replaced 3000.0 
26 (8900.0, 72.0, 29.0, 88.0) 
replaced 3500.0 
27 (4200.0, 99.0, 100.0, 8.0) 
replaced 3600.0 
28 (3000.0, 5.0, 41.0, 52.0) 
29 (3500.0, 9.0, 28.0, 73.0) 
30 (9200.0, 41.0, 28.0, 84.0) 
replaced 4200.0 
31 (6400.0, 51.0, 83.0, 59.0) 
replaced 4400.0 
32 (1900.0, 34.0, 18.0, 32.0) 
33 (9600.0, 72.0, 69.0, 34.0) 
replaced 4800.0 
34 (9600.0, 75.0, 55.0, 75.0) 
replaced 4900.0 
35 (5200.0, 47.0, 29.0, 18.0) 
36 (6600.0, 64.0, 12.0, 97.0) 
replaced 5800.0 
37 (700.0, 15.0, 20.0, 81.0) 
38 (2100.0, 88.0, 55.0, 77.0) 
39 (900.0, 50.0, 49.0, 77.0) 
40 (6000.0, 68.0, 33.0, 71.0) 
replaced 5900.0 
41 (200.0, 88.0, 93.0, 15.0) 
42 (8800.0, 69.0, 97.0, 35.0) 
replaced 5900.0 
43 (9900.0, 83.0, 44.0, 15.0) 
replaced 6000.0 
44 (3800.0, 56.0, 21.0, 59.0) 
45 (100.0, 93.0, 93.0, 34.0) 
46 (6500.0, 98.0, 23.0, 65.0) 
replaced 6000.0 
47 (1400.0, 81.0, 39.0, 82.0) 
48 (6500.0, 78.0, 26.0, 20.0) 
replaced 6400.0 
49 (4800.0, 98.0, 21.0, 70.0) 

print('replaced', old[0])呼び出しは必要ありませんトップ50

from random import seed, randint 
from heapq import heappush, heapreplace 

seed(42) 

# Make some fake data, in this form: (power, x_pos, y_pos, z_pos) 
def datagen(): 
    m = (100., 1., 1., 1.) 
    while True: 
     yield tuple(randint(1, 100) * u for u in m) 

top20 = {} 
heap = [] 

# Update the heap & the dict 
def update(k, tup): 
    if len(top20) < 20: 
     heappush(heap, tup + (k,)) 
     top20[k] = tup 
    elif tup[0] > heap[0][0]: 
     old = heapreplace(heap, tup + (k,)) 
     top20[k] = tup 
     del top20[old[-1]] 
     print('replaced', old[0]) 

# Test 

for k, tup in zip(range(50), datagen()): 
    print(k, tup) 
    update(k, tup) 

出力よりも、トップ20リストにサイズを縮小しましたが、それはですテストやデバッグに役立ちます。

Answer 2

powerの値を比較する場合、各タプルの最初の値がpowerの値であるタプルのヒープを使用できます。何かのように

import heapq 

def push_keep_fifty(heap, new): 
    if len(heap) < 50: 
     heapq.heappush(heap, new) 
    elif new > heap[0]: 
     heapq.heapreplace(heap, new) 

i = 1 #don't use int as a variable name 
x_pos = 10.0 
y_pos = 20.0 
z_pos = 30.0 
power = 9000.0 

heap = [] 
push_keep_fifty(heap, (power, i, x_pos, y_pos)) 

これは、Pythonがタプルを最初の要素（比較したいもの）と比較して比較するためです。これらのタプルのうちの2つがpowerの値を共有する場合は、2番目の要素を比較して比較します。