ruby array intersection performance issue

Question

I need to make intersection of n-arrays with millions of elements (database ID's). This code works perfect, but slow (with very big arrays). How can i improve it?

[[1,2,3,4],[2,4,6,8],[4,5,8]].inject([]){|c,v| c = v if c.size==0; c = c&v if c.size>0; c }

megas · Accepted Answer · 2012-10-05 13:26:10Z

6

[1,2,3,4] & [2,4,6,8] & [4,5,8] #=> [4]

The intersection method uses hash so it should be quick.

answered Oct 5, 2012 at 13:26

megas

21.9k12 gold badges84 silver badges134 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kyle · Accepted Answer · 2012-10-05 15:05:01Z

3

Ruby provides an intersection opperator.

May I suggest you try this:

> [[1,2,3,4],[2,4,6,8],[4,5,8]].reduce{ |accum, arr| accum & arr } => [4]

Edit:

This can be written a little more concise but it suffers from readability.

[[1,2,3,4],[2,4,6,8],[4,5,8]].reduce(:&)

edited Oct 5, 2012 at 15:05

answered Oct 5, 2012 at 13:25

Kyle

22.3k2 gold badges63 silver badges63 bronze badges

5 Comments

Kyle Over a year ago

yes. [[1,2,3,4],[2,4,6,8],[4,5,8]].reduce{ |accum, arr| accum | arr }

megas Over a year ago

You can use without &, just reduce(:&)

megas Over a year ago

It's not a reduce, it's because of intersection method.

Kyle Over a year ago

Correct. It would work the same if you replace reduce with inject as they are aliases of each other.

Parikshit Singh Over a year ago

What is the time complexity of this operator? Any links will help

Collectives™ on Stack Overflow

ruby array intersection performance issue

2 Answers 2

Comments

5 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Related