Question: I've got two large lists I'm comparing, but my algorithm is *super* slow.

Is there a faster way to compare each element of the list? Effectively, I want to find each URL where the id is present and parse out one segment of the URL.

The example below works, it just works *slow*.

```
# 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: 
Your current time complexity is ***O(NxM)*** where

*N = len(ids\_as\_string )  

M = len(url\_list )*

What you can do is, re-organise your data-structure in to maps

```
{id : url}

```

Example, process your 'id\_123' into map, looking at your code, I assume id's are unique in URLs.
like 

```
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>
    }

```

To process this, time complexity is ***O(N)*** N is length of url list.

the just do 

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

```

each *'if in'* look-up takes ***O(1)*** so, Total complexity: ***O(N) + O(M)***
Turn one of your two lists into a `set` and then use the `in` operator for a fast O(1) lookup, turning your O(N\*M) nested loop into a single O(N) `set` conversion and O(M) loop.

Note that this way your `if id in url` check does not work, but if the `id` is always in the same position you can extract it and then check whether it's in the set of IDs.

```
>>> id_set = set(ids_as_string)
>>> [url for url in url_list if url.split("_")[-1] in id_set]
['http://www.url.com/test/find-this/id_123948',
 'http://www.url.com/test/me-too/id_123094',
 'http://www.url.com/test/find-me-too/id_123049']

```