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

On May 2, 6:05 am, Robert Klemme <shortcut...@googlemail.com> wrote:
> On 02.05.2007 02:50, William James wrote:
>
>
>
> > 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
>
> Actually you forgot an an even simpler solution - although it is not as
> short as the other ones.  Probably better call it "more straightforward":
>
>    def simple2
>      res = []
>      len = 0
>
>      each do |s|
>        case s.length <=> len
>          when 1
>            len = s.length
>            res.clear << s
>          when 0
>            res << s
>          when -1
>            # too short, ignore
>          else
>            raise "Wrong comparison result: #{s.length <=> len}"
>        end
>      end
>
>      res
>    end
>
> 13:00:10 [Temp]: ./maxing.rb
> [["suffices", "mutation"]]
>
>               user     system      total        real
> simple   0.235000   0.000000   0.235000 (  0.239000)
> simple2  0.219000   0.000000   0.219000 (  0.187000)
> dober1   0.437000   0.000000   0.437000 (  0.435000)
> klemme1  0.407000   0.000000   0.407000 (  0.401000)
> klemme2  0.734000   0.000000   0.734000 (  0.765000)
> dober2   0.656000   0.000000   0.656000 (  0.658000)
> klemme3  0.344000   0.000000   0.344000 (  0.376000)
> martin   0.531000   0.000000   0.531000 (  0.529000)

Although this is faster, it would take me a lot longer,
starting from scratch, to understand it than to understand
the 2-line "simple" method.

>
> The reason is - of course - that you need to traverse the array only once.
>
> Btw, any idea why I'm seeing this if I replace "bm" with "bmbm"?
>
> 13:00:44 [Temp]: ./maxing.rb
> [["suffices", "mutation"]]
>
> Rehearsal -------------------------------------------
> simple  ./maxing.rb:99:in `send': undefined method `simple ' for
> #<Array:0x104226b4> (NoMethodError)
>          from ./maxing.rb:99
>          from ./maxing.rb:99:in `times'
>          from ./maxing.rb:99
>          from /usr/lib/ruby/1.8/benchmark.rb:293:in `measure'
>          from /usr/lib/ruby/1.8/benchmark.rb:261:in `bmbm'
>          from /usr/lib/ruby/1.8/benchmark.rb:259:in `each'
>          from /usr/lib/ruby/1.8/benchmark.rb:259:in `bmbm'
>          from ./maxing.rb:95
>
> Even though "simple" is reported an instance method of Arrray?

I noticed the same thing during my testing.
Benchmark tacks a space onto the "method" string.
A simple fix:
      10_000.times{ words.send( method.strip ) }

>
> Kind regards
>
>         robert