[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: fast set operations
From: |
Jaroslav Hajek |
Subject: |
Re: fast set operations |
Date: |
Sat, 9 Aug 2008 19:32:35 +0200 |
On Sat, Aug 9, 2008 at 4:40 PM, Levente Torok <address@hidden> 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