13

According to the blog post here, an any() + generator expression should run quicker than a for loop, and it seems like his reasoning makes sense.

But I've tried to use this method (albeit on some other function), but it seems to take a longer time to run than an explicit for loop.

def with_loop(a, b):
    for x in xrange(1, b):
        if x * a % b == 1: return True
    return False

def with_generator(a, b):
    return any(x * a % b == 1 for x in xrange(1, b))

Basically the code loops through all the numbers from 1 to b to find whether the number a has a modular inverse.

The times I got from running the functions are:

>>> from timeit import Timer as T
>>> T(lambda : with_generator(100, 300)).repeat(number = 100000)
[3.4041796334919923, 3.6303230626526215, 3.6714475531563266]
>>> T(lambda : with_loop(100, 300)).repeat(number = 100000)
[2.1977450660490376, 2.2083902291327604, 2.1905292602997406]
>>> T(lambda : with_generator(101, 300)).repeat(number = 100000)
[1.213779524696747, 1.2228346702509043, 1.2216941170634072]
>>> T(lambda : with_loop(101, 300)).repeat(number = 100000)
[0.7431202233722161, 0.7444361146951906, 0.7525384471628058]

with_generator(100,300) returns False and with_generator(101,300) returns True.

It seems that with_generator always takes a longer time to run than with_loop. Is there any reason for this?

EDIT: Is there any other shorter or more elegant way of rewriting with_loop so that we achieve similar or better performance? Thanks!

Improve this question
1
  • Further to the answer by User below, are there any other "more elegant" or shorter way of writing the code above, but still achieving a similar/better speed as with_loop? Commented Mar 1, 2014 at 23:09

1 Answer 1

Reset to default
7

Context

I think that

any() + generator expression should run quicker than a for loop

means that any does not generate all values but a loop does:

>>> T(lambda : any([x * 101 % 300 == 1 for x in xrange(1, 300)])).repeat(number = 100000)
[5.7612644951345935, 5.742304846931542, 5.746804810873488]
>>> T(lambda : any(x * 101 % 300 == 1 for x in xrange(1, 300))).repeat(number = 100000)
[2.1652204281427814, 2.1640463131248886, 2.164674290446399]

So the quote does not mean that a loop can never achieve the performance of a generator.

The quote means that a loop usually generates all elements and any does not use all of them and a generator only generates the elements that any uses.

Your function with_loop is equivalent to the generator. So you can not expect a different behaviour.

To put it more clearly: any(loop) is slower than any(generator) because the loop generates everything. Your with_loop is equivalent to any(generator) and not to any(loop).

Original Question

>>> profile.run("""T(lambda : with_loop(101, 300)).repeat(number = 100000)""")
         600043 function calls (600040 primitive calls) in 6.133 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        3    0.000    0.000    0.000    0.000 :0(append)
        6    0.000    0.000    0.000    0.000 :0(clock)
        3    0.000    0.000    0.000    0.000 :0(disable)
        3    0.000    0.000    0.000    0.000 :0(enable)
        3    0.000    0.000    0.000    0.000 :0(globals)
        1    0.000    0.000    0.000    0.000 :0(hasattr)
        3    0.000    0.000    0.000    0.000 :0(isenabled)
        2    0.000    0.000    0.000    0.000 :0(isinstance)
        1    0.000    0.000    0.000    0.000 :0(range)
        1    0.005    0.005    0.005    0.005 :0(setprofile)
   300000    0.579    0.000    5.841    0.000 <string>:1(<lambda>)
      4/1    0.000    0.000    6.128    6.128 <string>:1(<module>)
   300000    5.262    0.000    5.262    0.000 <string>:1(with_loop)
        1    0.000    0.000    6.133    6.133 profile:0(T(lambda : with_loop(101, 300)).repeat(number = 100000))
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 timeit.py:121(__init__)
        3    0.000    0.000    0.000    0.000 timeit.py:143(setup)
        3    0.000    0.000    6.128    2.043 timeit.py:178(timeit)
        1    0.000    0.000    6.128    6.128 timeit.py:201(repeat)
        1    0.000    0.000    0.000    0.000 timeit.py:94(_template_func)
        3    0.287    0.096    6.128    2.043 timeit.py:96(inner)


>>> profile.run("""T(lambda : with_generator(101, 300)).repeat(number = 100000)""")
         31500043 function calls (31500040 primitive calls) in 70.531 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   300000   30.898    0.000   67.590    0.000 :0(any)
        3    0.000    0.000    0.000    0.000 :0(append)
        6    0.000    0.000    0.000    0.000 :0(clock)
        3    0.000    0.000    0.000    0.000 :0(disable)
        3    0.000    0.000    0.000    0.000 :0(enable)
        3    0.000    0.000    0.000    0.000 :0(globals)
        1    0.000    0.000    0.000    0.000 :0(hasattr)
        3    0.000    0.000    0.000    0.000 :0(isenabled)
        2    0.000    0.000    0.000    0.000 :0(isinstance)
        1    0.000    0.000    0.000    0.000 :0(range)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
   300000    0.667    0.000   70.222    0.000 <string>:1(<lambda>)
      4/1    0.000    0.000   70.531   70.531 <string>:1(<module>)
   300000    1.629    0.000   69.555    0.000 <string>:6(with_generator)
 30600000   37.027    0.000   37.027    0.000 <string>:7(<genexpr>)
        1    0.000    0.000   70.531   70.531 profile:0(T(lambda : with_generator(101, 300)).repeat(number = 100000))
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.000    0.000 timeit.py:121(__init__)
        3    0.000    0.000    0.000    0.000 timeit.py:143(setup)
        3    0.000    0.000   70.531   23.510 timeit.py:178(timeit)
        1    0.000    0.000   70.531   70.531 timeit.py:201(repeat)
        1    0.000    0.000    0.000    0.000 timeit.py:94(_template_func)
        3    0.309    0.103   70.531   23.510 timeit.py:96(inner)

To call the generator every time, 30600000 times, seems to be much slower than just a for loop.

If you know how many elements exist in a list then you can write this:

l[0] * 101 % 300 == 1 or l[1] * 101 % 300 == 1 or l[2] * 101 % 300 == 1 or ....
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

That makes a lot of sense! I didn't know that any() will call the generator so many times! Anyway, is there any other "more elegant" or shorter way of writing with_loop (using the same idea), like how with_generator is written in a single line? While maintaining/improving the speed, of course.
I think there is no functional way in Python to write this for loop differently and equally fast. If you know the number of elements you coud also use ...[0]... or ...[1]... or ...[2]... But apart from that I think there is no way.
Could you elaborate a little more on the ...[0]... part? I don't really get it. Thanks!
Done. It is in the answer. I really should have written a bit more.
"means that any does not generate all values but a loop does:" By "loop", did you mean list comprehension?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.