代码之家 › 专栏 › 技术社区 › tonyahu

比较字典中列表的值

minimum heap tuples dictionary python

tonyahu · 技术社区 · 7 年前

字典包括一个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

很抱歉,这太长了,但我已经仔细研究了很多关于堆栈溢出的其他问题,还没有找到解决方案。如有任何建议,我们将不胜感激!

2 回复 | 直到 7 年前

Patrick Haugh 7 年前

如果您正在比较 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通过比较第一个元素来比较元组,这就是我们想要比较的。请记住,如果其中两个元组共享一个 权力

PM 2Ring 7 年前

下面的代码使用了与Patrick Haugh的答案类似的策略,只是它还维护了您的字典。正如Patrick的回答一样,我们将幂值放在元组的开头,这样它就可以按堆正确排序。我们将整数键附加到堆上元组的末尾,因为我们需要它来删除已被取代的dict项。

一旦达到所需的大小限制,我们只需要检查当前最小的项目。如果最小的项目小于新项目,则会被替换。

测试 update 代码我创建了一个生成器, datagen

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)

输出

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]) 调用不是必需的,但它对测试和调试很有用。