INNER JOINING Two Arrays

D

Dan

I have two arrays a and b which I need to iterate through simultaneously cr=
eating essentially an "INNER JOIN" on the values of the two arrays. Both ar=
rays contain integers and are sorted in ascending order. The first value in=
each array is the same and the last value in each array is the same. On ea=
ch iteration through the arrays I need to obtain the indexes of each array =
if the array values are equal to each other.

This is the code I have which works:

a=3D[1,2,5,13]
b=3D[1,1,2,2,2,5,13,13,13]

indexs=3D[]
items=3D[]
a.each_with_index do |itema,indexa|
=A0b.each_with_index do |itemb,indexb|
=A0 if (itema=3D=3Ditemb) then
=A0=A0 puts "#{indexa} #{indexb}"
=A0=A0 indexs << [indexa,indexb]
=A0=A0 items=A0 << [itema,itemb]
=A0 else=20
=A0=A0 next
=A0 end
=A0end
end

producing this output:

0 0
0 1
1 2
1 3
1 4
2 5
3 6
3 7
3 8

and these values of indexs and items:

irb(main):017:0> indexs
=3D> [[0, 0], [0, 1], [1, 2], [1, 3], [1, 4], [2, 5], [3, 6], [3, 7], [3, 8=
]]

irb(main):018:0> items
=3D> [[1, 1], [1, 1], [2, 2], [2, 2], [2, 2], [5, 5], [13, 13], [13, 13], [=
13, 13]]

Q1: Is there a more idiomatic and concise way of doing this using functiona=
l array methods?=A0=20

Also note that if you interchanged the two each loops they would produce th=
e same output and results:

b.each_with_index do |itemb,indexb|
=A0a.each_with_index do |itema,indexa|
=A0 ...
=A0end
end

Q2: Are there any observations one could make about which scenario would be=
faster both for my code and a more idiomatic solution you might have?
 
R

Robert Klemme

Q2: Are there any observations one could make about which scenario
would be faster both for my code and a more idiomatic solution you
might have?

Your algorithm has effort O(n*m) while with the given preconditions you
should be able to achieve O(n+m) instead. Less formal speaking, your
version compares each possible pair (all combinations, hence n*m) while
more efficient approaches exist.

Hint (because this seems to be some kind of assignment): you cannot use
Ruby's iteration via #each but should use array indexes.

Kind regards

robert
 
7

7stud --

I'd do something like this:

b=[1,1,2,2,2,5,13,13,13]
data = Hash.new{|hash, key| hash[key] = []}

b.each_with_index do |num, i|
data[num] << i
end

a=[1,2,5,13]

indexes = []
items = []

a.each_with_index do |num, i|
indexes_for_num = data[num]
arrs = indexes_for_num.map{|index| [i, index]}
indexes.push(*arrs)

indexes_for_num.length.times{items << [num, num]}
end

p indexes
p items

--output:--
[[0, 0], [0, 1], [1, 2], [1, 3], [1, 4], [2, 5], [3, 6], [3, 7], [3, 8]]
[[1, 1], [1, 1], [2, 2], [2, 2], [2, 2], [5, 5], [13, 13], [13, 13],
[13, 13]]

For small arrays, like the ones in your example, the speeds will be
close, but as the arrays get bigger, the hash lookups will be much
faster, like 10 times faster.
 

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

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top