using a range as a key

[Michael Linfield]

I'm trying to achieve the effect of having a range of integers as a hash
key, possible?

In effect I've tried:

range = 12345...12360

hash = { range => "success!" }

hash[12349]

=> nil

I've also tried:

array = []
range.each{|x| array << x}

hash = { array => "success!" }

hash[12349]
=> nil

Anyone have any advice to point me in a direction?

Thanks!

- Mac

 

[Robert Klemme]

I'm trying to achieve the effect of having a range of integers as a hash
key, possible?

In effect I've tried:

range = 12345...12360

hash = { range => "success!" }

hash[12349]

This cannot possibly work as 12349 != (12345...12360)

=> nil

I've also tried:

array = []
range.each{|x| array << x}

hash = { array => "success!" }

hash[12349]
=> nil

Same story.

Anyone have any advice to point me in a direction?

If you *always* want to access via individual numbers you can do

irb(main):025:0> range = 12345...12360
=> 12345...12360
irb(main):026:0> hash = {}
=> {}
irb(main):027:0> range.each {|i| hash = "success!"}
=> 12345...12360
irb(main):028:0> hash[12349]
=> "success!"

Although I believe there are more space effective solutions (maybe
storing range lower boundaries in an array and doing binary search). It
all depends on the problem you are trying to solve.

Kind regards

robert

 

[Zundra Daniel]

[Note: parts of this message were removed to make it a legal post.]

is this what you're trying to do

range = 12345...12360
hash = {range=>"success"}
hash[range]
=> "success"

 

[Alex Wayne]

I'm trying to achieve the effect of having a range of integers as a hash
key, possible?

In effect I've tried:

range = 12345...12360

hash = { range => "success!" }

hash[12349]

=> nil

This won't work. The range is a specific object, and that whole object
is the key
that points to "success!". SO in order to get success, you would need
to:

hash[12345...12360]

Hash won't do this on its own. Here is one way to go about this:

class RangedHash
def initialize(hash)
@ranges = hash
end

def [](key)
@ranges.each do |range, value|
return value if range.include?(key)
end
nil
end
end

ranges = RangedHash.new(
1..10 => 'low',
21..30 => 'medium',
41..50 => 'high'
)
ranges[5] #=> "low"
ranges[15] #=> nil
ranges[25] #=> "medium"

 

[Trans]

I'm trying to achieve the effect of having a range of integers as a hash
key, possible?

In effect I've tried:

range = 12345...12360

hash = { range => "success!" }

hash[12349]

=> nil

This won't work. The range is a specific object, and that whole object
is the key
that points to "success!". SO in order to get success, you would need
to:

hash[12345...12360]

Hash won't do this on its own. Here is one way to go about this:

class RangedHash
def initialize(hash)
@ranges = hash
end

def [](key)
@ranges.each do |range, value|
return value if range.include?(key)
end
nil
end
end

ranges = RangedHash.new(
1..10 => 'low',
21..30 => 'medium',
41..50 => 'high'
)
ranges[5] #=> "low"
ranges[15] #=> nil
ranges[25] #=> "medium"

It's an interesting idea. What is needed is a Hash that can have key
equality redefined. I seem to recall that 1.9 may have something for
this, so as too allow indifferent key access, and it may work here too
(using === instead of ==, or is it eql?) but I haven't explored it
yet.

T.

 

[Michael Linfield]

class RangedHash
def initialize(hash)
@ranges = hash
end

def [](key)
@ranges.each do |range, value|
return value if range.include?(key)
end
nil
end
end

ranges = RangedHash.new(
1..10 => 'low',
21..30 => 'medium',
41..50 => 'high'
)
ranges[5] #=> "low"
ranges[15] #=> nil
ranges[25] #=> "medium"

Beautiful. Works great,

However! The file that I'll be importing will probably contain a large
amount of traffic being pushed at RangedHash.new

If I had a predefined data file ie:

12345..12350 => 89734, 23456..23460 => 23532

ect ect. commas separating the ranges like above...How do I import the
literal of that file instead of the string.

file = File.readlines('testdata.txt') # this creates only 1 array
element

file[0].class
#=> String
file[1]
#=> nil

So this obviously wouldn't work in a manner of the following:

ranges = RangedHash.new(file)

Same goes for file = File.open('testdata.txt', 'w+')
Maybe Marshaldump is the way to go?

Ideas?

Thanks!

- Mac

 

[Calamitas]

It's an interesting idea. What is needed is a Hash that can have key
equality redefined. I seem to recall that 1.9 may have something for
this, so as too allow indifferent key access, and it may work here too
(using === instead of ==, or is it eql?) but I haven't explored it
yet.

Interesting idea, and it would work, but it wouldn't work very well as
you'll lost most of the advantage of hashing

Say we limit ourselves to ranges of integers for now. Then for hashing
to work, any integer and any range that integer is in should have the
same hash value. This means that all integers a and b, a < b, have the
same hash value because a..b includes both, so both must have the same
hash value as a..b. This obviously also means that all such ranges
must have the same hash value. So although it will still work, the
hashing function will be very bad.

Peter

 

[Robert Dober]

I'm trying to achieve the effect of having a range of integers as a hash
key, possible?

