Worst case on "classical" hash is lineal. Never happend, but on heavy loaded hashes, you can get lineal times which is bad, very bad.
Using Cuckoo method, with a hash table the double the size of the expected items, it ensures you that the collision is almost null. It seems strange the "loop infinite", but the probability decreases with a power of two on every iteration. Think about it. (every item could be in two positions .... ) Also, accessing to hash on classic hashes, could be lineal, not only write but read also could be lineal. On Cuckoo read is _strict_ constant. About the transposition table accessing time. Yes, I think the same but I have some doubts about IO and "heavy" access to deep in the game tree tables. --- Mark Boon <[EMAIL PROTECTED]> escribió: > This seems to be only a small variation of hashing > methods I was > taught at university in the 80s. > > The method I always used was simply putting the new > value and key in > the place of the old one, with one simple addition. > In case the spot > is filled it would look at the next 'n' spots until > it found an empty > one (or one with the same key of course). If not, > simply replace the > old values with the new. But I must say for me the > transposition > lookup was not a critical piece in terms of > performance because > evaluations were so many orders of magnitude more > expensive. So I > used n=10 for a dramatically better usage of the > available space in > the table. I did no real research in terms of > table-use, speed and > number of collisions as a function of 'n'. > > What ticked me off with the cuckoo method is > apparently it can loop > and a rehash is needed. Ouch, that better not happen > very often! > > Mark > > > On 19-jan-07, at 11:00, Å�ukasz Lew wrote: > > > Take a look at > > http://en.wikipedia.org/wiki/Cuckoo_hashing > > also. > > > > Lukasz > > > > On 1/19/07, Eduardo Sabbatella > <[EMAIL PROTECTED]> > > wrote: > >> Right now my two main concerns are about: > >> > >> 1) feasability, perhaps even prunning with UCT > for > >> storing usefull games, no more than 5 ply can be > >> stored on nowadays memory constraints. > >> > >> 2) techniques for prunning gametree on big > "databases" > >> of game configurations. This thing by itself its > a > >> quite big topic. > >> > >> About the hash method in your email, I have just > print > >> out the paper and I will read it on my commuting > back > >> home. I can't say much about hashing techniques > >> specially needed in this situation. > >> > >> I was planning to use Berkeley DB or something. > Is it > >> too bad? o_O > >> > >> Many thanks, > >> Eduardo > >> > >> --- £ukasz Lew <[EMAIL PROTECTED]> escribió: > >> > >> > I believe that clustering algorithm is > algorithm is > >> > both more > >> > practical and elegant, than > >> > two big, and other multilevel schemes. > >> > - It uses memory in more efficient manner > effecting > >> > in reduction of > >> > collision rate. > >> > - It allows for more than 2 entries on the same > hash > >> > before loosing > >> > the information > >> > > >> > I would also would like to point that there is > a new > >> > (2001) clever > >> > method of hashing > >> > i.e. Cuckoo Hashing that has the potential of > >> > replacing all other methods. > >> > > >> > If one is really serious about hash performance > then > >> > there is this > >> > 2006-hot article: > >> > > >> > http://www.cwi.nl/themes/ins1/publications/docs/ZuHeBo:DAMON:06.pdf > >> > > >> > Hope this helps :) > >> > £ukasz > >> > > >> > > >> > On 1/19/07, Erik van der Werf > >> > <[EMAIL PROTECTED]> wrote: > >> > > On 1/19/07, A van Kessel > >> > <[EMAIL PROTECTED]> wrote: > >> > > > Erik van der Werf's thesis was mainly about > >> > > > transposition table replacement algorihtms, > >> > IIRC. > >> > > > >> > > No it wasn't. I think you're confusing me > with > >> > Dennis Breuker. > >> > > > >> > > see: > >> > > http://www.xs4all.nl/~breukerd/thesis/index.html > >> > > > >> > > I have some knowledge on transposition > tables, and > >> > have even done some > >> > > experiments along the lines as suggested by > the > >> > original poster, but > >> > > it was definitely not the main topic of my > thesis > >> > (which btw can be > >> > > found at > >> > > >> > http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.ps.gz). > >> > > > >> > > > >> > > > My personal summary: it is very hard to be > more > >> > clever > >> > > > (at replacement) than "always replace when > >> > hitting an occupied slot". > >> > > > >> > > Yes, "new" does quite well under most > >> > circumstances. However, > >> > > something like "TwoBig" should be easy to > >> > implement with UCT. An > >> > > interesting question may be how to > efficiently > >> > free memory from > >> > > entries that become irrelevant in the > continuation > >> > of a game (after > >> > > the actual moves made have ruled out portions > of > >> > the full game-graph), > >> > > but this is probably not an issue in the > context > >> > of the original > >> > > poster's question. > >> > > > >> > > Erik > >> > > > _______________________________________________ > >> > > 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/ > >> > >> > >> > >> > >> > >> > >> > >> > __________________________________________________ > >> Preguntá. Respondé. DescubrÃ. > >> Todo lo que querÃas saber, y lo que ni > imaginabas, > >> está en Yahoo! Respuestas (Beta). > >> ¡Probalo ya! > >> http://www.yahoo.com.ar/respuestas > >> > >> _______________________________________________ > >> computer-go mailing list > >> [email protected] > >> > http://www.computer-go.org/mailman/listinfo/computer-go/ > >> > > _______________________________________________ > > computer-go mailing list > === message truncated === __________________________________________________ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
