From: borchers@... (Hans W. Borchers)
Date: 2002-03-21T18:05:20+09:00
Subject: Re: Why is Ruby so slow? - Solution

Dear All,

I am still wondering why it can be so slow in some cases? In my
example it took almost 30 secs to remove one element from a list
of 50000 items. And this one element was not even existing in the
array.

Trying to avoid traversing the list myself I now use:

    nitms = @col[j].uniq.nitems
    nitms -= 1 if mitms > 0  # i.e., if there are missing values

That is speed enough. Going through the list with a hash 'by hand'
and then counting keys was almost as fast (5 secs more).

So what slows it down so much when going through the list twice?

Hans Werner.

> > > 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