Algorithm of `all` function in python

Python
1

I was solving a question which required to check if the number is prime.
I solved it using the regular for loop, by checking if the number has a factor…
In the solutions, some people solved it using the all function.
I decided to check the time different between these methods.
By using newly learned decorators I defined following functions and the decorator

import time
import functools
# Time Decorator
def time_wrapper(func):
    @functools.wraps(func)
    def timer(*args, **kwargs):
        start = time.perf_counter()
        result = func(*args, **kwargs)
        print(f"Time for {func.__name__!r} using {args}: {time.perf_counter()-start:.6f} s")
        return result
    return timer

@time_wrapper
def loop_all_prime(n):
    return all(n%i for i in range(2, int(n**.5)+1))

@time_wrapper
def loop_regular_prime(n):
    for i in range(2, int(n**.5)+1):
        if not n%i: return False
    return True

To test this, I used the random module to generate random number between 10000 and 100000 as follow

# Generate Random number to test
import random
for i in range(10):
    num = random.randint(10**4, 10**5)
    loop_all_prime(num)
    loop_regular_prime(num)
    print('-'*50)

Here’s the response that I got

image
image638×710 28.7 KB

It is clear from above snap that in most of the cases, regular for loop, with break statement is more efficient than the built-in all. maybe it’s more effective for another operation or another scenario.

It’ll be better if someone explain a simplified algorithm for the all function or elaborate about it’s efficiency.
Thank you!:grinning_face_with_smiling_eyes:

2

Generally all function internally should be doing something similar to your regular function - https://docs.python.org/3.8/library/functions.html#all ; My guess is that the main difference comes from the additional function call (call of all) and fact that n%i for i in range(2, int(n**.5)+1) is actually additional generator comprehension. Both of which would give some overhead comparing to bare for loop.

If you had list for example

numbers = [num % n for n in range(2, int(num**.5)+1)]

and then pass it into slightly changed functions using all and loop then results would be more similar. Although obviously worse than both versions in your example.

Keep also in mind that in python not everything is about pure performance, as Zen of Python guides that readability counts and beautiful is better than ugly (code). :wink:

1 Like
3

Now, it makes sense. To create a generator, we’ve to iterate through all the elements in the list(or range),
but in case of regular for loop, we’re returning as soon as we found that the number is not prime.

4

Actually generator doesn’t produce whole list and doesn’t need to iterate through all elements first. That wouldn’t be even possible here, because range function is also a generator. Returning one element at the time, only when it’s needed. You might be thinking about normal list comprehension.
Realization that there are two generators here leads to something that may be even more surprising - generators can be chained together and will process one element at the time through the chain.

5

I thought it as a list comprehension.

6

Right, it would be list comprehension if there would be also square brackets.

[n%i for i in range(2, int(n**.5)+1)]

Change from it to generator comprehension / expression can take as little as just changing the parentheses type, or sometimes (like in your example), additional parentheses can be omitted.

(n%i for i in range(2, int(n**.5)+1))
7

and this is the reason why generators are faster than the list comprehension.
am I right?

8

If you are asking in the context of producing one element at the time, just when that’s needed, versus making the whole list when that’s not even needed, then yes. It’s also more memory efficient.

1 Like