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)}")

Numpy basically offers a gateway to C-style iteration. You might find the discussion at this question useful: numpy: function for simultaneous max() and min() — Nathan Chappell
– Nathan Chappell, Commented Feb 16, 2020 at 9:23
Are you aware that Python itself isn't compiled, but most builtins are written in a different language? — MisterMiyagi
– MisterMiyagi, Commented Feb 16, 2020 at 9:28

John Zwinck · Accepted Answer · 2020-02-23 06:34:30Z

5

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).

edited Feb 23, 2020 at 6:34

answered Feb 16, 2020 at 9:16

John Zwinck

252k44 gold badges347 silver badges459 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Jon Clements Over a year ago

You can also see using dis.dis there's less opcodes generated as well...

Kelly Bundy Over a year ago

Is there a linear time NumPy solution for this problem as well? (I don't know much NumPy.)

zvone Over a year ago

@HeapOverflow numpy does not provide linear time solutions to square complexity problems - it just offers vastly faster square time.

Kelly Bundy Over a year ago

@zvone It's not a square complexity problem.

Kelly Bundy Over a year ago

@JohnZwinck Great! I couldn't find anything about hash tables in NumPy, which is why I suspected there might not be a linear solution. So thanks for your assessment of this and for showing how to use Numba (which I had heard of but knew nothing about).

|

Collectives™ on Stack Overflow

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

1 Answer 1

11 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related