On Tue, 23 Aug 2005, Xeno Campanoli wrote: > Okay, I'm taking the example I got last week for multi-dimensional hashes, and > I don't have access to any Hash methods:
Xeno Campanoli <x...@eskimo.com> wrote: > Okay, I'm taking the example I got last week for multi-dimensional hashes, and > I don't have access to any Hash methods:
How it works: Hash.new {|h,k| block} creates a new hash, and calls the block whenever the hash is called with a nonexistent key. h and k, the two parameters passed to the block, are the hash itself and the key you tried to look up.
lambda {Hash.new} creates an anonymous function that returns a hash. The clever part here is that we capture a reference to the function we're defining, and pass that reference into the block we pass to the hash (this all works because lambdas are lazily evaluated). So now every time we call the hash with a missing key, the hash_factory is called again and generates a new autovivifying hash to store as the value.
Here's how you use it:
hash = hash_factory.call hash[1][2][3] #=> nil, but the hash will now have the keys
>> pHash.class # we can see its class is Proc => Proc >> pHash.call # if we call the Proc, it does its job and creates the hash => {} >> pHash[] # this is just a synonym for pHash.call
=> {}
I guess one could look at "pHash" as a factory that creates an auto-vivifying hash.
On Tue, 23 Aug 2005, William James wrote: > Phrogz wrote: >> To be clear, what Bill is saying is that you need to use pHash.call to >> create your hash, and call the Hash methods on that. Like so:
> > Phrogz wrote: > >> To be clear, what Bill is saying is that you need to use pHash.call to > >> create your hash, and call the Hash methods on that. Like so:
> >> uberhash['L']['a'] = "one" > >> p uberhash.keys #=> ["L"] > >> p uberhash['L'].keys #=> ["a"] > >> p uberhash['L'].values #=> ["one"]
> > How would you test to see if this exists?
> > h[9][8][7][6][5][4][3][2][1]
> I think it exists as soon as you refer to it. (I thought that's the > whole point :-) But if you didn't want that to happen I guess you > could do:
> if h[9][8][7][6][5][4][3][2].has_key?(1) ...
It's not the whole point. One needs to be able to check to see if an entry exists without changing the hash.
irb(main):002:0> h=pHash.call => {} irb(main):003:0> h['foo']=999 => 999 irb(main):005:0> if h[9][8][7][6][5][4][3][2].has_key?(1) then puts 'ok';end => nil irb(main):006:0> p h {"foo"=>999, 9=>{8=>{7=>{6=>{5=>{4=>{3=>{2=>{}}}}}}}}}
Even lowly Awk can easily do this. ------------------------------------------------- BEGIN { a[9,8,7,6,5,4,3,2,1] = "yes" if ( (9,8,7,6,5,4,3,2,1) in a ) print "o.k." if ( (0,8,7,6,5,4,3,2,1) in a ) print "not o.k." if ( (0,8,7,6,5,4,3,2) in a ) print "not o.k." print length(a)
On Tue, 23 Aug 2005, William James wrote: > David A. Black wrote: >> Hi --
>> On Tue, 23 Aug 2005, William James wrote:
>>> Phrogz wrote: >>>> To be clear, what Bill is saying is that you need to use pHash.call to >>>> create your hash, and call the Hash methods on that. Like so:
>>>> uberhash['L']['a'] = "one" >>>> p uberhash.keys #=> ["L"] >>>> p uberhash['L'].keys #=> ["a"] >>>> p uberhash['L'].values #=> ["one"]
>>> How would you test to see if this exists?
>>> h[9][8][7][6][5][4][3][2][1]
>> I think it exists as soon as you refer to it. (I thought that's the >> whole point :-) But if you didn't want that to happen I guess you >> could do:
>> if h[9][8][7][6][5][4][3][2].has_key?(1) ...
> It's not the whole point. One needs to be able to check > to see if an entry exists without changing the hash.
> irb(main):002:0> h=pHash.call > => {} > irb(main):003:0> h['foo']=999 > => 999 > irb(main):005:0> if h[9][8][7][6][5][4][3][2].has_key?(1) then puts > 'ok';end
I can't tell if you're saying the has_key? thing was the right solution or that it wasn't :-) The creation of the intermediate hashes is desired, right?
> >>> Phrogz wrote: > >>>> To be clear, what Bill is saying is that you need to use pHash.call to > >>>> create your hash, and call the Hash methods on that. Like so:
> >>>> uberhash['L']['a'] = "one" > >>>> p uberhash.keys #=> ["L"] > >>>> p uberhash['L'].keys #=> ["a"] > >>>> p uberhash['L'].values #=> ["one"]
> >>> How would you test to see if this exists?
> >>> h[9][8][7][6][5][4][3][2][1]
> >> I think it exists as soon as you refer to it. (I thought that's the > >> whole point :-) But if you didn't want that to happen I guess you > >> could do:
> >> if h[9][8][7][6][5][4][3][2].has_key?(1) ...
> > It's not the whole point. One needs to be able to check > > to see if an entry exists without changing the hash.
> I can't tell if you're saying the has_key? thing was the right > solution or that it wasn't :-) The creation of the intermediate > hashes is desired, right?
Quote: One needs to be able to check to see if an entry exists without changing the hash.
Creating intermediate hashes changes the hash.
Therefore, it wasn't the right solution.
The Awk example shows that Awk can perform this check without altering the hash in any way whatsoever, just as h.key?('foo') doesn't alter the hash. Having to alter the hash whenever you check for the existence of a key would be extremely crude and ineffecient.
> It's not the whole point. One needs to be able to check > to see if an entry exists without changing the hash.
> irb(main):002:0> h=pHash.call > => {} > irb(main):003:0> h['foo']=999 > => 999 > irb(main):005:0> if h[9][8][7][6][5][4][3][2].has_key?(1) then puts > 'ok';end > => nil > irb(main):006:0> p h > {"foo"=>999, 9=>{8=>{7=>{6=>{5=>{4=>{3=>{2=>{}}}}}}}}}
I'm not sure what you're trying to show here???
You called has_key?() on the last Hash. It did not add that key to the Hash, just as you said it shouldn't. The other Hashes were autovivified along the way, because you wrote code to make it so. I would be disappointed if any of the above had behaved differently and I know at least Perl has identical behavior.
That said, if you want an object that can check many levels deep without creating the upper levels, you can surely code one up with little effort.
On Tue, 23 Aug 2005, William James wrote: > David A. Black wrote: >> Hi --
>> On Tue, 23 Aug 2005, William James wrote:
>>> David A. Black wrote: >>>> Hi --
>>>> On Tue, 23 Aug 2005, William James wrote:
>>>>> Phrogz wrote: >>>>>> To be clear, what Bill is saying is that you need to use pHash.call to >>>>>> create your hash, and call the Hash methods on that. Like so:
>>>>>> uberhash['L']['a'] = "one" >>>>>> p uberhash.keys #=> ["L"] >>>>>> p uberhash['L'].keys #=> ["a"] >>>>>> p uberhash['L'].values #=> ["one"]
>>>>> How would you test to see if this exists?
>>>>> h[9][8][7][6][5][4][3][2][1]
>>>> I think it exists as soon as you refer to it. (I thought that's the >>>> whole point :-) But if you didn't want that to happen I guess you >>>> could do:
>>>> if h[9][8][7][6][5][4][3][2].has_key?(1) ...
>>> It's not the whole point. One needs to be able to check >>> to see if an entry exists without changing the hash.
>>> irb(main):002:0> h=pHash.call >>> => {} >>> irb(main):003:0> h['foo']=999 >>> => 999 >>> irb(main):005:0> if h[9][8][7][6][5][4][3][2].has_key?(1) then puts >>> 'ok';end
>> I can't tell if you're saying the has_key? thing was the right >> solution or that it wasn't :-) The creation of the intermediate >> hashes is desired, right?
> Quote: > One needs to be able to check to see if an entry exists without > changing the hash.
> Creating intermediate hashes changes the hash.
> Therefore, it wasn't the right solution.
It wasn't clear to me which hash you meant. I interpreted it as .....[2], and checking its keys was a way of checking the existence of the entry without changing the hash (i.e., *that* hash).
I do think the original impetus for this whole thing was the creation of a hash that automatically filled in with hashes in the face of h[1][2][3].... It's probably significantly harder to make a hash that does that sometimes, but not always, as it were. I haven't tried it yet though.
William James wrote: > Phrogz wrote: > > To be clear, what Bill is saying is that you need to use pHash.call to > > create your hash, and call the Hash methods on that. Like so:
> > uberhash['L']['a'] = "one" > > p uberhash.keys #=> ["L"] > > p uberhash['L'].keys #=> ["a"] > > p uberhash['L'].values #=> ["one"]
> How would you test to see if this exists?
> h[9][8][7][6][5][4][3][2][1]
Here's one way, but it doesn't seem efficient: ------------------------------------------------------------------ class Hash def has( *subs ) h=self subs.each{|x| return false unless h.key?(x) h=h[x] } true end end
uberhash['a']['b']['c']='The crux.' p uberhash.has('a','b','c') p uberhash.has('a','b','x') p uberhash ------------------------------------------------------------------
Output:
true false {"a"=>{"b"=>{"c"=>"The crux."}}}
Note that the hash wasn't changed by the check for the nonexistent key.
By the way, here's how Awk effortlessly handles multidimensional associative arrays (hashes): a['foo','bar'] is equivalent to a['foo' SUBSEP 'bar'] The keys are merely joined using a character that won't be found in the keys.
On Tue, 23 Aug 2005, William James wrote: > By the way, here's how Awk effortlessly handles multidimensional > associative arrays (hashes): > a['foo','bar'] > is equivalent to > a['foo' SUBSEP 'bar'] > The keys are merely joined using a character that won't be found > in the keys.
Am I right that the keys can only be scalar values?
> > By the way, here's how Awk effortlessly handles multidimensional > > associative arrays (hashes): > > a['foo','bar'] > > is equivalent to > > a['foo' SUBSEP 'bar'] > > The keys are merely joined using a character that won't be found > > in the keys.
> Am I right that the keys can only be scalar values?
Yes. The method is crude, but effective.
Getting back to checking for existence of a key in an autovivifying hash; what if I check for a million keys that don't exist:
1_000_000.times { |i| if h[i][8][7][6][5][4][3][2].has_key?(1) ...
}
This causes the hash to grow to enormous size. Will the garbage-collector eventually remove the spurious entries?
> Getting back to checking for existence of a key in an > autovivifying hash; what if I check for a million keys > that don't exist:
> 1_000_000.times { |i| > if h[i][8][7][6][5][4][3][2].has_key?(1) ... > }
> This causes the hash to grow to enormous size. Will the > garbage-collector eventually remove the spurious entries?
How can it? There's nothing to distinguish 'spurious' entries from 'real' ones - that's the whole point of autovivification.
That would make a cute quiz/golf problem, though - given such an autovivified hash, write a .cleanup! method that recursively deletes any keys that point to nil.
|
