From: Ezra Zygmuntowicz <ezmobius@...>
Date: 2007-07-12T10:20:58+09:00
Subject: Re: Returning part of a hash


On Jul 11, 2007, at 5:18 PM, Stefan Rusterholz wrote:

>> That said,
>> if you really want to make it O(n+m) (or so, and that's a +  
>> instead of a
>> *) you put the arguments list in a hash (which makes the include?  
>> call
>> O(1) instead of O(m)). That probably isn't a win until m is more than
>> three
>> (or maybe more, it would require benchmarking to find the magic  
>> number),
>> though.
>>
>>> Regards
>>> Stefan
>> --Greg
>
> Since this is a generic method one can't know how it will be used, so
> I'd go for scalability over speed in some anticipated cases. But  
> that's
> me.
> You can do it in O(n) (n = keys.length) and I'd even assume that way
> will be faster than the O(m*n) for small n's since the hash is most
> likely longer than the keys-array.
> The O(n) variant simply iterates over the keys and builds up the hash
> from that.
>
> But actually I really just wondered if he was aware about the  
> complexity
> of his algorithm :)
>
> Excuse any bad english please, it's a bit late here and english  
> isn't my
> first language.
>
> Regards
> Stefan


	Yeah I was aware of the complexity. But for what I use it for it's  
actually faster then the other way. I mostly use these methods in web  
apps to reject or accept keys out of the params hash> Like for  
logging the params but blocking any password fields. So the rejected  
keys are usually only one or two in number and the whole has usually  
has ~10 items in it.


	Benchmarking this you will see that block1 is faster then block2 for  
the cases I use it for:

class Hash

   def block1(*rejected)
     self.reject { |k,v|  rejected.include?(k) }
   end

   def block2(*rejected)
     hsh = rejected.inject({}){|m,k| m[k] = true; m}
     self.reject { |k,v| hsh[k] }
   end

end

require 'benchmark'

hash = {:foo => 'foo',
         :bar => 'bar',
         :baz => 'baz',
         :foo1 => 'foo1',
         :bar1 => 'bar1',
         :baz1 => 'baz1',
         :foo2 => 'foo2',
         :bar2 => 'bar2',
         :baz2 => 'baz2'
         }

n = 50000
Benchmark.bm do |x|
   puts "block1"
   x.report { n.times{ hash.block1(:foo) } }
   x.report { n.times{ hash.block1(:foo,:bar) } }
   x.report { n.times{ hash.block1(:foo, :bar, :baz) } }
   x.report { n.times{ hash.block1(:foo, :bar, :baz,:foo1) } }
   x.report { n.times{ hash.block1(:foo, :bar, :baz,:foo1, :bar2) } }
   x.report { n.times{ hash.block1 
(:foo, :bar, :baz,:foo1, :bar2, :baz2) } }
   x.report { n.times{ hash.block1 
(:foo, :bar, :baz,:foo1, :bar2, :baz2, :foo3) } }
   x.report { n.times{ hash.block1 
(:foo, :bar, :baz,:foo1, :bar2, :baz2, :foo3, :bar3) } }
   x.report { n.times{ hash.block1 
(:foo, :bar, :baz,:foo1, :bar2, :baz2, :foo3, :bar3, :baz3) } }

   puts "block2"
   x.report { n.times{ hash.block2(:foo) } }
   x.report { n.times{ hash.block2(:foo,:bar) } }
   x.report { n.times{ hash.block2(:foo, :bar, :baz) } }
   x.report { n.times{ hash.block2(:foo, :bar, :baz,:foo1) } }
   x.report { n.times{ hash.block2(:foo, :bar, :baz,:foo1, :bar2) } }
   x.report { n.times{ hash.block2 
(:foo, :bar, :baz,:foo1, :bar2, :baz2) } }
   x.report { n.times{ hash.block2 
(:foo, :bar, :baz,:foo1, :bar2, :baz2, :foo3) } }
   x.report { n.times{ hash.block2 
(:foo, :bar, :baz,:foo1, :bar2, :baz2, :foo3, :bar3) } }
   x.report { n.times{ hash.block2 
(:foo, :bar, :baz,:foo1, :bar2, :baz2, :foo3, :bar3, :baz3) } }
end



Cheers-
-- Ezra