Brad Fitzpatrick (brad) wrote,
Brad Fitzpatrick

bowling statistics

I knew this program I'm writing would take a ton of CPU, but I guess I didn't think realize how much it. What I'm doing is calculating bowling statistics over all possible games. Last time I went bowling I got it in my head to do this and I can't stop thinking about what the three-dimensional graph of [x=balls thrown, y=score, z=occurences] must look like.

I wrote it in Perl initially but it was way too slow so I rewrote it in C. In C it takes 43 seconds to compute the incredible small subset of the larger problem... in Perl that same subset takes 4 minutes and 10 seconds. Stupid Perl. :-)

If I disable the prints to stdout, the time of the C program drops to 10 seconds. On Kenny (the P3-933) it runs in 4 seconds.

Solving the entire problem is going to take approximately (50**6) times longer because right now I'm running it assuming only 4 frame game.

I need to think of way of a new way to solve the problem by breaking the game up into separate parts which don't interfere with the rest of the game (i.e. sets of open frames following an open frame).

Or, I need to make the program start at arbitrary points and run it on all four computers in here while I sleep. That's kinda hard to do right now because of how it's written (using recursion) ... An iterative solution might be faster, and more easily parallelizable, but it's harder to think about.

I guess I'll graph what I have so far, and then think about this later.

Also, I decided to use glib for the C port, but I don't like it much ... g_list_append appears to be O(n). But then again, so is strcat .... :-/
Tags: perl, tech

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.