我怎样才能让我的Python脚本快速检查列表中的字典是否具有与特定键相关联的特定值？

Question

例如我有一个这样的列表：

my_list = [{'name': 'a', 'value': 1}, {'name': 'b', 'value': 3}, {'name': 'a', 'value': 4}, {'name': 'c', 'value': 4}]

我想在不使用for循环的情况下快速获取名为“a”且值为4的字典

这是我的虚拟代码

for i in my_list:
    if i['name'] == 'a':
        if i['value'] == 4:
            print('found')
            break

它似乎是硬编码的，所以我想把它短路

Answer 1

如果您正在寻找一种“快速”方式（即比 O(N) 更好）来搜索列表，最好的选择是进行二分搜索，但这仅适用于您的列表以某种方式排序的情况这使得它可以被搜索。

在这种情况下，我观察到

my_list

按值排序，然后按名称排序。只要这是一个安全的假设，我们就可以使用

bisect.bisect

函数在 O(log N) 时间内搜索所需的项目，而不是 O(N) 时间。

from bisect import bisect

my_list = [{'name': 'a', 'value': 1}, {'name': 'b', 'value': 3}, {'name': 'a', 'value': 4}, {'name': 'c', 'value': 4}]
def list_key(d):
    """Key for sorting and bisection.
    Note that this happens to match the existing order of my_list."""
    return d['value'], d['name']

# If the list were unsorted, we would need to sort it first for bisect to work:
# my_list.sort(key=list_key)

def search_list(haystack, needle):
    i = bisect(haystack, list_key(needle), key=list_key) - 1
    return i if list_key(needle) == list_key(haystack[i]) else None

print(search_list(my_list, {'name': 'a', 'value': 4}))  # 2

正如上面评论中所观察到的，如果列表未排序，我们可以先对其进行排序以允许二分，但是要查找一个无法达到目的的值，因为排序本身是 O(N log N) ——但是，如果您正在搜索很多的值，然后进行一次排序，然后进行大量二分搜索操作将比进行大量线性搜索更快。

请注意，如果您计划进行大量搜索并且，您不能预先保证数据已排序，一个更简单的选择（尽管这与您最初的问题不同）将是直接将您的列表到字典中：

my_list = [{'name': 'a', 'value': 1}, {'name': 'b', 'value': 3}, {'name': 'a', 'value': 4}, {'name': 'c', 'value': 4}]

def list_key(d):
    """Key for dictionary lookups."""
    return d['value'], d['name']

my_dict = {list_key(d): i for i, d in enumerate(my_list)}

def search_my_list(needle):
    return my_dict.get(list_key(needle))

print(search_my_list({'name': 'a', 'value': 4}))  # 2

这空间效率较低（您本质上需要制作列表的额外副本），但构建字典只需要 O(N) 的时间，而搜索它只需要 O(1) 的时间。