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.