python - 字典对象搜索

Question

我已经从 REST API 获取了超过 8000 条记录。现在我需要搜索这个数据集。

我的数据集是这样的:

  data = {
        key: [ 
              {name:'foo1', 'age':22},
              {name:'foo2', 'age':23},
        ]}

当我使用这段代码时，我需要一种新的 python 搜索技术或算法，而不需要 O(n) 的复杂度；

for data in datas:
  if data["name"] == "foo1":
     calculate_func(data)

如何优化搜索算法的复杂性？

Answer 1

如果您的数据集与您发布的完全一样，那么您可以创建一个包含{key:value} 的字典，其中key 是名称，value 将是年龄。像这样 -

dict = {
'foo1': 22, 
'foo2': 23
}

然后如果您可以直接使用搜索词来访问与该名称对应的值。喜欢 -

age = dict[searchTermName]

通过这种方式，您只需要 O(n) 的时间来准备数据集，但对于每次搜索，您将需要 O(1) 的时间。

现在，如果您的数据集比这更复杂 - 您可以使用 prefix trie .这将是最有效的方法之一。在每次搜索中，最坏情况下的时间复杂度将为 O(search_term_length)。尽管它也有初始化成本。但这只是一次成本(O(n * key_length))。