Author: Edward Screven
Date: 14:41:59 06/19/98
Go up one level in this thread
On June 19, 1998 at 17:09:29, Robert Hyatt wrote: >This turns an O(N) operation (cpu complexity) and O(2N) operation (Space) >into an O(N^2) (complexity) to get to O(N) space. I don't like the trade >off. I can build a 350,000 game book with 25,000,000 moves, in under 40 >minutes on my P6, and under 10 minutes on a good alpha. The factor of two >in space isn't worth the factor of N in speed, because N is *big*. O(N) --> O(N**2)? no. i'll assume by O(N) time you mean expected time given pgn input of reasonable size, since the sort is O(N log N), but the overall process is dominated by scanning the input for typical inputs. partitioning will go from O(N) --> O(N * K) time and O(N) --> O(N / K) space, where K is the constant number of partitions you choose. you should choose K so that you just enough space to complete the operation. for example, if you require 500M of temporary space to build the book, but you only have 200M free, then you would choose K == 3, which would take about three times longer than if you had enough free disk space. whether or not it's worthwhile depends on what K you need to use and how badly you want the book. when super-wall.pgn becomes available, wouldn't you be killing to run with K=3 or K=4 if it meant you could actually build a book out of it? - edward
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.