# finding Hash subsets based on key value

Discussion in 'Ruby' started by ee, Jun 12, 2005.

1. ### eeGuest

Hi

Is there a simple way of searching the keys of a Hash to find a subset.
I have a set of keys with two values indicating group and sub-group,
eg:

group_1_item_1
group_2_item_2
group_1_item_2
group_1_item_4
group_2_item_3

I'd like to divide them into groups, but without having to loop through
the entire collection and having to test each key

Regards
Erik

ee, Jun 12, 2005

2. ### Martin DeMelloGuest

ee <> wrote:
> Hi
>
> Is there a simple way of searching the keys of a Hash to find a subset.
> I have a set of keys with two values indicating group and sub-group,
> eg:
>
> group_1_item_1
> group_2_item_2
> group_1_item_2
> group_1_item_4
> group_2_item_3
>
> I'd like to divide them into groups, but without having to loop through
> the entire collection and having to test each key

You can't get away without testing each key under the hood (this is
intrinsically an O(n) problem), but this should make it syntactically
convenient at least:

hash.partition {|k,v| k =~ /group_1/ }.map {|i| Hash[*i.flatten]}

Enumerable#partition divides your collection into two parts, based on
whether the block returns true or false, so it doesn't scale to more
than two subsets, but for your example it should work nicely.

martin

Martin DeMello, Jun 13, 2005

3. ### Robert KlemmeGuest

Martin DeMello wrote:
> ee <> wrote:
>> Hi
>>
>> Is there a simple way of searching the keys of a Hash to find a
>> subset. I have a set of keys with two values indicating group and
>> sub-group, eg:
>>
>> group_1_item_1
>> group_2_item_2
>> group_1_item_2
>> group_1_item_4
>> group_2_item_3
>>
>> I'd like to divide them into groups, but without having to loop
>> through the entire collection and having to test each key

>
> You can't get away without testing each key under the hood (this is
> intrinsically an O(n) problem),

Definitely!

> but this should make it syntactically
> convenient at least:
>
> hash.partition {|k,v| k =~ /group_1/ }.map {|i| Hash[*i.flatten]}
>
> Enumerable#partition divides your collection into two parts, based on
> whether the block returns true or false, so it doesn't scale to more
> than two subsets, but for your example it should work nicely.

IMHO we should have a general partitioning method (probably in Enumerable)
that does partitioning into several buckets and not just two. Something
like this maybe:

module Enumerable
def general_partition
parts = Hash.new {|h,k| h[k] = self.class.new}
each do |x|
parts[yield(x)] << x
end
parts
end
end

class Hash
def << (x) self[x[0]] = x[1] end
end

>> h={1=>1,2=>2,3=>3}

=> {1=>1, 2=>2, 3=>3}
>> h.general_partition {|k,v| k % 3}

=> {0=>{3=>3}, 1=>{1=>1}, 2=>{2=>2}}

Opinions?

Kind regards

robert

Robert Klemme, Jun 13, 2005
4. ### Martin DeMelloGuest

Robert Klemme <> wrote:
>
> IMHO we should have a general partitioning method (probably in Enumerable)
> that does partitioning into several buckets and not just two. Something
> like this maybe:
>
> module Enumerable
> def general_partition

I like it, but not the name. partition_by, perhaps.

martin

Martin DeMello, Jun 13, 2005
5. ### Robert KlemmeGuest

Martin DeMello wrote:
> Robert Klemme <> wrote:
>>
>> IMHO we should have a general partitioning method (probably in
>> Enumerable) that does partitioning into several buckets and not just
>> two. Something like this maybe:
>>
>> module Enumerable
>> def general_partition

>
> I like it, but not the name. partition_by, perhaps.

Yes, this is *much* better!

robert

Robert Klemme, Jun 13, 2005
6. ### James Edward Gray IIGuest

On Jun 13, 2005, at 3:55 AM, Robert Klemme wrote:

> Martin DeMello wrote:
>
>> Robert Klemme <> wrote:
>>
>>>
>>> IMHO we should have a general partitioning method (probably in
>>> Enumerable) that does partitioning into several buckets and not just
>>> two. Something like this maybe:
>>>
>>> module Enumerable
>>> def general_partition
>>>

>>
>> I like it, but not the name. partition_by, perhaps.
>>

>
> Yes, this is *much* better!

The Set class has this feature and I even like the name:

