?

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: jaebird
2000-12-17 08:11 pm (UTC)
OH MY GOD ITS THAT BOOK ALL OVER AGAIN. -_- That reminds me so much of Wuthering Heights and a few others its not even funny O.o *just stares at the page attempting almost to make it out chewing on a piece of chocolate nearly missing her mouth* ..Jae..
(Reply) (Thread)
[User Picture]From: bradfitz
2000-12-17 08:30 pm (UTC)

Re:

I read Wuthering Heights but I fail to see how it's related to this post at all ... are you on crack?
(Reply) (Parent) (Thread)
[User Picture]From: jaebird
2000-12-17 08:35 pm (UTC)

O.o

NO :S *looks at her toes sadly* did you like the book? I was reading to close to it when i tried to read it for fun.. but there were a lot of mishaps in it that I couldnt configure so.. O.o your entry could fit right into that book.. I would read over it and whoosh just think it was an odd turning point I didnt understand..Jae.. :(
(Reply) (Parent) (Thread)
[User Picture]From: visions
2000-12-17 08:56 pm (UTC)

Re: O.o

you are an intriguing individual... either that.. or you have very good crack.
(Reply) (Parent) (Thread)
[User Picture]From: jaebird
2000-12-17 09:01 pm (UTC)

O.O *blinks*

eh thanks You eh have nice boxers ^_^ hee hee *builds lego boxers* hehe slightly hard O.o *is innocent mind you* There are crazy people on my IM ^_^ I want to be one of those crazy librarians thanks though ^_^ *chews on a gummi gazing at the clock then at the homework she was suppose to do and sighs* *pushes a little pig figurine around on her desk* Nighters.. Jae
(Reply) (Parent) (Thread)
From: (Anonymous)
2000-12-17 09:25 pm (UTC)

Re: O.O *blinks*

*inhales* ^_^ So why do *exhales* -_- you *inhales* O.o want to be like a crazy librarian? *exhales* O.O

-_-
(Reply) (Parent) (Thread)
[User Picture]From: jaebird
2000-12-17 09:28 pm (UTC)

eh okay O.o Rubabdubdub

Cus ^_^ They are funners than most old foggies eh.. do you need cpr.. cus eh I don't think I know you well enough to give it to you.. are your boxers on too tight? O.o cus you know that can cause problems.. -_- Joke: who is the most popular guy in the nudist colony?.. Jae
(Reply) (Parent) (Thread)
[User Picture]From: visions
2000-12-17 09:30 pm (UTC)

Re: O.O *blinks*

hehe. umm... thanks... i think. :)

you make me laugh... hehe.

anyway, my IM handle is liquidst.. ill harass you online if you IM me. :)
(Reply) (Parent) (Thread)
[User Picture]From: jaebird
2000-12-18 04:27 am (UTC)

o.O

harrassment...always fun ^_^ Oreos are cool reminds me of sex.. not that I would know.. I am SO INNONCENT.. *smiles angelically*.. Jae
(Reply) (Parent) (Thread)
From: evan
2000-12-17 09:59 pm (UTC)

g_list_append

Of course it's O(n).
The GList type is just something like (I'm making this up)
{
GList *prev, *next;
gpointer data;
}

(as you'd expect)

so appending to the list requires finding the tail.

Two solutions:
1) prepend (if it will work in your situation)
or
2) store a "tail" pointer, then g_list_append() directly to the tail.
list = g_list_append(tail, data);
tail = tail->next;


(Reply) (Thread)
[User Picture]From: bradfitz
2000-12-17 10:06 pm (UTC)

Re: g_list_append

I know it's easy... thing is: it's boring!

The whole reason I used glib rather than doing this manually was because I thought glib provided things like this. I assumed glib provided a List* and ListNode*, where the List* knew things like the head and tail.
(Reply) (Parent) (Thread)
[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)
[User Picture]From: bradfitz
2000-12-17 10:11 pm (UTC)

Re: g_list_append

Another reason I don't like g_list_append's behavior:

It makes it too easy to do something stupid.

What if people didn't know anything about the underlying data structure and assumed that somehow glib must be doing something smart?
(Reply) (Parent) (Thread)
From: evan
2000-12-17 10:20 pm (UTC)

Re: g_list_append

If you know enough to be concerned with the performance of g_list_append(), you'd better understand the concept of a linked list. :P
(Reply) (Parent) (Thread)
[User Picture]From: jurann
2000-12-20 03:37 pm (UTC)

Re: g_list_append

Word of advice from the field: "Standard Library" means "Made for Idiots with Room For Mistakes". In the industry, if you need some library to work a certain way, it's usually not very tough to write it in a simple, efficient manner, just make sure there are no possibilities of data error. Error checking is the biggest cause for slowdown in stdlibs... And they wouldn't really be standard without it. General rule of thumb: if you need it done right, right away, best do it yourself unless you know of a library that does it EXACTLY the way you want already. Since that's a rarity, it's best to just optimize your own routines for getting stuff done. Yeah, it's boring, yeah, it's simplistic, but yeah, it's damn effective.

BTW - Sorry to hear about your trouble with Perl, the program shouldn't be running that slowly IMHO. Worst case scenario I've seen Perl run at about 50% the speed of a compiled C program unless the Perl code was not written with speed optimization in mind, or some dynamic of the Perl interpreter was left out of (or left in) the coding. Making fast Perl code pretty much requires sleeping with the demon, but she's good in bed and you'll be happy to come back to her. ;) I do almost all of my development in Perl these days, it's just one of the best trade-offs of development speed to execution speed. And you can do some loopy stuff with Perl! Anyway, I'm praising too much, so I'll go now. Good luck with your project. =)
(Reply) (Parent) (Thread)
[User Picture]From: bradfitz
2000-12-20 11:37 pm (UTC)

Re: g_list_append

I do 99.4% of my development in Perl lately too....

The particular program I was writing I knew Perl would suck at... it was just math in loops.

(Reply) (Parent) (Thread)
[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

http://www.bradfitz.com/bml/

Uses Apache's Action directive... running as a set of FastCGI processes now...
(Reply) (Parent) (Thread)
[User Picture]From: jaebird
2000-12-18 05:47 am (UTC)

Music is but a simple melody

UGH I am glad someone atleast knows what they are talking about... O.o
(Reply) (Thread)