Author: KarinsDad
Date: 14:00:07 04/11/00
Go up one level in this thread
On April 11, 2000 at 11:04:35, Colin Frayn wrote: [snip] >Is this method dumb? Why? It just takes a little nasty pointer arithmetic, but >other than that it's pretty straightforward. The length of the list is rarely >more than 2 or 3 entries, so it takes no time at all to traverse. > >Input appreciated. > >Cheers, >Col Well, it may not be dumb for your program. I do something similar in my program, however, I do not used linked lists. I have 64K pointers (i.e. 2 byte key within a table of pointers to the actual hash node locations) to the hash table and then have 2 pointers within each hash node to indicate "> current node" or "< current node". So, I have unbalanced b-trees in my hash table. However, with only 64K entries, I often have collisions (one key can collide hundreds of times), so linked lists would be inefficient. I have been thinking of upping this to a 3 byte key, but that would require a 6.5M pointer table (1.6M entries) instead of a 256K pointer table (64K * 4 bytes per pointer). Then, I would be down to tens of collisions max and probing and inserting would be a lot faster (at the cost of 6.25M of memory no longer available for the hash table). But, now that I have said that, I have to add a caveat. I also have a table of "additional node information" for each hash node. My main hash table may have (for example) 6,000,000 nodes in it at any given time, but my additional node info table may have 3000 or 4000 "nodes" of additional info. That is because I currently only want score type info out of my main hash node, but I want bitmap and other specific position info out of the additional info table. So, my main hash table rarely fills up completely, but I am constantly overwriting info in the additional info table. So, just like other people overwrite nodes in their main hash table, I overwrite nodes in my additional node info table. But, I usually only clean out my main hash table if I or my opponent make a move (and occassionally if it fills up, but that hasn't happened yet to my knowledge; guess I should go check that). But, one downside of this is that when I profiled my program, I was in my hashing code a LOT more than I wanted to be. So, this is an area where vast improvement should be done in my code. KarinsDad :)
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.