python - 迭代列表并查看元素是否存在的最快方法？

Question

我有两个比较大的列表，但我的算法 super 慢。

有没有更快的方法来比较列表中的每个元素？实际上，我想找到每个包含 id 的 URL 并解析出 URL 的一部分。

下面的示例有效，只是慢。

# This list actually has ~100k elements
ids_as_string = ["123948", "123094", "123049", "123095"]

# This list actually has ~2.2 million elements
url_list = [
    "http://www.url.com/test/dont-find-me/id_123",
    "http://www.url.com/test/dont-find-this/id_124",
    "http://www.url.com/test/find-this/id_123948",
    "http://www.url.com/test/me-too/id_123094",
    "http://www.url.com/test/not-me/id_1235",
    "http://www.url.com/test/find-me-too/id_123049"
]

addresses = []
counter = 0
for id in ids_as_string:
    for url in url_list:
        if id in url:
            address = url.split("/")[4].replace("-", " ")
            counter += 1
            print(f"Appending {counter}")
            addresses.append(address)
            break

Answer 1

您当前的时间复杂度是 O(NxM)，其中

N = len(ids_as_string)
M = len(url_list)

你可以做的是，将你的数据结构重新组织成 map

{id : url}

例如，将您的“id_123”处理成 map ，查看您的代码，我假设 id 在 URL 中是唯一的。喜欢

lookup_map = {
    '123' : "http://www.url.com/test/dont-find-me/id_123",
    '124' : "http://www.url.com/test/dont-find-this/id_124"
    <so on>
    }

要处理此问题，时间复杂度为 O(N) N 是 url 列表的长度。

只是做

for id in ids_as_string:
   if id in lookup_map:
      <OK>

每个 'if in' 查找都需要 O(1) 因此，总复杂度:O( N) + O(M)