[OT] Best algorithm for extremely large hashtable?

H. S. Teoh hsteoh at quickfur.ath.cx
Fri Nov 15 12:05:55 PST 2013


On Fri, Nov 15, 2013 at 08:48:19PM +0100, John Colvin wrote:
> On Friday, 15 November 2013 at 18:43:12 UTC, H. S. Teoh wrote:
> >so the edges of the graph may be thought of as a subset of the
> >edges of an n-dimensional grid.
> 
> Could perhaps elaborate on this point?
> 
> As far as I can see, the possible values of the nodes are all the
> points in N^n (or Z^n, dunno whether you have negatives) and the
> edges are all in the set of i*e_j for i in Z and j in N, where e_j
> is the unit vector along one axis, i.e. the edges are the euclidean
> basis vectors and their negatives.

Actually, i can only be 1 or -1.


> How is this the same as the edges of an n-dimensional grid?

Basically, adjacent nodes differ only in a single coordinate, and that
difference can only be 1 or -1. So for the 2D case, if you graph the
nodes on the plane, the edges would be horizontal/vertical line segments
of unit length. If you consider the 2D grid's edges to be *all* possible
such line segments, then in that sense you could think of the graph's
edges as being a subset of the 2D grid's.

I was hoping that this fact can be taken advantage of, to make a compact
representation of visited nodes.


T

-- 
By understanding a machine-oriented language, the programmer will tend
to use a much more efficient method; it is much closer to reality. -- D.
Knuth


More information about the Digitalmars-d mailing list