[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

new set functions

From: Lippert, Ross A.
Subject: new set functions
Date: Wed, 15 Nov 2000 09:52:44 -0500

I have made a modification to create_set because I found myself
often wanting not just the set of unique elements but also the
counts of those elements in the original input.  Perhaps that is
just my own eccentricity.

However, if one modifies create_set in this way (returning a
second output of counts), then I believe that the runtime complexity
of intersection and complement can be reduced to n log n instead of
n^2 (which they appear to be now, but I am no expert on complexity).

Anyhow, as a quick example I tried 
x = fix(20000*rand(1000,1)); y = fix(20000*rand(1000,1));

and found a big difference between the timings of
intersection(x,y), so I think I am on the right track.

I'd be sending this out in the form of a patch, but for the moment,
I'd really like feedback to tell me if I have done something stupid
so I don't waste time updating my CVS, installing the new scripts 
and then diffing all to find out I missed something.


Attachment: set.tgz
Description: Binary data

reply via email to

[Prev in Thread] Current Thread [Next in Thread]