[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Noob:Objects as key in hash

Tom Willis

3/6/2005 5:31:00 PM

Hi all,

I didn't want my first bit of participation on this list to be
something this silly. But I'm afraid I missed something vital in my 48
hour crash course.

If someone could take 10 seconds and tell me what I'm doing wrong I'd
greatly appreciate it and will give you props in my epitaph.

Feel free to point out and make fun of the style too :) I have thick skin.

I want to use an object as a key in a Hash.


here's some example code...

def main
puts "running this script..."
testpointid
end

def testpointid
p = PointID.new(1,1)
p2 = PointID.new(1,2)
pdup = PointID.new(1,1)
print "p!=pdup\n" if p!=pdup
d = Hash.new()
d[p]="point1"
d[p2]="point2"

#both of these return nil and I don't understand why
print "PointID test failed" if d[p]!="point1"
print "PointID test failed" if d[pdup]!="point1"

#this works, but it's not quite the interface I want
d[p.hash]="point1"
d[p2.hash]="point2"


print "PointID test failed" if d[p.hash]!="point1"
print "PointID test failed" if d[pdup.hash]!="point1"


end

class PointID
attr_reader :x,:y

def initialize(x,y)
@x = x
@y = y
@x.freeze
@y.freeze

end

def hash
return [@x.object_id,@y.object_id].to_s
end

def ==(other)
return hash == other.hash
end

def to_s
return hash()
end

end

--
Thomas G. Willis
http://paperbac...
16 Answers

Stefan Lang

3/6/2005 5:40:00 PM

0

Tom Willis wrote:

> Hi all,
>
> I didn't want my first bit of participation on this list to be
> something this silly. But I'm afraid I missed something vital in my 48
> hour crash course.
>
> If someone could take 10 seconds and tell me what I'm doing wrong I'd
> greatly appreciate it and will give you props in my epitaph.
>
> Feel free to point out and make fun of the style too :) I have thick skin.
>
> I want to use an object as a key in a Hash.
>
>
> here's some example code...
>
> def main
> puts "running this script..."
> testpointid
> end
>
> def testpointid
> p = PointID.new(1,1)
> p2 = PointID.new(1,2)
> pdup = PointID.new(1,1)
> print "p!=pdup\n" if p!=pdup
> d = Hash.new()
> d[p]="point1"
> d[p2]="point2"
>
> #both of these return nil and I don't understand why
> print "PointID test failed" if d[p]!="point1"
> print "PointID test failed" if d[pdup]!="point1"
>
> #this works, but it's not quite the interface I want
> d[p.hash]="point1"
> d[p2.hash]="point2"
>
>
> print "PointID test failed" if d[p.hash]!="point1"
> print "PointID test failed" if d[pdup.hash]!="point1"
>
>
> end
>
> class PointID
> attr_reader :x,:y
>
> def initialize(x,y)
> @x = x
> @y = y
> @x.freeze
> @y.freeze
>
> end
>
> def hash
> return [@x.object_id,@y.object_id].to_s
> end
>
> def ==(other)
> return hash == other.hash
> end
>
> def to_s
> return hash()
> end
>
> end
>

I think the problem is that you have to override the eql? method if
you override the hash method. Type 'ri Object#hash' and you'll get
the following:

------------------------------------------------------------ Object#hash
obj.hash => fixnum
------------------------------------------------------------------------
Generates a +Fixnum+ hash value for this object. This function must
have the property that +a.eql?(b)+ implies +a.hash == b.hash+. The
hash value is used by class +Hash+. Any hash value that exceeds the
capacity of a +Fixnum+ will be truncated before being used.

Type also 'ri Object#eql?' for more info.

ES

3/6/2005 6:18:00 PM

0

On Sun, March 6, 2005 5:30 pm, Tom Willis said:
> Hi all,
>
> I didn't want my first bit of participation on this list to be
> something this silly. But I'm afraid I missed something vital in my 48
> hour crash course.
>
> If someone could take 10 seconds and tell me what I'm doing wrong I'd
> greatly appreciate it and will give you props in my epitaph.
>
> Feel free to point out and make fun of the style too :) I have thick skin.
>
> I want to use an object as a key in a Hash.
>
>
> here's some example code...
>
> def main
> puts "running this script..."
> testpointid
> end
>
> def testpointid
> p = PointID.new(1,1)
> p2 = PointID.new(1,2)
> pdup = PointID.new(1,1)
> print "p!=pdup\n" if p!=pdup
> d = Hash.new()
> d[p]="point1"
> d[p2]="point2"
>
> #both of these return nil and I don't understand why
> print "PointID test failed" if d[p]!="point1"
> print "PointID test failed" if d[pdup]!="point1"
>
> #this works, but it's not quite the interface I want
> d[p.hash]="point1"
> d[p2.hash]="point2"
>
>
> print "PointID test failed" if d[p.hash]!="point1"
> print "PointID test failed" if d[pdup.hash]!="point1"
>
>
> end
>
> class PointID
> attr_reader :x,:y
>
> def initialize(x,y)
> @x = x
> @y = y
> @x.freeze
> @y.freeze
>
> end
>
> def hash
> return [@x.object_id,@y.object_id].to_s
> end
>
> def ==(other)
> return hash == other.hash
> end
>
> def to_s
> return hash()
> end
>
> end