irb(main):001:0> require "set"
=> true
irb(main):002:0> langs = Set.new([erl, ython, :ruby])
=> #<Set: {erl, ython, :ruby}>
irb(main):003:0> langs.classify { |m| m.to_s[0, 1] }
=> {"p"=>#<Set: {erl, ython}>, "r"=>#<Set: {:ruby}>}

James Edward Gray II

James Edward Gray II, Jun 13, 2005
7. ### Martin DeMelloGuest

James Edward Gray II <> wrote:
>
> The Set class has this feature and I even like the name:
>
> irb(main):001:0> require "set"
> => true
> irb(main):002:0> langs = Set.new([erl, ython, :ruby])
> => #<Set: {erl, ython, :ruby}>
> irb(main):003:0> langs.classify { |m| m.to_s[0, 1] }
> => {"p"=>#<Set: {erl, ython}>, "r"=>#<Set: {:ruby}>}

That *is* nice - wonder if there'd be any issues with moving it into
Enumerable.

martin

Martin DeMello, Jun 14, 2005
8. ### markGuest

Crazy Balloon flight computer software...

....gonna launch a computerized weather balloon, of couse!

And of course, I need to write the flight control software in Ruby,
because it is my favourite language. Anyone know how to control a
digital camera from ruby (under linux...)

Or, failing that, how to talk to a gps receiver? I'll need to
communicate with muxes as well.

Thanks,

Mark

http://www.retrobbs.org/balloon

mark, Jun 14, 2005
9. ### Pit CapitainGuest

Martin DeMello schrieb:
>>irb(main):002:0> langs = Set.new([erl, ython, :ruby])
>>=> #<Set: {erl, ython, :ruby}>
>>irb(main):003:0> langs.classify { |m| m.to_s[0, 1] }
>>=> {"p"=>#<Set: {erl, ython}>, "r"=>#<Set: {:ruby}>}

>
> That *is* nice - wonder if there'd be any issues with moving it into
> Enumerable.

Note that Set#classify creates a set for each group, which might not
always be what you want. IMO, Enumerable#classify should create arrays

Regards,
Pit

Pit Capitain, Jun 14, 2005
10. ### Martin DeMelloGuest

Pit Capitain <> wrote:
>
> Note that Set#classify creates a set for each group, which might not
> always be what you want. IMO, Enumerable#classify should create arrays

I like Robert Klemme's implementation, where each Enumerable creates
partitions of its own type, and calls << on them to populate them. OTOH
it adds an additional dependency to Enumerable (<< as well as each), but
maybe it could default to Array if << doesn't exist.

martin

Martin DeMello, Jun 14, 2005
11. ### Hal FultonGuest

Re: Crazy Balloon flight computer software...

mark wrote:
> ....gonna launch a computerized weather balloon, of couse!
>
> And of course, I need to write the flight control software in Ruby,
> because it is my favourite language. Anyone know how to control a
> digital camera from ruby (under linux...)
>
> Or, failing that, how to talk to a gps receiver? I'll need to
> communicate with muxes as well.

I can't help you offhand, but I just wanted to say this is the
coolest thing I've heard of in a month or more.

Actually, as for controlling devices... you might look into the
home automation realm. There are some Linux-based solutions there,
probably including security cameras and such.

Hal

Hal Fulton, Jun 15, 2005
12. ### Jeffrey MossGuest

Re: Crazy Balloon flight computer software...

Most of the cheap devices use serial/RS232 or I2C communications, you'll may
want to look into the realm of microcontrollers for your project. There are
a lot of hobbyists who've written kernel modules and such for these GPS
modules.

Check this out: www.gumstix.org

I found that gumstix board a while back and decided to dive right in to the
realm of microcontrollers. Never tried compiling ruby on it, don't know how
easy that would be, maybe others have done it.

-Jeff

----- Original Message -----
From: "Hal Fulton" <>
To: "ruby-talk ML" <>
Sent: Tuesday, June 14, 2005 5:18 PM
Subject: Re: Crazy Balloon flight computer software...

> mark wrote:
>> ....gonna launch a computerized weather balloon, of couse! And of course,
>> I need to write the flight control software in Ruby,
>> because it is my favourite language. Anyone know how to control a
>> digital camera from ruby (under linux...)
>>
>> Or, failing that, how to talk to a gps receiver? I'll need to
>> communicate with muxes as well.

>
> I can't help you offhand, but I just wanted to say this is the
> coolest thing I've heard of in a month or more.
>
> Actually, as for controlling devices... you might look into the
> home automation realm. There are some Linux-based solutions there,
> probably including security cameras and such.
>
>
> Hal
>
>

Jeffrey Moss, Jun 15, 2005