Re: set functions

[etienne grossmann]

  Hello,


Date: Sat, 8 Jul 2000 11:35:45 +0100
From: Paul Kienzle <address@hidden>
#  More matlab like set functions, tens to hundreds of times faster than
#  the corresponding matlab functions:
#
#          unique, union, intersect, setdiff, setxor, ismember
#
#  The equivalent octave functions are:
#
#          create_set -> unique
#          intersection -> intersect
#          union -> union
#          complement(y,x) -> setdiff(y,x)
#
#  These are not exact equivalents.  The matlab functions return either
#  row or column vectors depending on their inputs whereas the octave
#  functions always return row vectors.  Neither handle the matlab
#  'rows' option.
#
#  Paul Kienzle
#  address@hidden

  Here are some speed comparison results. On this machine (Linux
2.2.15, Debian, PII 350, 128MB, Octave 2.1.30) it seems that only the
intersect () function presents an advantage. CPU time is measured
below, maybe other time measures would disagree :


#  Sizes             :  1      2      5      20     200    50000  500000
#  Octave create_set :  0.0022 0.0021 0.0021 0.0018 0.0029 0.3470 4.5840
#  Paul's unique     :  0.0022 0.0022 0.0023 0.0020 0.0033 0.4910 6.2740

#  Sizes               :  1      2      5      20     200    50000  500000
#  Octave intersection :  0.0041 0.0040 0.0042 0.0049 0.0102 4.6930 345.8660
#  Paul's intersect    :  0.0050 0.0054 0.0055 0.0057 0.0072 1.0180 13.0320

#  Sizes        :  1      2      5      20     200    50000  500000
#  Octave union :  0.0038 0.0039 0.0037 0.0038 0.0054 0.8190 10.5060
#  Paul's union :  0.0027 0.0028 0.0028 0.0030 0.0051 1.0660 13.4740


#  Sizes             :  1      2      5      20     200    50000  500000
#  Octave complement :  0.0046 0.0040 0.0039 0.0045 0.0084 4.1070 340.9080
#  Paul's setdiff    :  0.0041 0.0042 0.0045 0.0048 0.0082 4.1060 339.8560


======================================================================

  Here is one of the scripts that produced these figures :

======================================================================
## test_pkienzle_intersect.m
1;

ok_sz = ok_res = 1 ;

sizes =  [1,   2,   5,   20,  200,50000, 500000] ;
ntests = [500, 500, 500, 500, 100,10,    5];


t_pk = t_oct = zeros(1,columns(sizes));

for j = 1:columns(sizes),
  sz = sizes(j)
  
  for i = 1:ntests(j),
    ## x = find (randn (1,sz)<0);
    x = round (sz*rand (1,sz)/10);
    y = round (sz*rand (1,sz)/10);

    mytic ();
    xx = intersection (x,y) ;
    t_oct(j) += mytic ();

    mytic () ;
    yy = intersect (x,y);
    t_pk(j) += mytic ();

    if length (xx) != length (yy),
      ok_sz = 0 ;
    elseif any (xx(:) != yy(:)),
      ok_res = 0;
    end

  end

end
t_oct ./= ntests ;
t_pk ./= ntests ;
printf ("Sizes               : %s\n",sprintf (" %-6i",sizes));
printf ("Octave intersection : %s\n",sprintf (" %-6.4f",t_oct));
printf ("Paul's intersect    : %s\n",sprintf (" %-6.4f",t_pk));
printf ("OK : sizes %i,  Res : %i\n",ok_sz,ok_res);
======================================================================

  Mytic () is the function :

======================================================================
##       dt = mytic()
##
## Returns the cputime since last call to 'mytic'.
function dt = mytic()
   static last_mytic = 0 ;
   [t,u,s] = cputime() ;
   dt = t - last_mytic ;
   last_mytic = t ;
endfunction
======================================================================


  Cheers,

  Etienne



-----------------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.che.wisc.edu/octave/octave.html
How to fund new projects:  http://www.che.wisc.edu/octave/funding.html
Subscription information:  http://www.che.wisc.edu/octave/archive.html
-----------------------------------------------------------------------