Re: cellfunc vs cell2mat speed?

[David Bateman]

Levente Torok wrote:
> Hi David,
>
> On Tuesday 09 September 2008, David Bateman wrote:
>   
> > Levente Torok wrote:
> >     
> > > Hi David and others
> > >
> > > This is small speed test:
> > >
> > > function t = test( s )
> > >
> > >     t = time;
> > >     c=cell( s, 1 );
> > >     r = rand( 8, 1 );
> > >     c{:,1} = r;
> > >     cc = cell2mat( c );
> > >     t = time - t;
> > >
> > > end
> > >
> > > octave:4> test( 1000 )
> > > ans =  0.27966
> > > octave:5> test( 10000 )
> > > ans =  12.347
> > > octave:6> test( 13000 )
> > > ans =  26.865
> > > octave:3> test( 16000 )
> > > ans =  47.761
> > > octave:4> test( 19000 )
> > > ans =  83.082
> > >
> > >
> > > As it seems, each adding of 3000 elements doubles the time it needs to convert 
> > > cell to matrix.
> > > I believe the slowness is due to the recursive scripting nature of the 
> > > cell2mat.m function.
> > > I thought I will write a small conversion program in C with limited capabilities for my own needs 
> > > ( ie. only c{i,1} =matrix will be handled ) but I am so much confused with the interface of the 
> > > Cell class.
> > >
> > >
> > > ( NB: if I replace cell2mat with cellfun( c, "mean" ) I would get:
> > > octave:10> test( 20000 )
> > > ans =  8.0793
> > > and this increases linearly with size of the cell array)
> > > Thank you very much in advance,
> > >
> > > Levente
> > >
> > >
> > >
> > >
> > >   
> > >       
> > The code that handles this is essentially
> >
> >  t = cputime; cc = cat(1, c{:}); cputime - t
> >     
> I replaced it. This is just a little bit better now:
>
> octave:2> test( 10000 )
> ans =  9.3086
> octave:3> test( 13000 )
> ans =  20.437
> octave:4> test( 16000 )
> ans =  39.590
> The trend is the same.
>
>   
> > There are two issues with the above. The first is that the cat function 
> > is called with an enormously large number of arguments and the second is 
> > that the cat function, unlikely [], doesn't make any specializations for 
> > the same class of data in the concatenation. Compare the above with
> >
> > t = cputime; cc = [c{:}]; cputime - t;
> >     
>
> octave:7> test( 40000 )
> ans =  0.30402
>
> This is extremely fast however it does not do the thing I want since it 
> concatenates the
> columns rowwise rather than columnwise. ie.
> c=cell(2,1)
> c{1} = [ 1;2 ; 3];
> c{2} = [ 4;2 ; 3];
> octave:12> [c{:}]
> ans =
>
>    1   4
>    2   2
>    3   3
>
> It wouldn't be the problem if I wouldn't need to handle vectors of different 
> sizes, hence I cannot use
> reshape to it. Isn't there such a simple expression to do column wise 
> concatenation?
>
>   
Yes something like

function c = mycell2mat (c)
 k = 1;
 while (numel (c) > 1)
   n = rows (c);
   if (n == 1)
     if (ndims (c) == 2)
   c = reshape (c, [numel(c), 1]);
     else
   c = reshape (c, size(c)(2:end));
     endif
   else
     sz = size (c)(2 : end);
     if (isscalar (sz))
   c1 = cell ([sz, 1]);
     else
   c1 = cell (sz);
   sz = prod (sz);
     endif
     if (k == 2)
   for i = 1 : sz
     c1{i} = [c{(i - 1) * n + (1 : n)}];
   endfor
     else
   ## This is faster than
   ##   for i = 1:sz, c1{i} = cat (k, c{(i - 1) * n + (1 : n)}); endfor
   idx = 1 : ndims(c);
   idx(k) = idx (2);
   idx(2) = k;
   c = cellfun(@(x) permute (x, idx), c, "UniformOutput", false);
   for i = 1:sz
     c1{i} = ipermute ([c{(i - 1) * n + (1 : n)}], idx);
   endfor
     endif
     c = c1;
   endif
   k++;
 endwhile
 c = [c{:}];
endfunction


is generic. Though the case of "k=1" could be vastly accelerated if 
there existed a transpose opertaor of a cs-list that created a 
semi-colon separated list. I don't think it exists, so maybe the above 
is the best we can do without reworking the "cat" function to make the 
same speedups as the "[]" code.

D.