如何从 O(n) 中的两个字典列表中搜索？

Question

请在标记为重复之前阅读。我知道执行此操作的方法，并且我已阅读有关同一主题的其他堆栈问题，但所有解决方案都在 O(n²).

中

假设我们必须像这样列出字典。

source = [
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
]
target = [
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
    {'a': 'value', 'b': 'value', 'c': 'value'},
]

我想在这里做的是从键 b 上过滤来自源的字典，它与来自目标的任何字典的键 b 具有相同的值。

到目前为止，我所看到的所有问题、答案和讨论在大型数据集上都不是很有效。我期望字典数以百万计。源和目标都来自托管在不同 AWS RDS 上的两个不同数据库 (MySql)。我正在尝试查找相同的数据并在存在时进行更新或在不存在时进行插入，这就是我需要此过滤器的原因。

我什至不确定这是否可以在 O(n) 中实现。如果是这种情况，最优化的方法是什么。如果使用不同的数据结构可以提高性能，请告诉我。

Answer 1

这绝对不是最佳数据格式。

如果您只关心是否有任何文档具有相同的b，则没有理由获取完整记录。相反（伪代码），您可以获得您关心的不同 b 值的 set。

target_bs = set(get_first_column("SELECT DISTINCT b FROM target"))

然后你可以做（同样，就查询而言是伪代码）

for record in get_records("SELECT * FROM source"):
    if record["b"] not in target_bs:  # efficient set lookup
        # ... insert...

当然，如果您能够连接两个数据库并在那里简单地执行此操作（例如临时 table 的 bs）而不是通过 Python 进行往返，那么效率会更高。

编辑：说到临时 tables，另一种选择是

# Get list of unique Bs from first database
existing_bs = set(get_first_column(db1, "SELECT DISTINCT b FROM target"))
# Create and populate a temporary table for them in the second database
execute(db2, "CREATE TEMPORARY TABLE bs (b SOMEDATATYPE PRIMARY KEY)")
insert_many(db2, "INSERT INTO bs (b) VALUES (?)", target_bs)

# Query all records where there is no matching `b` in that temporary table
for record in get_records(db2, "SELECT * FROM source LEFT JOIN bs ON (source.b = bs.b) WHERE bs.b IS NULL"):
   # do something with the record

Answer 2

我的解决方案非常简单：您可以使用 set 来存储源列表中 'b' 键的所有值。然后您可以从源中过滤该集合中的所有值。

结果复杂度为 O(2n)，即 O(n)。

source = [
    {'a': '1', 'b': 'ad', 'c': 'value'},
    {'a': '2', 'b': 'xs', 'c': 'value'},
    {'a': '3', 'b': '3sda', 'c': 'value'},
    {'a': '4', 'b': 'va', 'c': 'value'},
    {'a': '5', 'b': 'gnghng', 'c': 'value'},
    {'a': '6', 'b': 'nhgnhg', 'c': 'value'},
    {'a': '7', 'b': 'nhnhg', 'c': 'value'},
]
target = [
    {'a': '10', 'b': 'ad', 'c': 'value'},
    {'a': '13', 'b': 'adadas', 'c': 'value'},
    {'a': '16', 'b': 'asda', 'c': 'value'},
    {'a': '18', 'b': 'xs', 'c': 'value'},
    {'a': '21', 'b': 'value', 'c': 'value'},
    {'a': '24', 'b': 'va', 'c': 'value'},
    {'a': '27', 'b': 'sads', 'c': 'value'},
]

dict_source: set = set(item['b'] for item in source)
filtered_from_source: list = [item for item in target if item['b'] in dict_source]

如何从 O(n) 中的两个字典列表中搜索？

How to search from two list of dict in O(n)?

python

algorithm

search

time-complexity

data-structures