Why these two approaches for computing sum produce different run-time

user_17435112 0
Viewed 92

Why these two approaches for computing sum produce different run-time? (5 times check) Both codes run on : https://colab.research.google.com

from timeit import repeat

setup = 'a = [1] * 10_000_000'

expressions = [
    'sum(x % 2 for x in a)',
    'sum(True for x in a if x % 2)',
]

for expression in expressions:
    times = sorted(repeat(expression, setup, number=1))
    print(*('%.2f ' % t for t in times), expression)

result:

0.65  0.65  0.65  0.65  0.66  sum(x % 2 for x in a)
1.03  1.04  1.04  1.05  1.06  sum(True for x in a if x % 2)

Another check but different result:

...

setup = 'a = [0] * 10_000_000'

...

Result:

0.66  0.66  0.66  0.67  1.45  sum(x % 2 for x in a)
0.43  0.43  0.44  0.45  0.46  sum(True for x in a if x % 2)

Third check

...

setup = 'a = range(10**7)'

...

Result:

0.75  0.75  0.76  0.77  0.78  sum(x % 2 for x in a)
0.81  0.82  0.82  0.82  0.84  sum(True for x in a if x % 2)
list sum optimization python performance
2 Answers

For clarity, let's denote:

Expression 1: sum(x % 2 for x in a)

Expression 2: sum(True for x in a if x % 2)

Check 1: a = [1] * 10_000_000

Check 2: a = [0] * 10_000_000

Check 3: a = range(10**7)

Now, in both checks, Expression 1 involves calculating 10 million modulus values and summing all 10 million of them. That takes pretty much the same amount of time whether the modulus is always 1 (Check 1) or always 0 (Check 0).

Expression 2 works a bit differently. It calculates 10 million modulus values, compares them to zero, and sums a series that has entries only for the non-zero values.

For Check 1, this means Expression 2 has 10 million comparisons to do, and 10 million values to sum. That's the same sum as for Expression 1 in Check 1, but with the added work of comparisons. So no surprise that for Check 1, Expression 2 is slower than Expression 1.

For Check 2, Expression 2 has 10 million comparisons to do again, but those comparisons all find that the modulus is zero. Therefore there is nothing for the summation step to do! It turns out that compared for Check 2, the time that Expression 2 spends on comparisons is less than the saving it makes by not having to sum everything. So for check 2, Expression 2 is faster than Expression 1.

(Edited after the question was updated with check 3)

For Check 3, Expression 1 once again just sums 10 million items. Expression 2 does 10 million comparisons and sums 5 million items. Since Expression 2 turns out slightly slower, we can see that the time saved by removing 5 million items from the sum is a little bit less than the time taken in doing 10 million comparisons.

user_7650910

If you run the tests in a hardware, the runtime of different results can be related to many circumstances, here are some examples:

  • processes active
  • hardware
  • temperature
  • cooling system
  • order of evaluation

But just in the part of the logic, the second expression is slower because the condition is evaluated

And, a conditional generator comprehension gets evaluated slower than a normal comprehension. Furthermore timing something in python is extremely relative to different things from the software to the hardware even to internal optimization.

user_132857070
Related