Hash normally goes by object equality; i.e. whether the reference
points to the same object. Your #hash generates a string from the
two values, but the crux is that it's a String that it returns so
I think object-equality is used for comparisons. Try to have your
#hash return ...to_s.hash instead, and see what happens.

Generally speaking, using an object this way might not be the best
idea. If each Point were an immutable, unique instance (think Fixnum,
for example), I would think it's OK but I'm somewhat leery of this.
Maybe use the direct coordinates instead -or then make each Point
unique (and then you'd have a RefToPoint that would be used in making
shapes, for example).

What effect do you want?

> Thomas G. Willis

E

Jim Weirich

3/6/2005 6:19:00 PM

0

On Sunday 06 March 2005 12:30 pm, Tom Willis wrote:
> Hi all,

Hi Tom!

> I want to use an object as a key in a Hash.
> class PointID
[...]
> def hash
> return [@x.object_id,@y.object_id].to_s
> end
> def ==(other)
> return hash == other.hash
> end
[...]
> end

You are very close. In order to use an object as a hash key, it must support
the hash function and the eql? (not ==) function.

The hash function should return an integer to be used for hashing. Your
version returns a string. One correction might be ...

def hash
[@x.object_id, @y.object_id].to_s.hash
end

That will now work. But you probably really don't want to bother converting
the above to a string. Why not just do:

def hash
@x.object_id + @y.object_id
end

The other issue is that hash uses eql? for comparisons rather than ==. But
eql? and == compare values, but == might attempt a type conversion before
comparisons (e.g. 1 == 1.0 is true) while eql? will not (1.eql?(1.0) is
false). I would simply add:

def eql?(other)
self == other
end

That should do it.

--
-- Jim Weirich jim@weirichhouse.org http://onest...
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

Jim Weirich

3/6/2005 6:27:00 PM

0

On Sunday 06 March 2005 01:17 pm, ES wrote:

> Generally speaking, using an object this way might not be the best
> idea. If each Point were an immutable, unique instance (think Fixnum,
> for example), I would think it's OK but I'm somewhat leery of this.

Good points. I see the example uses .freeze on the x and y attributes. This
freezes the objects referenced by @x and @y (and since the objects are
Fixnum, this is a bit pointless. Fixnums are immutable anyways). What it
doesn't do is freeze the binding between @x/@y and those objects. I'm
guessing you really intended the following:

def initialize(x,y)
@x = x
@y = y
freeze # Freeze the PointID object
end

--
-- Jim Weirich jim@weirichhouse.org http://onest...
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

James Britt

3/6/2005 6:47:00 PM

0

Jim Weirich wrote:
> ...
> The hash function should return an integer to be used for hashing. Your
> version returns a string. One correction might be ...
>
> def hash
> [@x.object_id, @y.object_id].to_s.hash
> end
>
> That will now work. But you probably really don't want to bother converting
> the above to a string. Why not just do:
>
> def hash
> @x.object_id + @y.object_id
> end

Isn't this the same value as

@y.object_id + @x.object_id

giving, for example,

PointID.new( 1, 2).hash == PointID.new( 2, 1).hash


But they are different coordinates.

James

ES

3/6/2005 6:50:00 PM

0

On Sun, March 6, 2005 6:26 pm, Jim Weirich said:
> On Sunday 06 March 2005 01:17 pm, ES wrote:
>
>> Generally speaking, using an object this way might not be the best
>> idea. If each Point were an immutable, unique instance (think Fixnum,
>> for example), I would think it's OK but I'm somewhat leery of this.
>
> Good points. I see the example uses .freeze on the x and y attributes. This
> freezes the objects referenced by @x and @y (and since the objects are
> Fixnum, this is a bit pointless. Fixnums are immutable anyways). What it
> doesn't do is freeze the binding between @x/@y and those objects. I'm
> guessing you really intended the following:
>
> def initialize(x,y)
> @x = x
> @y = y
> freeze # Freeze the PointID object
> end

