Author: Daniel Clausen
Date: 06:20:44 11/08/02
Go up one level in this thread
On November 08, 2002 at 07:40:45, Tony Werten wrote: >On November 08, 2002 at 04:14:34, Daniel Clausen wrote: > >>On November 07, 2002 at 18:03:52, Ron Murawski wrote: >> >>>On November 07, 2002 at 16:57:04, Martin Bauer wrote: >>> >>>>On November 07, 2002 at 16:08:49, Tony Werten wrote: >>>> >>>>>Somewhere from 8Mb you will get a 99,9% hitrate after a few seconds. >>>> >>>>Memory usage depends on waht I am storing, can you tell me a number of Hashtable >>>>entries? >>>> >>> >>>One less than a power of two (aka Mesenne number) entries is best, a prime >>>number of entries is supposed to be acceptable. >> >>Shouldn't it be the opposite? "prime number is best but 2^n-1 is acceptable"? > >Don't think so. With a big table, collisions are not probable so no real >difference there. But: 2^n-1 can be calculated with a cheap AND and prime most >be done with an expensive mod. I agree that "prime" or "2^n-1" is not a big difference when it comes to computer chess hashtables. The reason is that in CC you typically don't probe many times (maybe up to 4). In other areas it's different though, and then the probing algorithm is good when it ensures that the probe sequence probes all possible array position eventually. (like with 'quadratic probing' and #slots being prime) That's not the case in computer chess HTs though. In summary, I think that a prime number for #slots would still be a lil better, but the fact the it's much cheaper to calculate the slot number (with the AND 2^n "trick") outweighs that in CC. Sargon
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.