fast set operations

[Jaroslav Hajek]

On Sat, Aug 9, 2008 at 4:40 PM, Levente Torok <toroklev at gmail.com> wrote:
> Dear All,
>
> I was in the need to have a fast set operations such as intersection and complement but the
> those that I could use with the current octave versions (<3.0) are very very slow to my needs.

Well, set operations are not a typical bottleneck in computations
people employ Octave for, so there's not much demand for improvement.
Still, 2.9.x series are quite old - benchmarking should be done
against development version (or a recent snapshot at least) to be of
any value. There have been improvements to set functions since (though
mostly for functionality rather than performance) and to sorting
(which may make a significant difference).

> For this reason I wrote a version in STL C++.

OK, but if I were to do that, I'd simply wrap set_intersection from <algorithm>.

> May be not optimal in terms of strorage (I convert everything to STL vector since it has fast iterators)
> however this is still 100-500 times faster for vectors with 10^5 elements, at least,
> than the versions currently supplied by octave. I enclose the sources.
>

If you have any interest, I can test this against development version
if I have the time. 100-500 is too much; if this is still true, we
should improve something.
Also note that if the set sizes are not asymptotically equal, then
your approach is sub-optimal. (Instead of O(N*log(N) + M*log(M)) you
can easily get O(N*log(N)+M))

regards,



-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz