Sorry I did not have time to look at your code, but here a few quick hints:
1) Before any optimization make sure that your code works 100% correctly. This means testing extensively and writing tests that you can use as you start optimizing to make sure nothing breaks in the process. You might get into big trouble if there is a bug you find after doing lots of optimizations. 2) Learn how to profile your code. I don't work in C so unfortunately I can't give you specific directions. But this is always the first step in optimizing a large project. When you can see exactly where your bottlenecks are it is 100 times easier and more efficient to optimize. Without profiling you might find yourself spending a week on an optimization that ends up giving you only 1% speedup. The main optimization for me was squeezing every little bit out of random number generation. This meant using a third party random number generator in java (because the built in one is slow and also not really pseudorandom anyway) and using various other tricks... 3) Think very carefully about data structures and algorithms at a high level. I tried to simplify my board structure and my structure for representing strings as much as possible and this also generated a lot of speedup. As the last poster mentioned, if you are picking a random intersection and rejecting the ones that are occupied until you have filled the board this will take a lot longer than mainting a list of empty intersections and only sampling from these. More specifically, only sampling from empty intersections will take O(n) to fill the board, while sampling with replacement and rejecting occupied intersections will take O(nlogn) which is actually pretty bad since a lot of time is spent deciding where to play as it is. I hope that helps! On Nov 12, 2007 2:45 PM, Heikki Levanto <[EMAIL PROTECTED]> wrote: > On Mon, Nov 12, 2007 at 06:10:21PM +0100, Petr Baudis wrote: > > Sorry, it's http://repo.or.cz/w/zzgo.git > > I've had a quick look at it, and have already two comments: > > 1) You seem to use struct {x,y} for coordinates all the way. I think using a > single int is usually faster. I was involved with GNU Go when we made that > change, and it did make sense. Gives some speed, but costs a bit of work, and > some readability. > > 2) It looks like your montecarlo algorithm tries to pick random points and > discards those that are not empty or legal to play in. It ought to be faster > to make a list of legal points in advance (or at least empty ones), and pick > from that list. This list can be maintained incrementally during the MC > simulation. > > > Still, I like your style, and may yet decide to take advantage of your > library instead of LibEGO at least in some of my experiments. > > - Heikki > > -- > Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk > > _______________________________________________ > > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
