在字典中查找与条件匹配的值

Question

如果条件满足,我试图从字典设置一个值.基本上我迭代我的字典的值,并检查它们是否适合我的条件(然后我打破循环,这不是最好的做法,但保存一些迭代)

这是我正在使用的代码:

for (key,value) in zip(mn_zone_dict.keys(), mn_zone_dict.values()):
    if cost < value:
        zone = key
        break

我做它的工作,但它相对缓慢,而我必须检查> 10k记录,所以我正在寻找一些更聪明(也许更pythonic)的方法来解决这个任务.我已经看到一个函数any()但它只返回如果有这样的条目匹配条件而不告诉哪个.

我很乐意听到您的想法和建议.

Answer 1

如果您直接按原样拥有数据，只有字典结构，则每次都必须对其进行迭代。您可以获得的最佳加速是使用理解而不是循环，而dict.items不是zip：

zones = [k for k, v in my_zone_dict.items() if cost < v]

一方面，这会迭代整个字典。另一方面，它会立即告诉您有多少值符合标准（如果有）。

这里的问题是，无论推导式的开销比显式循环少多少，这仍然O(n)适用于每次查找。正确的解决方案是使用不同的或互补的数据结构。既然你想要value比某些东西更大，我建议使用最大堆。

Python 在模块中实现了堆heapq。它有点不寻常，因为它不提供堆对象，只是将列表堆化和维护为堆的函数。另外，仅支持最小堆，但这没关系，因为您始终可以否定您的值：

my_zone_list = [(-v, k) for k, v in my_zone_dict.items()]
heapq.heapify(my_zone_list)

这是一次性O(n)处罚，您永远不必重复。你的整个循环现在变成了一个O(1)操作：

if cost < -my_zone_list[0][0]:
    zone = my_zone_list[0][1]

插入新元素是有O(log(n))代价的：

heapq.heappush(my_zone_list, (-new_value, new_key))

作为旁注，如果您不能引入新的数据结构，您可能会获得更好的性能

v, zone = max((v, k) for k, v in my_zone_dict.items())
if cost < v: ...