Asked Jan 10th, 2018 2:30 AM 79 0 1
  • 79 0 1
0

Ruby: How does `grep` method work?

Share
  • 79 0 1

Context

Problem

Let's say I want to find all even numbers in an array then double them up.
Example:

# Input:
a = [1, 2, 3, 4, 5]
# Output:
[4, 8]

I came up with 2 solutions:

Solution 1:

a.select{|x| x.even?}.map{|x| x * 2}
# => [4, 8]

Solution 2:

is_even = ->(x){x.even?}
a.grep(is_even){|x| x * 2}
# => [4, 8]

Question

In Solution 1, there are 2 iterations:

  • select will iterate through a, pick out even numbers, then return array [2, 4]
  • map will iterate through [2, 4] to double them up

I have a question about the grep method in Solution 2 :

How many iterations does ruby walk through inside method grep? Does it iterate through a, check if an element is even, if it is, yield it right away to the supplied code block? In this case, there's only one iteration.
Or does it walk through 2 iterations like in Solution 1.?

I hope I made my question clear enough. Thank you.

1 ANSWERS


Answered Jan 10th, 2018 8:15 AM
Accepted
+1

This is source code of Enumerable#grep

 static VALUE
enum_grep(VALUE obj, VALUE pat)
{
    VALUE ary = rb_ary_new();
    struct MEMO *memo = MEMO_NEW(pat, ary, Qtrue);

    rb_block_call(obj, id_each, 0, 0, rb_block_given_p() ? grep_iter_i : grep_i, (VALUE)memo);

    return ary;
}

Returns an array of every element in enum for which Pattern === element. If the optional block is supplied, each matching element is passed to it, and the block's result is stored in the output array.

So I think it's just only one iteration.

And as you said, solution 1 uses the output array of select as input of map.

FYI https://ruby-doc.org/core-2.5.0/Enumerable.html#method-i-grep https://ruby-doc.org/core-2.5.0/Enumerable.html#method-i-select https://ruby-doc.org/core-2.5.0/Enumerable.html#method-i-map

Share
Jan 10th, 2018 9:59 AM

Thank you for your answer.
Honestly, I've read the source code of Enumerable#grep but don't understand a word.
So, is it safe to say Solution 2 is more efficient than Solution 1 because it takes less iteration to process?

0
| Reply
Share
Jan 10th, 2018 1:15 PM

@toan not sure. you should check the benchmark for that 😃

require 'benchmark'
big_array = (1..10**7).to_a
is_even = ->(x){x.even?}
puts Benchmark.measure { big_array.select{|x| x.even?}.map{|x| x * 2} }
# => 0.980000   0.040000   1.020000 (  1.015895)
puts Benchmark.measure { big_array.grep(is_even){|x| x * 2} }
# => 1.480000   0.020000   1.500000 (  1.521293)

Solution 1 is faster as the benchmark result 😃

0
| Reply
Share