In effect I've tried:

range = 12345...12360

hash = { range => "success!" }

hash[12349]

=> nil

This won't work. The range is a specific object, and that whole object
is the key
that points to "success!". SO in order to get success, you would need
to:

hash[12345...12360]

Hash won't do this on its own. Here is one way to go about this:

class RangedHash
def initialize(hash)
@ranges = hash
end

def [](key)
@ranges.each do |range, value|
return value if range.include?(key)
end
nil
end
end

ranges = RangedHash.new(
1..10 => 'low',
21..30 => 'medium',
41..50 => 'high'
)
ranges[5] #=> "low"
ranges[15] #=> nil
ranges[25] #=> "medium"

It's an interesting idea. What is needed is a Hash that can have key
equality redefined. I seem to recall that 1.9 may have something for
this, so as too allow indifferent key access, and it may work here too
(using === instead of ==, or is it eql?) but I haven't explored it
yet.

T.

The basic problem I am seeing is that by accessing a hash with ranges
as keys by elements of these ranges we simply lose our constant lookup
time. I have some difficulties that we can come up with hash functions
that yield the same value for
the range and all its elements and different values for most other ranges.
Another issue would of course be how to define behavior in case of
overlapping ranges - undefined would probably the best one can come up
without needing to traverse the whole hash for each update.

Well if we sacrifice constant lookup time of course search trees might
indeed solve OP's problem.

Cheers
Robert

 

[Eivind Eklund]

However! The file that I'll be importing will probably contain a large
amount of traffic being pushed at RangedHash.new

I smell premature optimization, under the terms "probably" and "large".

For a range set that is lower than about 10 million numbers (100
million for a high end machine), it should work quote OK to push each
number in each range into a hash. I would try this before going off
an writing code to support something more complex.

Apart from that, this is solvable in O(log N) per lookup using a
binary tree. If you need something faster, you could do it by
constructing your tree in byte based buckets - essentially, you end up
with one lookup per byte in your number, finding what range it is part
of when the number is well enough resolved that it can only be in one
range.

I have never heard of any way to construct hashes that would be useful
for this, and my gut feeling is that it would have to combine with one
of the above algorithms anyway, and you'd have to do a post-read
perfect hash construction - basically, you'd have to define your
ranges up front and then dynamically create a hash function from it.
My hunch is that this would only be worthwhile if you were dealing
with data sets of many terabytes, and had to process them quickly and
regularly. Of course, it is an interesting research problem...

Eivind.

 

[Ilan Berci]

Apart from that, this is solvable in O(log N) per lookup using a
binary tree. If you need something faster, you could do it by
constructing your tree in byte based buckets - essentially, you end up
with one lookup per byte in your number, finding what range it is part
of when the number is well enough resolved that it can only be in one
range.

Eivind.

As a clarification, it's only LogN if you are using a sorted array with
binary lookup, the RangedHash implementation as above will not perform
LogN.. It will be N..

I also believe that this is not a case of premature optimization, If
someone says hash to me, I immediately expect it to behave as a LogN and
I don't want to concern myself with number of entries within the
container.. Hashes are simply hashes, and if you want to make them
perform different than from what every coder knows them to be, then at
least have the courtesy to change the class name..

ilan

 

[Robert Klemme]

As a clarification, it's only LogN if you are using a sorted array with
binary lookup, the RangedHash implementation as above will not perform
LogN.. It will be N..

I also believe that this is not a case of premature optimization, If
someone says hash to me, I immediately expect it to behave as a LogN and

Did you want to say "behave as O(1)" - because that's what is usually
considered to be hash lookup performance?

I don't want to concern myself with number of entries within the
container.. Hashes are simply hashes, and if you want to make them
perform different than from what every coder knows them to be, then at
least have the courtesy to change the class name..

Absolutely.

Kind regards

robert

 

[Trans]

Interesting idea, and it would work, but it wouldn't work very well as
you'll lost most of the advantage of hashing

Say we limit ourselves to ranges of integers for now. Then for hashing
to work, any integer and any range that integer is in should have the
same hash value. This means that all integers a and b, a < b, have the
same hash value because a..b includes both, so both must have the same
hash value as a..b. This obviously also means that all such ranges
must have the same hash value. So although it will still work, the
hashing function will be very bad.

You are right of course. And actually, I'm not sure it could even
work, now that you mention these details. How could a..b and a..c have
the same hash value in order to match the hash value of x such that a
< x < b and a < x < c. -- Am I understanding this right?

However, beyond that, I can imagine some sort of flexible and
optimized Lookup class that uses a re-definable key match proc which
could be quite handy.

T.

 

[Michael Linfield]

I smell premature optimization, under the terms "probably" and "large".



Eivind.

Precisely what I did. Knowing there was no way to actual construct a
hash needing the format I did within say IRB, I created a basic file
utilizing the hash structure, then imported it as a whole literal.

if you want to make them
perform different than from what every coder knows them to be, then at
least have the courtesy to change the class name..

I completely agree and plan to change that class name now that its been
brought to my attention.

A more 'correct' approach to this scenario would be of course to use an
SQL database and deal with the ranges in that matter, but theres always
the challenge of how to do it different than everyone else

- Mac