CODEWITHSUNDEEP
arraysruby
Pend
Pend

Reputation: 742

Finding the value and index of the first occurence of the largest element in an array

I'm looking for a way to find the value and index of the first occurrence of the largest element in an array (in ruby). I have not been able to find a way to achieve this with fewer than 2 lines of code and without traversing the array more than I would like.

First I tried:

example = [1, 100, 2, 100, 3]
value, index = example.each_with_index.max

But this gives me the index of the last occurrence of the largest element.

My current approach is:

example = [1, 100, 2, 100, 3]
value = example.max
index = example.find_index(value)

Which works, but if the first and last occurrences of the largest element are the last two elements of the array, my current code has to traverse pretty much the entire array twice.

I'm more interested in performance than code size, but if there is a non-wasteful one-line solution that would be great!

Upvotes: 0

Views: 274

Answers (2)

Cary Swoveland
Cary Swoveland

Reputation: 110675

Here is a one-pass solution, but I would be surprised if it were faster than the OP’s two-pass solution, considering that Array#max and Array#find_index are both implemented in C and are optimized for arrays (as opposed to their Enumerable counterparts).

 value, index = example.each_with_index.max_by { |n,i| [n,-i] }
  #=> [100, 1]

When you tried example.each_with_index.max, you first computed

enum = example.each_with_index
  #=> #<Enumerator: [1, 100, 2, 100, 3]:each_with_index>

We can convert this enumerator to an array to see what elements it will generate.

enum.to_a
  #=> [[1, 0], [100, 1], [2, 2], [100, 3], [3, 4]]

When Array#max is sent to enum it orders the elements generated by enum, largest to smallest, as follows.

[[100, 3], [100, 1], [3, 4], [2, 2], [1, 0]]

The reason for this ordering is explained in the third paragraph in the doc for Array#<=>.

That's why you obtained

enum.max
  #=> [100, 3]

By contrast, I have Enumerable#max_by searching for the largest value in

a = [[1, 0], [100, -1], [2, -2], [100, -3], [3, -4]]

which is

a.max
  #=> [100, -1]

so [100, 1] is returned.

Upvotes: 3

Stefan Pochmann
Stefan Pochmann

Reputation: 28596

I'm more interested in performance

You really should measure then. Your own solution is about 75 times faster than Cary's solution (who also really should've measured).

              user     system      total        real
Yours     0.484000   0.000000   0.484000 (  0.485868)
Cary's   36.094000   0.000000  36.094000 ( 36.412679)

Yes, your solution traverses the array twice. But it's two fast traversals. Cary only has one traversal, but it's a slow one. He's doing much much more per element, an enumerator gets involved, and he's partially doing it in Ruby code.

My benchmark code:

require 'benchmark'

example = (1..10**8).to_a
Benchmark.bm(7) do |x|
  x.report("Yours") {
    value = example.max
    index = example.index(value)
  }
  x.report("Cary's") {
    value, index = example.each_with_index.max_by { |n,i| [n,-i] }
  }
end

I btw changed your example.find_index to example.index. Same thing. Just shorter name.

The fastest single-pass solution (if you for some reason insist on one) I came up with is this:

value, index = example[0], 0
i = 0
example.each do |v|
  if v > value
    value = v
    index = i
  end
  i += 1
end

That took about 4.8 seconds, so about 7.5 times faster than Cary's but still about 10 times slower than yours.

Bottom line: Use your own solution. You can even make it a short one-liner (but I wouldn't):

index = example.index(value = example.max)

Upvotes: 1

Related Questions