From: William James <w_a_x_man@...>
Date: 2007-05-02T09:55:07+09:00
Subject: Re: Array.which_long? ( I coded an extension for Array )

On May 1, 2:26 am, "Robert Dober" <robert.do...@gmail.com> wrote:
> On 5/1/07, Robert Klemme <shortcut...@googlemail.com> wrote:
>
> > On 01.05.2007 00:03, Robert Dober wrote:
> > > On 4/30/07, Robert Klemme <shortcut...@googlemail.com> wrote:
> > > <snip>
>
> > >> >> def longest
> > >> >>    lg = Hash.new {|h,k| h[k] = []}
> > >> >>    each {|x| lg[x.size] << x}
> > >> >>    lg.sort_by {|k,v| k}.last.pop
> > >> >> end
> > >> > good idea but I wanted inject :)
> > >> >> <snip>
>
> > >> That's an easy transformation (left as exercise for the reader, bonus
> > >> points for a one liner). :-)
>
> > > inject( Hash.new{ |h,k| h[k]=[]} ){|h,e| h[e.size] << e}.sort_by....
> >                                                        ^^^^
> > The return from the block is missing. :-)
>
> Yeah I did not like this so I did not test it, I forgot the return of
> the block in the solution below too, but I liked the solution and
> therefore tested it....
>
> > > as this is not readable anymore let me golf a little bit
>
> > > inject([]){|a,e| a[e.size] = (a[e.size]||[])+[e];a}.last
> > > hmm that is not too bad ;)
>
> > Couldn't you just use ||= here?
>
> > inject([]){|a,e|(a[e.size]||=[])<<e;a}.last
>
> Indeed, I guess I was very tired!!!
> Now the solutions complexity and length just seems right.
> Thanks for getting this right.
>
> > I like your idea to use the length as array index - that way no sorting
> > is needed.  Brilliant!
>
> Well that is grossly exaggerated, but thank you anyway, the idea was
> yours of course I just used an Array instead of a Hash, that must be
> my tiny Lua background.
>
> Cheers
> Robert

I wondered whether these rather convoluted solutions had the
redeeming feature of being faster than a simple and natural
solution.  It turned out that they are slower:

             user     system      total        real
simple   0.671000   0.010000   0.681000 (  0.711000)
dober1   1.472000   0.010000   1.482000 (  1.512000)
klemme1  1.261000   0.000000   1.261000 (  1.292000)
klemme2  2.324000   0.010000   2.334000 (  2.363000)
dober2   1.903000   0.000000   1.903000 (  1.963000)
klemme3  1.211000   0.000000   1.211000 (  1.242000)
martin   1.663000   0.000000   1.663000 (  1.692000)

Here's the benchmark code:

require 'benchmark'

# Find longest strings.
class Array
  def simple
    max = map{|s| s.size}.max
    select{|s| s.size == max}
  end

  def dober1
    inject([]){ |s, e|
      if s.empty? || s.first.size < e.to_s.size then [e]
      elsif s.first.size == e.to_s.size then s << e
      else s
      end
    }
  end

  def klemme1
     inject([]) do |lg, e|
       case
         when lg.empty?, lg.first.size == e.size
           lg << e
         when lg.first.size < e.size
           [e]
         else
           lg
       end
     end
  end

  def klemme2
     lg = Hash.new {|h,k| h[k] = []}
     each {|x| lg[x.size] << x}
     lg.sort_by {|k,v| k}.last.pop
  end

  def dober2
    inject([]){|a,e| a[e.size] = (a[e.size]||[])+[e]
      a}.last
  end

  def klemme3
    inject([]){|a,e|(a[e.size]||=[])<<e;a}.last
  end

  def martin
    inject([0,[]]) { |(s,l),e|
      if e.to_s.size == s then [s,l << e]
      elsif e.to_s.size < s then [s,l]
      else [e.to_s.size, [e]]
      end
    }[1]
  end

end

methods = %w(simple dober1
  klemme1 klemme2 dober2 klemme3 martin)

words = %w(posit that it suffices that the past
  is exempt from mutation)

# Verify that all methods produce same result.
p methods.map{|method| words.send( method )}.uniq
puts

Benchmark.bm( 7 )  do |bm|

  methods.each{|method|
    bm.report( method ) do
      10_000.times{ words.send( method ) }
    end
  }

end