If you are talking about 128k nodes, I don't think traversing them will take
very long.
Peter Drake wrote:
On Jul 6, 2009, at 9:26 AM, Isaac Deutsch wrote:
If you're hashing by chaining, you presumably go to the appropriate
slot in the table, then traverse the (short) linked list of nodes
hanging from that slot. If the node you want isn't present, though,
you have to find another node you can overwrite, presumably from
another chain in the hash table. How do you find such a node without
a lengthy search?
Firstly, I don't understand the problem you describe: "If the node you
want isn't present, though, you have to find another node you can
overwrite, presumably from another chain in the hash table." Are you
referring to a node that was inserted, then overwritten, and now you
need it again?
No, I'm referring to a node that was inserted and is no longer relevant.
For example, if my tree is
A
B
C
D
E
(that is, B and D are children of the root, C is the child of B, etc.),
then I move to B, the remaining tree is:
B
C
The nodes A, D, and E are no longer relevant, because they can no longer
be reached. The challenge is to make these available for reuse
(overwriting) without traversing all of memory.
Secondly, to find a node that has to be overwritten, do you have a
criteria that always finds "the node the least probable to be used
again", or can it also return that there aren't any nodes in this
chain that should be overwritten? The first one would always limit the
search to a single chain, without looking at other chains in the hash
table, wouldn't it?
I wasn't aiming for that level of sophistication; just hoping to reuse
nodes that are no longer in the tree (dag) because they're along roads
not taken.
Peter Drake
http://www.lclark.edu/~drake/
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
