QUESTION: Good data structure for list within list with duplicates?

B

basi

Hello,
I have a dictionary within a dictionary, where the inner dictionary may
have duplicate keys:

"x" =>
"aa" => 2
"aa" => 3
"bb" => "boo"
..

"y" =>
"aa" => 5
"cc" => "see"
"cc" => "sea"
..
...

The first level has about 750 entries.

First, what is a good structure for this? I've looked at hash within
hash, but I'm not up to adopting some of the ways to handle duplicate
keys in hash -- unless there's one that even a rank newbie like myself
can use.

The key query I'd need from the list is finding if in the embedded
dictionary a value exists for a key, where the key may have duplicates,
for example, Is "see" a value of the key "cc" in "y"?

Thanks.

basi
 
T

Trans

The appropriate structure is probably Associative Arrays in Hash.

{
"x" => [
[ "aa", 2 ],
[ "aa", 3 ],
[ "bb", "boo" ],
...
],

"y" => [
[ "aa", 5 ],
[ "cc" , "see" ],
[ "cc" , "sea" ],
...
],
...
}

You can create you own class for it too, start with something like
this:

class PairHash

def initialize()
@outer = Hash.new([])
end

def add_entry( x, y, z )
a = [y,z]
@outer[x] << a
a
end

def del_entry( x, y=nil )
if y
@outer[x].reject! { |e| e[0] == y }
else
@outer.delete(x)
end
end

def inner_value?( v, x, y )
@outer[x].select { |e| e == [y,v] }
end

end

# demo
ph = PariHash.new
ph.add_entry( "x", "aa", 2 )
ph.add_entry( "x", "aa", 3 )
ph.add_entry( "x", "bb", "boo" )
ph.inner_value?( 3, "x", "aa" ) )

T.
 
D

Dominik Bathon

Hello,
I have a dictionary within a dictionary, where the inner dictionary may
have duplicate keys:

"x" =3D>
"aa" =3D> 2
"aa" =3D> 3
"bb" =3D> "boo"
..

"y" =3D>
"aa" =3D> 5
"cc" =3D> "see"
"cc" =3D> "sea"
..
...

The first level has about 750 entries.

First, what is a good structure for this? I've looked at hash within
hash, but I'm not up to adopting some of the ways to handle duplicate
keys in hash -- unless there's one that even a rank newbie like myself
can use.

You can use hashes within a hash, where the values of your inner hashes =20
are arrays. Your example would then look like:

{ "x" =3D> { "aa" =3D> [2, 3], "bb" =3D> ["boo"] },
"y" =3D> { "aa" =3D> [5], "cc" =3D> ["see", "sea"] } }

To ease the construction of this you should create your outer hash like =20
that:

h =3D Hash.new { |h,k|
h[k] =3D Hash.new { |h2,k2|
h2[k2] =3D []
}
}

If you have never used Hash::new with a block, then please read "ri =20
Hash::new":

-------------------------------------------------------------- Hash::new
Hash.new =3D> hash
Hash.new(obj) =3D> aHash
Hash.new {|hash, key| block } =3D> aHash
------------------------------------------------------------------------
Returns a new, empty hash. If this hash is subsequently accessed by
a key that doesn't correspond to a hash entry, the value returned
depends on the style of +new+ used to create the hash. In the first
form, the access returns +nil+. If _obj_ is specified, this single
object will be used for all _default values_. If a block is
specified, it will be called with the hash object and the key, and
should return the default value. It is the block's responsibility
to store the value in the hash if required.

h =3D Hash.new("Go Fish")
h["a"] =3D 100
h["b"] =3D 200
h["a"] #=3D> 100
h["c"] #=3D> "Go Fish"
# The following alters the single default object
h["c"].upcase! #=3D> "GO FISH"
h["d"] #=3D> "GO FISH"
h.keys #=3D> ["a", "b"]

# While this creates a new default object each time
h =3D Hash.new { |hash, key| hash[key] =3D "Go Fish: #{key}" }
h["c"] #=3D> "Go Fish: c"
h["c"].upcase! #=3D> "GO FISH: C"
h["d"] #=3D> "Go Fish: d"
h.keys #=3D> ["c", "d"]


Then you can build your example:

irb(main):022:0> h =3D Hash.new { |h,k| h[k]=3DHash.new { |h2,k2| h2[k2]=3D=
[] } }
=3D> {}
irb(main):023:0> h["x"]["aa"] << 2
=3D> [2]
irb(main):024:0> h["x"]["aa"] << 3
=3D> [2, 3]
irb(main):025:0> h["x"]["bb"] << "boo"
=3D> ["boo"]
irb(main):026:0> h["y"]["aa"] << 5
=3D> [5]
irb(main):027:0> h["y"]["cc"] << "see"
=3D> ["see"]
irb(main):028:0> h["y"]["cc"] << "sea"
=3D> ["see", "sea"]
irb(main):029:0> h
=3D> {"x"=3D>{"bb"=3D>["boo"], "aa"=3D>[2, 3]}, "y"=3D>{"cc"=3D>["see", "=
sea"], =20
"aa"=3D>[5]}}
The key query I'd need from the list is finding if in the embedded
dictionary a value exists for a key, where the key may have duplicates,
for example, Is "see" a value of the key "cc" in "y"?

irb(main):030:0> h["y"]["cc"].include?("see")
=3D> true
irb(main):031:0> h["y"]["cc"].include?("sea")
=3D> true
irb(main):032:0> h["y"]["cc"].include?("s")
=3D> false

Hope that helps,
Dominik
 
B

basi

Both Trans' and Dominik's suggestions look like I can get them to work.
Thank you both!

basi
 
W

Wayne Vucenic

Or, as a variation on the above solutions, use an array of the two
keys as the hash key:

@h =3D {["x","aa"] =3D> [2,3], ["x", "bb"] =3D> ["boo"],
["y","aa"] =3D> [5], ["y", "cc"] =3D> ["see", "sea"]}

def isValue?(main,embedded,value)
return false if @h[[main, embedded]].nil?
@h[[main, embedded]].include?(value)
end
=20
p isValue?("y", "cc", "see") # true
p isValue?("a", "b", "c") # false
=20
Wayne Vucenic
No Bugs Software
"Ruby and C++ Contract Programming in Silicon Valley"
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top