Python - nested loop vs 'in' operator resulting in almost double runtime

Question

I come from a C++/Java background and have done a simple implementation of the 'TwoNumberSum' algorithm below. I first implemented it in a more C/Java way using the conventional nested loop then using the 'in' operator. I was expecting both to execute in similar time as 'in' should ideally also iterate through the list which should result in a nested loop and thus somewhere similar execution time but to my surprise the first algorithm takes double the time of the second. Can someone explain what is causing such huge gap in runtime?

I am getting below results on executing the snippet.

Execution Time of Algo 1: 1.023191

Execution Time of Algo 2: 0.46218059999999994

from timeit import timeit

# First Algorithm using simple lists/arrays
code1 = """
def TwoNumberSum(list, sum):

    for i in range(0, len(list)-1):
        for j in range(i+1, len(list)):
            if list[i] + list[j] == sum:
                return [list[i], list[j]]
    return []


TwoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10)
"""
# Second Algorith similar to first using 'in' operator
code2 = """
def TwoNumberSum(list, sum):

    for i in range(0, len(list)-1):
        if sum-list[i] in list[i+1:-1]:
            return [list[i], sum-list[i]]
    return []

TwoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10)
"""

print(f"Execution Time of Algo 1: {timeit(code1, number=100000)}")
print(f"Execution Time of Algo 2: {timeit(code2, number=100000)}")

Answer 1

Python is an interpreted language, and for loops in it are notoriously slow. You probably expect that in is implemented as a for loop, and it is, but it's implemented natively (typically in C), not in Python. There are a lot of functions like that in Python, otherwise the whole language would be impractically slow (at least on the most common interpreter implementation, which is CPython).

If you care about performance in Python, you'll need to do everything you can to avoid Python loops that are executed many times. This is a big part of why NumPy exists and is written largely in C (because operating on vectors and arrays takes forever if you use for loops).

You can also write your own Python modules in C (or C++, or other languages which can expose C callable functions), and this is very useful if you need to accelerate custom loops.

---

Added to address comments from user "Heap Overflow":

If the input list is long, you want an linear time solution. Here is one:

def TwoNumberSum(nums, target):
    seen = set()
    for num in nums:
        complement = target - num
        if complement in seen:
            return num, complement
        seen.add(num)

This is actually slower for the short example lists given in the question, but will be faster for longer lists. But it still contains a for loop in Python, which means it won't be blazing fast. An easy way to fix that is to use Numba, which automatically translates a subset of Python to machine code:

import numba
TwoNumbaSum = numba.njit(TwoNumberSum)

Numba expects NumPy arrays rather than lists, so call it like this:

TwoNumbaSum(np.asarray([3, 5, -4, 8, 11, 1, -1, 6]), 10)

That's it, now you have a linear time solution with no for loops in Python, and you didn't have to write C or C++ code (which would run just as fast but require more effort to develop).