[Jprogramming] Dictionary AKA hash

[Roger Hui]

If the keys are strings then s: would work well.
(as Dan Bron indicated in his msg).  You can run 
a few benchmarks to verify linear look-up time
and fast look-up for individual keys.



----- Original Message -----
From: Andrew Nikitin <nsg21 at hotmail.com>
Date: Friday, February 26, 2010 17:40
Subject: [Jprogramming]  Dictionary AKA hash
To: J programming <programming at jsoftware.com>

> 
> > From Roger Hui
> > Sat Feb 27 02:58:52 HKT 2010
> 
> > a. It matters a great deal what kind of keys you have.
> > b. It matters what the pattern of put and get is like.
> 
> Keys are arbitrary strings, sizes ranging 10-100. Maybe 
> occasional 1000.
> Number of Gets is about same as number of puts (within factor of 10).
> I am not looking for best solution, just for good enough. 
> Exactly like
> perl hashes. I do not know how they are implemented and quite possibly
> in certain situations there are better strategies, but they do what
> asked most of the time.
> 
> > c. The special code in J is for K&i. .  But K has to
> > be fixed.
> 
> I briefly considered redefining (tacit) get after each put to take
> advantage of this fact.  How much overhead we are talking 
> about here?
> What would be the ratio of gets to puts where it would make sense?
> Assuming that K gradually grows into 1e5
> 
> > d. One method is to make K more than twice as 
> > big as the number of real keys, and rehash when
> > the density exceeds 0.5.
> 
> I am not sure I understand that. Do you mean like preallocating space
> and then reallocating it in chunks as need goes?
> 
> BTW, since some kind of code implementing dictionaries is 
> already in the
> interpreter, maybe you would consider exposing it through pair 
> of 128!:x
> foreigns? The only difference from assignment/evaluation would 
> be that
> it needs to accept arbitrary strings as 'names'.