Problem 1 – nah

by

Eric wins for the first solution. I think I can beat his execution time by approximately a factor of 2 though (on my computer, after running each a few times). The built-in set data structure also has a built-in union function, which I found in chapter 5 of the tutorial. So, my go at the problem is:

 from time import time

 t = time()

 threes = set(3*n for n in range(1,1000/3 + 1)) # multiples of 3
 fives = set(5*n for n in range(1,1000/5)) # multiples of 5

 either = threes | fives # set union

 print sum(either), "in", time()-t, "sec"

I also included the code to calculate execution time that I learned about from the blog “Numerical Recipes“.

Anybody wanna do up a more general solution? Maybe see how the different approaches scale to numbers higher than 1000, or with other choices of divisors (allowing more of them, perhaps)?

Have another approach? How does it compare, speed-wise?

Just a side-note: I also took my solution and put it all into one line, and avoided saving the sets as variables. This technique seemed to take, on average, just slightly longer to run.

Tags: ,

7 Responses to “Problem 1 – nah”

  1. Jaime Says:

    Thanks for the link… I have moved the blog to wordpress, by the way… I recently found myself that it is better to use clock rather than time, as it gives higher precision. I have also started doing a t = time.clock() - t before the print statement, to avoid counting the time to output the first characters, which for faster codes can be very significant. Also, it is considered more pythonic to do imports like this:

    import time
    ...
    t = time.clock()
    ...
    t = t - time.clock()
    print whatever,"in",t,"sec."
    

    Having been there, seeing you progress down the problem list is going to be a lot of fun... You will find out sooner than later that the brute force approaches that work fine for the first few, eventually fail miserably. And most of the time the failure is due to the math not being sophisticated enough, not the programming. The generalization you propose is a great playground to start changing the mindset, and come up with an ultra-fast solution, which will prove useful later on. hint...

    • sumidiot Says:

      According to this page, time.clock() works better on Windows machines, but not Linux. Or something like that. When I switched my code to time.clock(), I got 0.0, or sometimes 0.01 seconds, whereas I was getting things like 0.0004 using time.time().

      Also, wouldn’t doing “t = t – time.clock()” return a negative time?

  2. Jaime Says:

    Also, as python notes…

    …lthough the insidious bug usually goes the other way, it is not very safe to count on the division of to integers to return an integer. As a matter of fact 1000/3 yields a float in python 3.0, so it is better to either cast the result as int(1000/3), or to use the integer division operator, 1000//3. If you do a from __future__ import division at the very beginning of your program, you can force 3.0 behavior on earlier python versions.

    …unless you want to create a list and store it for later, use xrange instead of range. The latter has to generate the full list before passing it to the set constructor, while the former yields the elements one at a time, so it is faster and has a smaller memory footprint.

    …take advantage of all of range parameters. You can skip costly multiplications by asking for xrange(1,1000,3) instead of 3*n for n in range(1,1000/3 + 1).

    • sumidiot Says:

      Speaking of memory footprints, any suggestions for how to go about comparing those for various scripts? I tried the “time” command, and can see some differences, but perhaps these programs are just too small to notice appreciable differences.

  3. Jaime Says:

    I meant xrange(3,1001,3)

  4. sumidiot Says:

    Thanks, Jaime, for all the great suggestions!

    After working on this solution last night, and playing around with some things to change, and see their affect on performance, I struck on the more mathematical solution. And then I started wondering how easy it would be to write a generalization of that solution, allowing for more divisors… I didn’t work on it carefully, but it kept me up anyway. For now I think I’ll hope some of our other authors carry it out 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: