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

[User Picture]From: jurann
2000-12-21 01:09 pm (UTC)

Re: g_list_append

Awesome, Perl rules.

Too true about the math loops, Perl's not very handy for pure-math applications since it treats all variables as strings internally, and math work in Perl requires a little extra process overhead (well, exponentially more depending on the size of your loops) to handle them effectively. Blah. C makes sense, it makes perfect sense.

So what's with this BML stuff LJ uses? I never heard of it until yesterday, when my boss and I looked it up on Google based on the file extensions on LJ. Interesting, I was responsible for a similar project at CourtLink which we termed the "token-parser". That project was 100% Perl, and was damnfast in mod_perl on Apache. But how does BML link into the webserver? Is it an API, module, Perl script, eh? I'm asking to make conversation and because I'm too lazy right now to look it all up. Plus it gives you a chance to be witty and say stuff. =) Thanks!
(Reply) (Parent) (Thread)
[User Picture]From: bradfitz
2000-12-21 05:01 pm (UTC)

Re: g_list_append


Uses Apache's Action directive... running as a set of FastCGI processes now...
(Reply) (Parent) (Thread)