[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Finding shared elements between to arrays.

Sebastian probst Eide

10/9/2007 9:47:00 PM

Hi
I am wondering if there is a really smart built in way to get an array
which has the elements shared by two other arrays? I made two
"solutions" myself, but I am wondering what other people are using, and
if there is a preferred solution to the task? array.union(other_array)
or something like that?

Well... here are the two solutions that seemed the most obvious to me. I
profiled them and the second one performed a little better:

a1 = ['a', 'b', 'c', 'd']
a2 = ['c', 'd', 'e', 'f']
a3 = []

#Solution 1
a1.each { |e| a3 << e if a2.include?(e) }

#Solution 2
a3 = a1.map { |e| e if a2.include?(e) }
a3.compact!


Info from the profiler:
% cumulative self self total
time seconds seconds calls ms/call ms/call name
41.56 29.29 29.29 400000 0.07 0.11 Array#include?
28.31 49.24 19.95 100000 0.20 0.68 Array#each
22.06 64.79 15.55 1100000 0.01 0.01 String#==
4.19 67.74 2.95 200000 0.01 0.01 Array#<<
3.89 70.48 2.74 1 2740.00 70480.00 Integer#upto
0.00 70.48 0.00 1 0.00 70480.00 #toplevel

% cumulative self self total
time seconds seconds calls ms/call ms/call name
43.82 28.24 28.24 400000 0.07 0.11 Array#include?
23.32 43.27 15.03 1100000 0.01 0.01 String#==
22.25 57.61 14.34 100000 0.14 0.58 Array#map
8.50 63.09 5.48 1 5480.00 64450.00 Integer#upto
2.11 64.45 1.36 100000 0.01 0.01 Array#compact!
0.00 64.45 0.00 1 0.00 64450.00 #toplevel

Thanks in advance!

Best regards
Sebastian
--
Posted via http://www.ruby-....

15 Answers

Carl Porth

10/9/2007 9:56:00 PM

0

I think the operation you are looking for is a set intersection. In
Ruby, it is the & method.

>> ['a', 'b', 'c', 'd'] & ['c', 'd', 'e', 'f']
=> ["c", "d"]

Carl

On Oct 9, 2:46 pm, Sebastian probst Eide
<sebastian.probst.e...@gmail.com> wrote:
> Hi
> I am wondering if there is a really smart built in way to get an array
> which has the elements shared by two other arrays? I made two
> "solutions" myself, but I am wondering what other people are using, and
> if there is a preferred solution to the task? array.union(other_array)
> or something like that?
>
> Well... here are the two solutions that seemed the most obvious to me. I
> profiled them and the second one performed a little better:
>
> a1 = ['a', 'b', 'c', 'd']
> a2 = ['c', 'd', 'e', 'f']
> a3 = []
>
> #Solution 1
> a1.each { |e| a3 << e if a2.include?(e) }
>
> #Solution 2
> a3 = a1.map { |e| e if a2.include?(e) }
> a3.compact!
>
> Info from the profiler:
> % cumulative self self total
> time seconds seconds calls ms/call ms/call name
> 41.56 29.29 29.29 400000 0.07 0.11 Array#include?
> 28.31 49.24 19.95 100000 0.20 0.68 Array#each
> 22.06 64.79 15.55 1100000 0.01 0.01 String#==
> 4.19 67.74 2.95 200000 0.01 0.01 Array#<<
> 3.89 70.48 2.74 1 2740.00 70480.00 Integer#upto
> 0.00 70.48 0.00 1 0.00 70480.00 #toplevel
>
> % cumulative self self total
> time seconds seconds calls ms/call ms/call name
> 43.82 28.24 28.24 400000 0.07 0.11 Array#include?
> 23.32 43.27 15.03 1100000 0.01 0.01 String#==
> 22.25 57.61 14.34 100000 0.14 0.58 Array#map
> 8.50 63.09 5.48 1 5480.00 64450.00 Integer#upto
> 2.11 64.45 1.36 100000 0.01 0.01 Array#compact!
> 0.00 64.45 0.00 1 0.00 64450.00 #toplevel
>
> Thanks in advance!
>
> Best regards
> Sebastian
> --
> Posted viahttp://www.ruby-....


Eric I.

10/9/2007 10:00:00 PM

0

On Oct 9, 5:46 pm, Sebastian probst Eide
<sebastian.probst.e...@gmail.com> wrote:
> Hi
> I am wondering if there is a really smart built in way to get an array
> which has the elements shared by two other arrays? I made two
> "solutions" myself, but I am wondering what other people are using, and
> if there is a preferred solution to the task? array.union(other_array)
> or something like that?

The & operator, as defined on Arrays, performs an intersection
operation.

>From the RDoc:

> array & other_array
> ------------------------------------------------------------------------
> Set Intersection---Returns a new array containing elements common
> to the two arrays, with no duplicates.
>
> [ 1, 1, 3, 5 ] & [ 1, 2, 3 ] #=> [ 1, 3 ]

Also, another tip: rather than using a combination of map and
compact!, you could instead use select, as in:

a3 = a1.select { |e| a2.include?(e) }

Best,

Eric

----

Are you interested in on-site Ruby training that's been highly
reviewed by former students? http://Lea...

Sebastian probst Eide

10/9/2007 10:06:00 PM

0

Nice Carl!
Thank you very much!

Sebastian
--
Posted via http://www.ruby-....

Sebastian probst Eide

10/9/2007 10:30:00 PM

0

Yeah, I was wondering if there wasn't a better way than using map and
compact!
Ruby has so many functions that it's often hard for me to know which one
to chose. I guess I'll learn as I use Ruby more!

Thanks for the reply Eric!

Sebastian
--
Posted via http://www.ruby-....

Robert Klemme

10/10/2007 6:48:00 AM

0

2007/10/10, Eric I. <rubytraining@gmail.com>:
> On Oct 9, 5:46 pm, Sebastian probst Eide
> <sebastian.probst.e...@gmail.com> wrote:
> > Hi
> > I am wondering if there is a really smart built in way to get an array
> > which has the elements shared by two other arrays? I made two
> > "solutions" myself, but I am wondering what other people are using, and
> > if there is a preferred solution to the task? array.union(other_array)
> > or something like that?
>
> The & operator, as defined on Arrays, performs an intersection
> operation.
>
> >From the RDoc:
>
> > array & other_array
> > ------------------------------------------------------------------------
> > Set Intersection---Returns a new array containing elements common
> > to the two arrays, with no duplicates.
> >
> > [ 1, 1, 3, 5 ] & [ 1, 2, 3 ] #=> [ 1, 3 ]
>
> Also, another tip: rather than using a combination of map and
> compact!, you could instead use select, as in:
>
> a3 = a1.select { |e| a2.include?(e) }

Just a caveat: for large Arrays it might be inefficient (I don't know
how it's implemented). You might want to look at class Set:

irb(main):001:0> require 'set'
=> true
irb(main):002:0> [ 1, 1, 3, 5 ].to_set.intersection [ 1, 2, 3 ]
=> #<Set: {1, 3}>

Kind regards

robert

Sebastian probst Eide

10/10/2007 1:35:00 PM

0

I'll check it out!
Thanks Robert.

By the way: What a great forum this is! So many helpful, friendly and
knowledgeable people!

Thanks to all of you!

Best regards
Sebastian
--
Posted via http://www.ruby-....

Robert Dober

10/10/2007 1:56:00 PM

0

On 10/10/07, Eric I. <rubytraining@gmail.com> wrote:
> On Oct 9, 5:46 pm, Sebastian probst Eide
> <sebastian.probst.e...@gmail.com> wrote:
> > Hi
> > I am wondering if there is a really smart built in way to get an array
> > which has the elements shared by two other arrays? I made two
> > "solutions" myself, but I am wondering what other people are using, and
> > if there is a preferred solution to the task? array.union(other_array)
> > or something like that?
>
> The & operator, as defined on Arrays, performs an intersection
> operation.
>
> >From the RDoc:
>
> > array & other_array
> > ------------------------------------------------------------------------
> > Set Intersection---Returns a new array containing elements common
> > to the two arrays, with no duplicates.
> >
> > [ 1, 1, 3, 5 ] & [ 1, 2, 3 ] #=> [ 1, 3 ]
>
> Also, another tip: rather than using a combination of map and
> compact!, you could instead use select, as in:
>
> a3 = a1.select { |e| a2.include?(e) }
>
> Best,
>
> Eric
>
> ----
Oops I just made a fool out of myself in a different thread, funny
nobody hollered at me so far, please let me repair the damage here
a3 = a1.select { |e| a2.include?(e) }
is *not* a1 & a2
[1,1,2].select{ |x| [1,1,3].include? x }
is *not*
[1,1,2] & [1,1,3]

Well so much for being clever, I believe it was Kent Back, "clever is
an insult".

Cheers
Robert


>
> Are you interested in on-site Ruby training that's been highly
> reviewed by former students? http://Lea...
>
>
>


--
what do I think about Ruby?
http://ruby-smalltalk.blo...

Rick DeNatale

10/10/2007 2:33:00 PM

0

On 10/10/07, Robert Dober <robert.dober@gmail.com> wrote:

> > ----
> Oops I just made a fool out of myself in a different thread, funny
> nobody hollered at me so far, please let me repair the damage here
> a3 = a1.select { |e| a2.include?(e) }
> is *not* a1 & a2
> [1,1,2].select{ |x| [1,1,3].include? x }
> is *not*
> [1,1,2] & [1,1,3]


The difference being that & eliminates duplicates from the result.

Another semantic equivalent for a1.select{ |e| a2.include?(e) }

is either
a1 - (a1 - a2)
or
a2 - (a2 - a1)

Whether or not one of these performs better than the select depends on
the 'statistical' properites of the arrays:

require "benchmark"

TESTS = 10_000
a1 = [1, 2, 3, 1, 1, 4, 5] * 100
a2 = [1, 3, 5]

r1 = a1.select { |e| a2.include?(e) }
r2 = a2.select { |e| a1.include?(e) }
r3 = a1 - (a1 - a2)
r4 = a2 - (a2 - a1)

puts r1 = r2 ? "Good" : "Bad"
puts r2 = r3 ? "Good" : "Bad"
puts r3 = r4 ? "Good" : "Bad"


Benchmark.bmbm do |results|
results.report("select a1 in a2:") { TESTS.times { a1.select { |e|
a2.include?(e) } } }
results.report("select a2 in a1:") { TESTS.times { a2.select { |e|
a1.include?(e) } } }
results.report("a1 - (a1 - a2) :") { TESTS.times { a1 - (a1 - a2 ) } }
results.report("a2 - (a2 - a1) :") { TESTS.times { a2 - (a2 - a1) } }
end

Produces:

Good
Good
Good
Rehearsal ----------------------------------------------------
select a1 in a2: 3.360000 0.020000 3.380000 ( 3.417788)
select a2 in a1: 0.030000 0.000000 0.030000 ( 0.026397)
a1 - (a1 - a2) : 0.670000 0.000000 0.670000 ( 0.680342)
a2 - (a2 - a1) : 0.240000 0.010000 0.250000 ( 0.250795)
------------------------------------------- total: 4.330000sec

user system total real
select a1 in a2: 3.360000 0.010000 3.370000 ( 3.386324)
select a2 in a1: 0.020000 0.000000 0.020000 ( 0.024740)
a1 - (a1 - a2) : 0.660000 0.000000 0.660000 ( 0.670034)
a2 - (a2 - a1) : 0.240000 0.000000 0.240000 ( 0.242316)


--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denh...

Robert Dober

10/10/2007 2:47:00 PM

0

On 10/10/07, Rick DeNatale <rick.denatale@gmail.com> wrote:
> On 10/10/07, Robert Dober <robert.dober@gmail.com> wrote:
>
> > > ----
> > Oops I just made a fool out of myself in a different thread, funny
> > nobody hollered at me so far, please let me repair the damage here
> > a3 = a1.select { |e| a2.include?(e) }
> > is *not* a1 & a2
> > [1,1,2].select{ |x| [1,1,3].include? x }
> > is *not*
> > [1,1,2] & [1,1,3]
>
>
> The difference being that & eliminates duplicates from the result.
>
> Another semantic equivalent for a1.select{ |e| a2.include?(e) }
>
> is either
> a1 - (a1 - a2)
> or
> a2 - (a2 - a1)
ah interesting
I do however feel very bad about the duplicate elimination of Array#&
this really seems to be worth a RCR, Arrays are just not sets from a
conceptional POV and from a practical POV we have uniq if we want to
be the result unique.

a1 - (a1 - a2 )
which is the best effort one can make ( I guess ) just seems not so
readable anymore, and it is not an idiom frequently used so one does
not get easily acquainted to it :(
Maybe Array#intersect would be nice to have too?

Cheers
Robert
--
what do I think about Ruby?
http://ruby-smalltalk.blo...

Rick DeNatale

10/10/2007 4:38:00 PM

0

On 10/10/07, Robert Dober <robert.dober@gmail.com> wrote:

> a1 - (a1 - a2 )
> which is the best effort one can make ( I guess ) just seems not so
> readable anymore, and it is not an idiom frequently used so one does
> not get easily acquainted to it :(

Heck, I use it so infrequently that I just thought of it. <G>

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denh...