From: Robert Klemme <shortcutter@...>
Date: 2011-03-04T19:11:42+09:00
Subject: Re: Extracting the shortest string from an array

On Thu, Mar 3, 2011 at 7:18 PM, Josh Cheek <josh.cheek@gmail.com> wrote:
> On Thu, Mar 3, 2011 at 11:35 AM, Robert Klemme
> <shortcutter@googlemail.com>wrote:
>
>> On 03.03.2011 16:02, Thorsten Hater wrote:
>>
>>> in Ruby 1.9 this should work:
>>>
>>>    arr.sort_by(&:length)[0]
>>>
>>
>> Inefficient as it creates a new array.  Better do
>>
>> irb(main):001:0> ["qwe", "qwerty"].min_by(&:length)
>> => "qwe"
>>
>>
>>  or more portable/readable (1.8 compatible):
>>>
>>>    arr.sort_by{|s| s.length }[0]
>>>
>>
>> Inefficient as well (see above).

> They're also O( n lg n ) where the correct solution, using min, is O(n)

How do you know that it's O(n * log n)?  A reasonable implementation
of min_by would look like this:

def min_by(enum, &c)
  min = nil
  val = nil

  enum.each do |e|
    e_val = c[e]

    if val.nil? || e_val < val
      min = e
      val = e_val
    end
  end

  min
end

As far as I can see this is O(n).

Also, big O isn't everything.  Usually object allocation is very
expensive (compared to other operations) because of the GC
housekeeping overhead.

Cheers

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/