From: Gavin Kistner <gavin@...>
Date: 2005-12-06T11:41:17+09:00
Subject: Re: Speed Golf - Remove Early Dups

On Dec 5, 2005, at 6:27 PM, ako... wrote:
> i meant in.reverse.uniq!.reverse! (the first reverse is non- 
> destructive)

Array#uniq! can return nil if no changes were made. This will not  
occur given the above input, but can for the general case.

Using reverse rather than dup does shave a bit of time off, though,  
which puts it as the winner on my machine. So far:

Rehearsal --------------------------------------------------------
William James          4.230000   0.060000   4.290000 (  4.369104)
Simple Copies          1.180000   0.010000   1.190000 (  1.227496)
Dup and In-Place       1.210000   0.010000   1.220000 (  1.240726)
Reverse and In-Place   1.130000   0.010000   1.140000 (  1.158873)
Hash and Compact       7.220000   0.090000   7.310000 (  7.552673)
---------------------------------------------- total: 15.150000sec

                            user     system      total        real
William James          4.230000   0.040000   4.270000 (  4.465252)
Simple Copies          1.190000   0.010000   1.200000 (  1.218064)
Dup and In-Place       1.220000   0.010000   1.230000 (  1.268994)
Reverse and In-Place   1.120000   0.010000   1.130000 (  1.152538)
Hash and Compact       7.220000   0.060000   7.280000 (  7.511923)


input = ["i", "v", "w", "e", "l", "d", "u", "f", "e", "v", "f", "e",  
"d", "e", "w", "d"]

require 'benchmark'
Benchmark.bmbm( 20 ) do |r|
   n = 100_000

   r.report( 'William James' ){
     n.times{
       out = []
       input.each{ |x| out.delete( x ); out << x }
     }
   }

   r.report( 'Simple Copies' ){
     n.times{
       input.reverse.uniq.reverse
     }
   }

   r.report( 'Dup and In-Place' ){
     n.times{
       out = input.dup
       out.reverse!
       out.uniq!
       out.reverse!
       out
     }
   }

   r.report( 'Reverse and In-Place' ){
     n.times{
       out = input.reverse
       out.uniq!
       out.reverse!
       out
     }
   }

   r.report( "Hash and Compact" ){
     n.times{
       seen = {}
       out = input.dup
       out.each_with_index{ |val,idx|
         if old_idx = seen[ val ]
           out[ old_idx ] = nil
         end
         seen[ val ] = idx
       }
     }
   }

end