Speed up for loop iterating over two large (10000s) lists

Bit operations will make it much faster, it also allows some expensive operations to be performed only once.

Consider the bellow function:

def is_subnet_of(ip: str, network: str) -> bool:
    def bin_ip(ip: str) -> int:
        return int("".join(map(lambda n: bin(int(n)).replace("0b", "").zfill(8), ip.split("."))), 2)

    net, mask_len = network.split("/")
    mask_len = int(mask_len)

    # Convert ip and net to binary-format
    ip_bin = bin_ip(ip)
    net_bin = bin_ip(net)

    # Build mask
    mask = int(mask_len * '1' + (32 - mask_len) * '0', 2)

    # check (Bit operations are faster)
    return net_bin ^ (mask & ip_bin) == 0

# `is_subnet_of("172.16.56.40", "172.16.56.0/24")` will return True.

It takes 3 steps to decided whether the given ip is in the network:

1. Convert ip and net to binary-format(We need another functionbin_ipto do this job)
2. Build the net mask
3. Do the check：(net ^ (mask & ip))

Even better, step1 and step2 only have to be performed once, which will save us most of the time:

from typing import Tuple


def check_subnet(ip, network_list):
    def bin_ip(ip: str) -> int:
        return int(
            "".join(map(lambda n: bin(int(n)).replace("0b", "").zfill(8), ip.split("."))), 2
        )

    def bin_net(net: str) -> Tuple[int, int]:
        net_ip, mask_len = net.split("/")
        mask_len = int(mask_len)

        net_bin = bin_ip(net_ip)
        mask = int(mask_len * "1" + (32 - mask_len) * "0", 2)

        return net_bin, mask

    def is_subnet_of(ip: int, network: Tuple[int, int]) -> bool:
        return network[0] ^ (network[1] & ip) == 0

    ip = bin_ip(ip)
    networks = tuple(map(bin_net, network_list))

    return tuple(is_subnet_of(ip, network) for network in networks)


# Below are the test section
address_and_networks = {"172.16.56.40": ["172.16.56.0/24", "172.16.56.32/27"]}

result = tuple(check_subnet(ip, network_list) for ip, network_list in address_and_networks.items())

print(result)

If you insist using pandas vectorization operations, then I suggest:

1. Use the bin_ip function I mentioned above to construct matrixs of ip, network, and mask (this step will be O(n) complexity)
2. Use numpy matrix operations (as we all know, pandas actually uses numpy to complete numerical calculations) to calculate the result:result = ((ip & mask) == net.T)

In this way, we will do the O(n) complexity ourselves and leave the O(n^2) part to pandas/numpy vectorization operations.

You are running into O(n^2) complexity.

As you mentioned, len(IP_addresses_list) = 31995 and len(Network_list) = 54099. Currently you are looping all 31995 * 54099 iterations and so causing the slowness.

Just for rough idea the same length loop doing nothing(just a pass statement) took almost 4 mins on online python compiler website. It still took a little over 1 min on my machine.

You need to reduce the iterations happening inside is_subnet_of function.

1. One approach here is break from the loop whenever possible. Do you see any conditions when your result is complete or you no longer need to continue the loop on Network_list (inside is_subnet_of function)?

2. Another approach is reduce your search list (Network_list). Convert it into dictionary with key as first 3 parts of IP address. And in is_subnet_of loop only the shorter list matching first 3 parts of IP address.

For example:

Addresses = ['172.16.56.40','172.16.16.16']
Networks = ['172.16.56.0/24', '172.16.56.32/27']

Convert your Network lists to dictionary for Networks

Networks = ['172.16.56.0/24', '172.16.56.32/27']
network_dict = {}
for n in Networks:
    network_dict.setdefault(n[:n.rfind(".")], []).append(n)
print(network_dict)    

Output:
{'172.16.56': ['172.16.56.0/24', '172.16.56.32/27']}

So your is_subnet_of function will loop through for 172.16.56.40 and no loop for 172.16.16.16

Without the actual data, it is a bit hard to understand what exactly is happening, but some general advise could be:

• DataFrame.merge with how='inner' allows you to relatively fast check which values appear in two separate lists. So if you have one column containing the first three parts of IP addresses and another column containing network IPs (again only XXX.XXX.XXX and not the last part), this could already do the job. You might need to do some checking afterwards, but the number of operations would be much less. merge is vectorized making it a suitable candidate.
• dask.apply could be used on a Dask DataFrame. This could be combined with merge similar to the above-mentioned idea.

Once you provide example data, the suggestions above could be refined.