Yep, that would certainly work for a simple solution. For a more complex
realization of the idea, I'd consider some sort of a factory object, call
it PointSpace, for example. Whenever a user needs a reference to a point
that exists within the PointSpace, the factory finds out if there's already
a Point for the specified coordinates. If there is, a reference to that is
returned, otherwise a new Point is created. Points could of course be removed
from the list when there are no references remaining. Pretty standard factory
stuff but it'd guarantee a Point's uniqueness -and for syntactical simplicity,
Point could certainly internalize/implement PointSpace.

> -- Jim Weirich

E

Tom Willis

3/6/2005 6:55:00 PM

0

On Mon, 7 Mar 2005 03:26:55 +0900, Jim Weirich <jim@weirichhouse.org> wrote:
> On Sunday 06 March 2005 01:17 pm, ES wrote:
>
> > Generally speaking, using an object this way might not be the best
> > idea. If each Point were an immutable, unique instance (think Fixnum,
> > for example), I would think it's OK but I'm somewhat leery of this.
>>...

Thanks for the replies.

The problem I'm trying to solve. Which really isn't a problem, because
I'm just experimenting is a board game emulation.

I had an idea that a framework could be slapped together for various
board games. Tic Tac Toe, Checkers, Chess etc...

So to represent the board or get access to the board state, my first
stab at it was an immutable collection of coordinates that you can
associae arbitrary data with keyed by x,y.

I imagine I'd have a board object. And I would access it like this.

tictactoe = GameBoard.new(length=3,width=3)
tictactoe.place(2,2,"x")
tictactoe.place(3,3,"o")
tictactoe.place(2,3,"x")
tictactoe.place(3,1,"o")
tictactoe.place(2,1,"x")
>>"x's win"

class GamBoard
...
def place(x,y,data)

@pointcollection[PointID.new(x,y)].data = data if <some conditions>

end

#previous implementation which I didn't like
#because it would be something I'd do in python
def place(x,y,data)
@pointcollection["#{x}:#{y}"].data = data
end
...
end


haven't figured out the how to determine a winner yet, which is why I
didn't start with chess. :)


Probably not the best design. But my main goal is learning a new
language, and it's more fun than reading a bunch of documentation. :)

Probably more than you wanted to know, but this is how I arrived at
this little problem /misunderstanding.


Thanks again.


--
Thomas G. Willis
http://paperbac...

Joel VanderWerf

3/6/2005 8:06:00 PM

0

James Britt wrote:
> Jim Weirich wrote:
>
>> ...
>> The hash function should return an integer to be used for hashing.
>> Your version returns a string. One correction might be ...
>>
>> def hash
>> [@x.object_id, @y.object_id].to_s.hash
>> end
>>
>> That will now work. But you probably really don't want to bother
>> converting the above to a string. Why not just do:
>>
>> def hash
>> @x.object_id + @y.object_id
>> end
>
>
> Isn't this the same value as
>
> @y.object_id + @x.object_id
>
> giving, for example,
>
> PointID.new( 1, 2).hash == PointID.new( 2, 1).hash
>
>
> But they are different coordinates.

That's ok, as long as #eql? says they are different. In fact, many
objects must give the same value in response to #hash, since there are
far more possible objects than Fixnums. The #hash method is only used to
find the hash bin, and then #eql? is used to test equality within the bin.

Joel VanderWerf

3/6/2005 8:06:00 PM

0

Tom Willis wrote:
...
> class PointID
> attr_reader :x,:y
>
> def initialize(x,y)
> @x = x
> @y = y
> @x.freeze
> @y.freeze
>
> end
>
> def hash
> return [@x.object_id,@y.object_id].to_s
> end
>
> def ==(other)
> return hash == other.hash
> end
>
> def to_s
> return hash()
> end
>
> end

One approach to this problem that saves some typing (but isn't terribly
efficient because it generates garbage arrays):

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby...

Jim Weirich

3/6/2005 8:49:00 PM

0

On Sunday 06 March 2005 01:47 pm, James Britt wrote:
> Jim Weirich wrote:
> > def hash
> > @x.object_id + @y.object_id
> > end
>
> Isn't this the same value as
>
> @y.object_id + @x.object_id

Yes. As Joel points out that to some degree you expect things to occasionally
hash the the same value. If too many things hash to the same value, then
your hash array will slow down.

For small boards, it probably doesn't matter, but not only do [1,2] and [2,1]
map to the same hash, but so would [0,3] and [3,0]. In fact, all diagnols
running from the lower left to the upper right have the same hash value on
all their cells.

So x+y suggestion, while working, is rather suboptimal. How about this ...

def hash
@x + 1000*@y
end

(I dropped the object_id call because it looks like we are mapping from
fixnums).

--
-- Jim Weirich jim@weirichhouse.org http://onest...
-----------------------------------------------------------------
"Beware of bugs in the above code; I have only proved it correct,
not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)