From: Robert Klemme <shortcutter@...>
Date: 2007-05-02T20:10:05+09:00
Subject: Re: Array.which_long? ( I coded an extension for Array )

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)

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?

Kind regards

	robert