Python3 Vs Python2 List/generator Range Performance

I have this simple function that partitions a list and returns an index i in the list such that elements at indices less that i are smaller than list[i] and elements at indices gre

Solution 1:

As mentioned in the comments, you should be benchmarking with timeit rather than with OS tools.

My guess is the range function is probably performing a little slower in Python 3. In Python 2 it simply returns a list, in Python 3 it returns a range which behave more or less like a generator. I did some benchmarking and this was the result, which may be a hint on what you're experiencing:

python -mtimeit "range(10)"1000000 loops, best of 3: 0.474 usec per loop

python3 -mtimeit "range(10)"1000000 loops, best of 3: 0.59 usec per loop

python -mtimeit "range(100)"1000000 loops, best of 3: 1.1 usec per loop

python3 -mtimeit "range(100)"1000000 loops, best of 3: 0.578 usec per loop

python -mtimeit "range(1000)"100000 loops, best of 3: 11.6 usec per loop

python3 -mtimeit "range(1000)"1000000 loops, best of 3: 0.66 usec per loop

As you can see, when input provided to range is small, it tends to be fast in Python 2. If the input grows, then Python 3's range behave better.

My suggestion: test the code for larger arrays, with a hundred or a thousand elements.

Actually, I went further and test a complete iteration through the elements. The results were totally in favor of Python 2:

python -mtimeit "for i in range(1000):pass"10000 loops, best of 3: 31 usec per loop

python3 -mtimeit "for i in range(1000):pass"10000 loops, best of 3: 45.3 usec per loop

python -mtimeit "for i in range(10000):pass"1000 loops, best of 3: 330 usec per loop

python3 -mtimeit "for i in range(10000):pass"1000 loops, best of 3: 480 usec per loop

My conclusion is that, is probably faster to iterate through a list than through a generator. Although the latter is definitely more efficient regarding memory consumption. This is a classic example of the trade off between speed and memory. Although the speed difference is not that big per se (less than miliseconds). So you should value this and what's better for your program.