Author: Robert Hyatt
Date: 06:41:44 06/20/98
Go up one level in this thread
On June 19, 1998 at 17:41:59, Edward Screven wrote: >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 no... because when N=60,000,000 multiple passes is simply gross in terms of total time. It's easier to go buy a 9 gig or a 23 gig SCSI disk, than to let the book create run forever. IE with 25,000,000 moves, my current book create takes about 30 minutes. Of that, 25 minutes + is spent on reading/parsing the moves, the remainder is sorting/merging. Sorting and merging times won't change, but the parsing time will be multiplied by "K" which is a pretty large "product". IE with K=.5 million, this takes 50 passes at 25 minutes per pass. I'd rather deal with larger space requirements than with 24 hours to build the book.
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.