Performance using the Ruby 'include?' method

Question

I would like to know how much the include? method can affect the performance if I have something like this:

array = [<array_values>]           # Read above for more information

(0..<n_iterations>).each { |value| # Read above for more information
  array.include?(value)
}

In cases <array_values> are 10, 100 and 1.000 and <n_iterations> are 10, 100, 1000.

Also, your question is a bit unclear to me. Can you provide an example of what array could be? — Sophie Alpert
– Sophie Alpert, Commented Jun 25, 2011 at 3:46
@Andrew Grimm - How can I try running the code in the IRB / Rails console and retrieve perfomance time or other important information about this matter? — user502052
– user502052, Commented Jun 25, 2011 at 3:46

Marc-André Lafortune · Accepted Answer · 2011-06-25 03:49:59Z

17

Use a Set (or equivalently a Hash) instead of an array, so that include is O(1) instead of O(n).

Or if you have multiple include to do, you can use array intersection & or subtraction - which will build a temporary Hash to do the operation efficiently.

answered Jun 25, 2011 at 3:49

Marc-André Lafortune

79.8k17 gold badges172 silver badges167 bronze badges

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

3 Comments

Sophie Alpert Over a year ago

The asker now suggests that it is an array of strings, so conversion to a Set/Hash doesn't sound possible.

Marc-André Lafortune Over a year ago

@Ben Alpert: Why not? An Array of <anything> can be converted to a Set of <anything>. If using a Hash, use the objects as the keys (and use true, say, for the corresponding values). Note that Set does exactly that internally.

Sophie Alpert Over a year ago

Whoops, my bad. I misread the question as doing (essentially) array.each { |el| el.include? value }; you're completely right.

Yardboy · Accepted Answer · 2011-06-25 03:59:43Z

2

I think ruby-prof might be a good place to start. However, that performance data won't be useful without something else to compare this to. As in, "is the performance of this method better or worse than [some other method]?"

Also, note that as n_iterations increases larger than the size of array, this code will probably perform better, due to sheer number of #include? calls.

array.each do |value|
  (0..<n_iterations>).map.include?(value)
end

edited Jun 25, 2011 at 3:59

answered Jun 25, 2011 at 3:52

Yardboy

2,8251 gold badge25 silver badges31 bronze badges

Collectives™ on Stack Overflow

Performance using the Ruby 'include?' method

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related