如何从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具有相同的值。

到目前为止，我所看到的所有问题、答案和讨论在大数据集上都不是很有效。我预计字典会有数百万本。Source和Target都来自托管在不同AWS RDS上的两个不同的数据库(MySql)。我试图找到相同的数据和更新，如果它存在或插入，如果它不是，这就是为什么我需要这个过滤器。

我甚至不确定这是否能在O(n)中实现。如果是这样的话，最优化的方法是什么?也请让我知道性能是否可以提高使用不同的数据结构。

Answer 1

我的解决方案很简单:您可以使用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]

Answer 2

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

如果所有你关心的是是否有任何文档具有相同的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...

如果您能够连接两个数据库并在那里简单地执行此操作(例如使用bs的临时表)，而不是通过Python往返，那么自然会更有效。

编辑:说到临时表，另一个选项是

# 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