From: nobu.nokada@...
Date: 2002-03-20T22:32:14+09:00
Subject: Re: Why is Ruby so slow? - Solution

Hi,

At Wed, 20 Mar 2002 21:42:19 +0900,
Ron Jeffries wrote:
> >Yes, current implementation is optimized for bigger arrays, it
> >takes O(N+M) time, but former was O(N*M), where arrays with N
> >and M size.  Perhaps, in this case, GC occurred several times
> >per each loops by 1,600,000 items hashes.
> 
> I'm curious. How do you do this operation in O(N+M)?

Once making a hash whose keys are the minuend's elements, and
remove the subtrahend's elements from it.  At last, for all the
minuend's elements, add it to the result array if it is
contained in the hash.  Oops, sorry, it was O(2*N+M).

-- 
Nobu Nakada