Gregory Seidman wrote:
> On Thu, Jul 12, 2007 at 06:34:31AM +0900, Stefan Rusterholz wrote:
>> > 
>> >    # blocks the keys in the arguments
>> >    # >> {:one => 1, :two => 2, :three => 3}.block(:one)
>> >    # => {:two=>2, :three=>3}
>> >    def block(*keys)
>> >      self.reject { |k,v| keys.include?(k) }
>> >    end
>> > end
>> 
>> I wonder, are you aware that those are O(n^2)?
> 
> Actually, they are O(n*m) since the size of the arguments array is 
> (almost
> certainly) different from and smaller than the size of the hash.

IIRC we generally refered to O(m*n) as O(n^2) too, but can be that I 
remember wrongly. Anyway, O(m*n) is certainly more precise.

> 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

-- 
Posted via http://www.ruby-forum.com/.