CODEWITHSUNDEEP
python
josinalvo
josinalvo

Reputation: 1488

is this python benchmark useful?

I recently tried to run an Project Euler problem in python. It was my belief that it would do something like 100^5 steps.

After seeing that my solution wat taking too long (it is supposed to run in under a minute) I asked myself if any python program that ran this many steps would be viable (under a minute)

so, I designed a foolish little test

def fun():
  l=range(1,100)
  for x in l:
     for y in l:
        for k in l:
           for n in l:
               for h in l:
                  s=1

>>> t = timeit.Timer('demorado.fun()','import demorado')
>>> t.timeit(1)
1202.484529018402
>>>

does is make sense ? Does it prove that any program with this many steps (in this case, I guess there are 2*(100^5)) always demands some 20 minutes ?

Upvotes: 1

Views: 147

Answers (5)

npnmodp
npnmodp

Reputation: 1242

Try pass instead of s=1 in the inner loop.

Also, use numpy.nditer with "external_loop" option, or write the loops in Cython if loops turn out to be your bottleneck.

Upvotes: 0

Oleg2718281828
Oleg2718281828

Reputation: 1039

Does it prove that any program with this many steps always demands some 20 minutes ?

Depends on your definition of "step". Here is code that requires about 99^5 floating point operations, but runs in about 1 second:

import numpy as np
a = np.zeros(shape=(1681, 1681), dtype=np.float32) # 1681 x 1681 matrix
b = np.dot(a, a) # matrix product

Upvotes: 1

Madison May
Madison May

Reputation: 2763

For python it's probably a good estimate. Using numpy or C++ extensions might speed up your Project Euler code, but remember all problems on Project Euler are designed to be solvable in <1 min. It's very unlikely you are required to run 100^5 operations in order to arrive at the correct solution. I'd try to approach the problem from a different angle if I were you.

Upvotes: 1

Ali Afshar
Ali Afshar

Reputation: 41657

It is a reasonable assumption, though I am not sure it is doing what you want. In real life this might be closer:

for i in xrange(100 ** 5): pass

Upvotes: 2

Tim Pietzcker
Tim Pietzcker

Reputation: 336468

Project Euler problems are not supposed to run in under a minute because your programming language is fast enough, but because there exists a solution that's cleverer than just brute force.

But in your case, yes, you'll get a function that loops 99^5 times (not 100^5 because range(1,100) is 1, 2, ..., 99)...

Upvotes: 2

Related Questions