根据大量的字典更新字典

Question

我有一个巨大的（大约 350k 个元素）字典列表：

lst = [
{'data': 'xxx', 'id': 1456},
{'data': 'yyy', 'id': 24234},
{'data': 'zzz', 'id': 3222},
{'data': 'foo', 'id': 1789},
]

另一方面，我收到了一个又一个缺失值的字典（大约 550k）（不是每个字典都缺失这个值），我需要更新它们：

example_dict = {'key': 'x', 'key2': 'y', 'id': 1456, 'data': None}

收件人：

example_dict = {'key': 'x', 'key2': 'y', 'id': 1456, 'data': 'xxx'}

我需要获取每个字典并在列表中搜索以匹配 'id' 并更新 'data'。这样做需要很长时间才能处理：

if example_dict['data'] is None:
    for row in lst:
        if row['id'] == example_dict['id']:
            example_dict['data'] = row['data']

有没有办法构建一个结构化的分块数据，例如10k 值并告诉传入的字典在哪个块中搜索 'id'？或者任何其他优化方法？感谢任何帮助，保重。

Answer 1

使用字典而不是线性搜索列表。

第一个重要的优化是通过 lst 删除线性搜索，方法是构建一个索引为 id 并指向行

的字典

例如，如果您有足够的 RAM 来保存内存中的所有行，这将比您的代码快很多：

row_dict = {row['id']: row for row in lst}

if example_dict['data'] is None:
    if example_dict['id'] in row_dict:
        example_dict['data'] = row_dict[example_dict['id']]['data']

无论您是按 10k 块处理行还是一次性处理所有行，此改进都与您相关，因为字典查找时间是恒定的，而不是 lst 的线性大小。

制作您自己的分块过程

接下来你问“有没有办法构建一个结构化的分块数据......”。是的，一点没错。如果数据太大而无法放入内存，请编写一个 first pass 函数，将基于 id 的输入分成几个临时文件。如果顺序不相关，它们可以基于 ID 的最后两位数字，或者如果您愿意，它们可以基于 ID 的范围。对行列表和您收到的字典执行此操作，然后使用上面的代码一次处理每个 list/dict 相同 ID 的文件对。

不过，如果您必须保留接收词典的顺序，则此方法将更难实施。

Answer 2

lst 列表的一些预处理可能会有很大帮助。例如。将该字典列表转换为字典，其中 id 将是一个键。

准确的把lst改成这样的结构：

lst = {
    '1456': 'xxx',
    '24234': 'yyy',
    '3222': 'zzz',
    ...
}

然后当尝试检查 example_dict 中的 data 属性时，只需直接访问 lst 中的 id 键，如下所示：

if example_dict['data'] is None:
    example_dict['data'] = lst.get(example_dict['id'])

它应该将时间复杂度从二次复杂度 (n*n) 降低到线性复杂度 (n)。

Answer 3

尝试从 lst 创建散列 table（在 Python 中 dict）以加速基于 'id' 的查找：

        lst = [
            {'data': 'xxx', 'id': 1456},
            {'data': 'yyy', 'id': 24234},
            {'data': 'zzz', 'id': 3222},
            {'data': 'foo', 'id': 1789},
            ]        
        example_dict = {'key': 'x', 'key2': 'y', 'id': 1456, 'data': None}        
        dct ={row['id'] : row for row in lst}
        if example_dict['data'] is None:
            example_dict['data'] = dct[example_dict['id']]['data']
        print(example_dict)

示例输出：

{'key': 'x', 'key2': 'y', 'id': 1456, 'data': 'xxx'}

根据大量的字典更新字典

Updating dictionaries based on huge list of dicts

python

dictionary

etl

data-processing

python-3.x

使用字典而不是线性搜索列表。

制作您自己的分块过程