在Python中检查字典列表中的项目

Question

我有一个字典的列表=

a = [{"ID":1, "VALUE":2},{"ID":2, "VALUE":2},{"ID":3, "VALUE":4},...]

"ID"是每个字典的唯一标识符。考虑到这个列表非常大，检查某个特定的"ID"是否在列表中，最快的办法是什么？如果没有的话，怎么把它加进去？然后再更新它的"VALUE"（如果字典已经在列表中，"VALUE"会被更新，否则会写入一个特定的值）。

Answer 1

针对你问的问题，如果不改变数据结构，其实没有更快的方法来查找，还是得用循环检查每个元素，并且为每个元素做字典查找。不过，你可以把这个循环的工作交给Python的运行时来处理，而不是用Python的for循环。

不过我还没试过这样做是否真的会更快。

a = [{"ID":1, "VALUE":2},{"ID":2, "VALUE":2},{"ID":3, "VALUE":4}]
id = 2

tmp = filter(lambda d: d['ID']==id, a)

# the filter will either return an empty list, or a list of one item. 
if not tmp:
    tmp = {"ID":id, "VALUE":"default"}
    a.append(tmp)
else:
    tmp = tmp[0]

# tmp is bound to the found/new dictionary

Answer 2

还需要更新找到的键：

d = dict((item['ID'], item['VALUE']) for item in a)

for new_key, new_value in new_items:
    d.setdefault(new_key, 0)
    d[new_key] = new_value

Answer 3

把你的列表转换成字典，然后检查值会更有效率。

d = dict((item['ID'], item['VALUE']) for item in a)
for new_key, new_value in new_items:
    if new_key not in d:
        d[new_key] = new_value

Answer 4

如果可以的话，按照其他回答的建议，把数据转换成字典。但如果你有理由不想改变存储物品的数据结构，这里有一些方法可以尝试：

items = [{"ID":1, "VALUE":2}, {"ID":2, "VALUE":2}, {"ID":3, "VALUE":4}]

def set_value_by_id(id, value):
    # Try to find the item, if it exists
    for item in items:
        if item["ID"] == id:
            break

    # Make and append the item if it doesn't exist
    else:  # Here, `else` means "if the loop terminated not via break"
        item = {"ID": id}
        items.append(id)

    # In either case, set the value
    item["VALUE"] = value

* 我想到的一些合理理由包括：保持物品的顺序，以及允许有相同ID的重复物品。如果你想让字典满足这些要求，可以看看OrderedDict和关于重复键的这个回答。

Answer 5

你应该不要使用列表。而是使用字典，把ID映射到嵌套的字典中：

a = {
    1: {'VALUE': 2, 'foo': 'bar'},
    42: {'VALUE': 45, 'spam': 'eggs'},
}

注意，在嵌套字典中，你不需要包含ID这个键；这样做是多余的。

现在你可以简单地检查一个键是否存在：

if someid in a:
    a[someid]['VALUE'] = newvalue

我假设你的ID键不一定是连续的数字。我还假设你需要存储除了VALUE之外的其他信息；否则，只用一个简单的字典，把ID映射到VALUE就可以了。

字典让你可以在O(1)的时间内（无论字典大小如何，时间都是固定的）通过键来查找值。列表也可以在固定时间内查找元素，但前提是你知道索引。

如果你不知道索引，还得逐个扫描列表，那就需要O(N)的时间，其中N是元素的数量。你需要查看列表中的每一个字典，看看它是否匹配ID，如果ID不存在，那就意味着你得从头到尾搜索一遍。而字典则能在O(1)的时间内告诉你这个键是否存在。