?

Log in

No account? Create an account
brad's life [entries|archive|friends|userinfo]
Brad Fitzpatrick

[ website | bradfitz.com ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

bowling statistics [Dec. 17th, 2000|07:51 pm]
Brad Fitzpatrick
[Tags|, ]

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 .... :-/
LinkReply

Comments:
[User Picture]From: visions
2000-12-18 11:44 am (UTC)

Re: g_list_append

it seems rare to find a standard library that actually does the "best" thing.
(Reply) (Parent) (Thread)
[User Picture]From: bradfitz
2000-12-18 12:50 pm (UTC)

Re: g_list_append

word to that.
(Reply) (Parent) (Thread)
[User Picture]From: jaebird
2000-12-21 02:44 pm (UTC)
*sticks her tongue out at him too*
(Reply) (Parent) (Thread)
[User Picture]From: jaebird
2000-12-21 02:43 pm (UTC)

O.O

*Just sticks her tongue out*
(Reply) (Parent) (Thread)