On Tue, May 5, 2009 at 7:56 PM, Francisco J. Martínez Serrano <[email protected]> wrote: > On Tue, May 5, 2009 at 1:49 PM, Jaroslav Hajek <[email protected]> wrote: >> Why do you think so? Can you elaborate? > > While I think both algorithms are O(N), my proposal is more > "vector-like", thus cpu-friendly. At least with non-sparse matrices:
In fact, I think neither one is O(N). It can't even be O(N) with general data, given that the output should be sorted. > > octave:18> a=magic(1000)(:);b=magic(200)(:); > octave:19> tic;setdiff(a,b);toc > Elapsed time is 0.764591 seconds. > octave:20> tic;setdiff2(a,b);toc > Elapsed time is 0.448301 seconds. > > It is not such a big deal, anyway, unless you want to do huge setdiffs. > Here is what I get with development ver: octave:1> a=magic(1000)(:);b=magic(200)(:); octave:2> tic;setdiff(a,b);toc Elapsed time is 0.206671 seconds. octave:3> tic;setdiff2(a,b);toc Elapsed time is 0.218514 seconds. Benchmarking 3.0.x is now virtually useless whenever indexing or sorting plays a major part. Besides, I do not consider the case above to be representative. When you work with sets in Octave, they're usually kept sorted, so it's likely that in "setdiff", at least a will be sorted and uniquified. So: octave:1> a=unique(magic(1000)(:));b=magic(200)(:); octave:2> tic;setdiff(a,b);toc Elapsed time is 0.0681071 seconds. octave:3> tic;setdiff2(a,b);toc Elapsed time is 0.135171 seconds. I'll be glad if you're interested in improving Octave's performance, but that seriously needs you work with development sources. Cheers -- RNDr. Jaroslav Hajek computing expert & GNU Octave developer Aeronautical Research and Test Institute (VZLU) Prague, Czech Republic url: www.highegg.matfyz.cz ------------------------------------------------------------------------------ The NEW KODAK i700 Series Scanners deliver under ANY circumstances! Your production scanning environment may not be a perfect world - but thanks to Kodak, there's a perfect scanner to get the job done! With the NEW KODAK i700 Series Scanner you'll get full speed at 300 dpi even with all image processing features enabled. http://p.sf.net/sfu/kodak-com _______________________________________________ Octave-dev mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/octave-dev
