Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!f10g2000hsf.googlegroups.com!not-for-mail
From: Pietro <pietromas@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Optimize this!
Date: Sat, 9 Feb 2008 15:13:18 -0800 (PST)
Organization: http://groups.google.com
Lines: 197
Message-ID: <f64ac0c4-b7f2-48fd-a694-6ba8ababe6a5@f10g2000hsf.googlegroups.com>
References: <5b74607b-c527-4c9b-833a-b08d4be5d48a@s13g2000prd.googlegroups.com> 
NNTP-Posting-Host: 87.74.179.93
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1202598798 21198 127.0.0.1 (9 Feb 2008 23:13:18 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sat, 9 Feb 2008 23:13:18 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: f10g2000hsf.googlegroups.com; posting-host=87.74.179.93; 
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (X11; U; Linux i686 (x86_64); en-US; rv:1.8.1.9) 
Xref: news.mathworks.com comp.soft-sys.matlab:450379




us  wrote:
> Pietro:
> <SNIP fast re-indexing...
>
> well, well...
> since the order does not matter, one might look a bit
> further and come up with an even faster (2-line) solution...
> the code snippet below shows its performance AND uncovers
> that <tc> solutions may get very slow and sometimes be
> incorrect(!?)
>
> the code (copy/pasted) from previous posts
>
> function t=foo
>      fmt={
>           '%5d %5d = %3.0f'
>           '%11.3f %11.3f  '
>           'isequal: %-1d %-1d'
>      };
>      nt=10;
>      t=zeros(nt,7);
> for  k=1:nt
>      a=ceil(rand(10^4,1)*10^k).'; % integers
> % ***** jd *****
>      tic;
>      [b,J,J]=unique(a);
>      t(k,3)=toc;
> try % look out for memory problems
> % ***** tc *****
>      vec=a;
>      tic;
>      x = zeros(max(vec)-min(vec)+1,1) + nan;
>      x(vec) = 1;
>      nu = sum(~isnan(x));
>      x(~isnan(x)) = 1:nu;
>      y = x(vec);
>      t(k,4)=toc;
> catch
>      t(k,4)=nan;
>      y=J.';
> end
> % ***** us *****
>      tic;
>      [as,ax]=sort(a);
>      as(ax)=cumsum([1,diff(as)]~=0);
>      t(k,5)=toc;
> % run-time result
>      t(k,1:2)=[numel(a),numel(b)];
>      t(k,6:7)=[isequal(J,y.'),isequal(J,as)];
>      t(k,3:5)=100*t(k,3:5)./t(k,3);
>      disp(sprintf([fmt{:}],t(k,:)));
> end
> end
>
> output on a wintel system c2.2*2.4/2gb/vista/r2007b (look
> at it in the original version for proper formatting...)
>
> 1) using the ~original input
>      a=[3 7 2 2 3 100 7 7 56];
> veclen uniquelen jd=100% tc% us% equal(jd,tc) equal(jd,us)
>     9     5 = 100     46.076      13.029  isequal: 1 1
>
> 2) using the loop, however
>
> 10000    10 = 100     43.648      96.747  isequal: 1 1
> 10000   100 = 100     30.893      76.001  isequal: 1 1
> 10000  1000 = 100     38.042      77.902  isequal: 1 1
> 10000  6366 = 100    108.570      70.773  isequal: 1 1
> 10000  9521 = 100   1261.356      68.274  isequal: 0 1 !
> 10000  9950 = 100  12899.902      66.274  isequal: 0 1 !
> 10000  9997 = 100 125642.159      64.475  isequal: 0 1 !
> 10000 10000 = 100        NaN      75.425  isequal: 1 1
> 10000 10000 = 100        NaN      69.354  isequal: 1 1
> 10000 10000 = 100        NaN      73.868  isequal: 1 1
>
> just a few thoughts...
> us

On 8 Feb, 22:46, "us " <u...@neurol.unizh.ch> wrote:
> Pietro:
> <SNIP fast re-indexing...
>
> well, well...
> since the order does not matter, one might look a bit
> further and come up with an even faster (2-line) solution...
> the code snippet below shows its performance AND uncovers
> that <tc> solutions may get very slow and sometimes be
> incorrect(!?)
>
> the code (copy/pasted) from previous posts
>
> function t=foo
>      fmt={
>           '%5d %5d = %3.0f'
>           '%11.3f %11.3f  '
>           'isequal: %-1d %-1d'
>      };
>      nt=10;
>      t=zeros(nt,7);
> for  k=1:nt
>      a=ceil(rand(10^4,1)*10^k).'; % integers
> % ***** jd *****
>      tic;
>      [b,J,J]=unique(a);
>      t(k,3)=toc;
> try % look out for memory problems
> % ***** tc *****
>      vec=a;
>      tic;
>      x = zeros(max(vec)-min(vec)+1,1) + nan;
>      x(vec) = 1;
>      nu = sum(~isnan(x));
>      x(~isnan(x)) = 1:nu;
>      y = x(vec);
>      t(k,4)=toc;
> catch
>      t(k,4)=nan;
>      y=J.';
> end
> % ***** us *****
>      tic;
>      [as,ax]=sort(a);
>      as(ax)=cumsum([1,diff(as)]~=0);
>      t(k,5)=toc;
> % run-time result
>      t(k,1:2)=[numel(a),numel(b)];
>      t(k,6:7)=[isequal(J,y.'),isequal(J,as)];
>      t(k,3:5)=100*t(k,3:5)./t(k,3);
>      disp(sprintf([fmt{:}],t(k,:)));
> end
> end
>
> output on a wintel system c2.2*2.4/2gb/vista/r2007b (look
> at it in the original version for proper formatting...)
>
> 1) using the ~original input
>      a=[3 7 2 2 3 100 7 7 56];
> veclen uniquelen jd=100% tc% us% equal(jd,tc) equal(jd,us)
>     9     5 = 100     46.076      13.029  isequal: 1 1
>
> 2) using the loop, however
>
> 10000    10 = 100     43.648      96.747  isequal: 1 1
> 10000   100 = 100     30.893      76.001  isequal: 1 1
> 10000  1000 = 100     38.042      77.902  isequal: 1 1
> 10000  6366 = 100    108.570      70.773  isequal: 1 1
> 10000  9521 = 100   1261.356      68.274  isequal: 0 1 !
> 10000  9950 = 100  12899.902      66.274  isequal: 0 1 !
> 10000  9997 = 100 125642.159      64.475  isequal: 0 1 !
> 10000 10000 = 100        NaN      75.425  isequal: 1 1
> 10000 10000 = 100        NaN      69.354  isequal: 1 1
> 10000 10000 = 100        NaN      73.868  isequal: 1 1
>
> just a few thoughts...
> us

Thanks. That was helpful.

In my particular case I think the dominant factor is the size of the
input vector. I expect the values to be distributed between 1 and 1e7
give or take so this is the range I am testing with. By varying the
length of the vector I got these results (real time shown in brackets)

       10        10 = 100 (5.360000e-04)  72826.119 (3.903480e-01)
265.299 (1.422000e-03)  isequal: 1 1
      100        99 = 100 (2.780000e-04) 135831.655
(3.776120e-01)      31.655 (8.800000e-05)  isequal: 1 1
     1000       958 = 100 (2.312500e-02)   1688.004
(3.903510e-01)       0.843 (1.950000e-04)  isequal: 1 1
    10000      6294 = 100 (2.038300e-02)   1922.337
(3.918300e-01)      10.293 (2.098000e-03)  isequal: 1 1
   100000      9990 = 100 (3.631300e-02)   1107.595
(4.022010e-01)      82.676 (3.002200e-02)  isequal: 1 1
  1000000      9990 = 100 (5.138290e-01)     99.105
(5.092280e-01)      86.513 (4.445300e-01)  isequal: 1 1
 10000000      9996 = 100 (1.077124e+01)     24.823 (2.673767e
+00)      97.074 (1.045604e+01)  isequal: 1 1

This is how I generate the input:

a = round(rand(10 ^ k, 1) * (1e4 - 1)) + 1; % generate 10^k elements,
with frequency of 10^(k-4)
tmp = round(rand(1, 1e4) * 10 ^ 7) + 1; % distributed between 1 and
10^ 7
a = tmp(a);
clear tmp;

Its hard to tell what to do. My vectors could be a million or two
long, but they could also be much much smaller. I suppose I should
dynamically select a method based on the length of the input.

Cheers.

P.S.
Is there a difference between A' and A.' ?