cellfunc vs cell2mat speed?

12 messages
Open this post in threaded view
|

cellfunc vs cell2mat speed?

 Hi All, I am just wondering why is it so difficult to convert a cell array to matrix? I used cellfunc on  cell array of 59000 cells which took 7 seconds but the conversion to a matrix of size 443320 , 7 took about 1080 seconds on my machine. The cell2mat on the same data took appx 150 times more time. I am just shocked. Should I replace the original cell2mat with a C routine? Lev -- Blogger of http://fapuma.blogspot.com_______________________________________________ Help-octave mailing list [hidden email] https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Open this post in threaded view
|

Re: cellfunc vs cell2mat speed?

 Levente Torok wrote: > Hi All, > > I am just wondering why is it so difficult to convert a cell array to matrix? > > I used cellfunc on  cell array of 59000 cells which took 7 seconds > but the conversion to a matrix of size > 443320 , 7 > took about 1080 seconds on my machine. > > The cell2mat on the same data took appx 150 times more time. > I am just shocked. Should I replace the original cell2mat with a C routine? > > Lev > Short example please. The above is not much use as a bug report. D. _______________________________________________ Help-octave mailing list [hidden email] https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Open this post in threaded view
|

Re: cellfunc vs cell2mat speed?

 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 -- Blogger of http://fapuma.blogspot.com_______________________________________________ Help-octave mailing list [hidden email] https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Open this post in threaded view
|

Re: cellfunc vs cell2mat speed?

 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 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; I'm working on a fix.. D. _______________________________________________ Help-octave mailing list [hidden email] https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Open this post in threaded view
|

Re: cellfunc vs cell2mat speed?

 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? > I'm working on a fix.. Thank you very much in advance. Lev -- Blogger of http://fapuma.blogspot.com_______________________________________________ Help-octave mailing list [hidden email] https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Open this post in threaded view
|

Re: cellfunc vs cell2mat speed?

 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. _______________________________________________ Help-octave mailing list [hidden email] https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Open this post in threaded view
|

[Changeset} Re: cellfunc vs cell2mat speed?

 I'd suggest something like teh attached changeset that improves the speed but keeps teh code compatible. D. # HG changeset patch # User David Bateman <[hidden email]> # Date 1221002489 -7200 # Node ID 7bd7ce1d2634dab6969acc76af0de702f9eb222f # Parent  eb774ade7516a05fdc6a3dec59eaa15ab1827ddd improve speed of cell2mat diff --git a/scripts/ChangeLog b/scripts/ChangeLog --- a/scripts/ChangeLog +++ b/scripts/ChangeLog @@ -1,3 +1,7 @@ 2008-09-09  John W. Eaton  <[hidden email] +2008-09-09  David Bateman  <[hidden email]> + + * general/cell2mat.m: Improve the speed.. +  2008-09-09  John W. Eaton  <[hidden email]>     * time/datestr.m: Convert format and use strftime to do most of diff --git a/scripts/general/cell2mat.m b/scripts/general/cell2mat.m --- a/scripts/general/cell2mat.m +++ b/scripts/general/cell2mat.m @@ -48,20 +48,46 @@ function m = cell2mat (c)      else        error ("cell2mat: all elements of cell array must be numeric, logical or char");      endif +  elseif (ndims (c) == 2) +    nr = rows (c); +    c1 = cell (nr, 1); +    for i = 1 : nr +      c1{i} = [c{i : nr : end}]; +    endfor +    ## This is faster than "c = cat(1, c{:})" +    c = [cellfun(@(x) x.', c1, "UniformOutput", false){:}].';    else -    ## n dimensions case -    for k = ndims (c):-1:2, +   nd = ndims (c); +   for k = nd : -1 : 2        sz = size (c); +      if (k > ndims (c) || sz(end) == 1) + continue; +      endif        sz(end) = 1;        c1 = cell (sz); -      for i = 1:(prod (sz)) -        c1{i} = cat (k, c{i:(prod (sz)):end}); -      endfor +      sz = prod (sz); +      if (k == 2) +        for i = 1 : sz +  c1{i} = [c{i : sz : end}]; +        endfor +      else +        ## This is faster than +        ##   for i = 1:sz, c1{i} = cat (k, c{i:(prod (sz)):end}); endfor + idx = [1, k, (3 : (k - 1)), 2, ((k + 1): nd)]; +        c = cellfun(@(x) permute (x, idx), c, "UniformOutput", false); +        for i = 1: sz +  c1{i} = ipermute ([c{i : sz : end}], idx); +        endfor +      endif        c = c1;      endfor -    m = cat (1, c1{:}); +    if (numel (c) > 1) +      idx = [2, 1, 3 : nd]; +      c = ipermute([cellfun(@(x) permute (x, idx), c, "UniformOutput", false){:}], idx); +    else +      c = c{1}; +    endif    endif -  endfunction    ## Tests _______________________________________________ Help-octave mailing list [hidden email] https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Open this post in threaded view
|

[Changeset} Re: cellfunc vs cell2mat speed?

 On 10-Sep-2008, David Bateman wrote: | I'd suggest something like teh attached changeset that improves the | speed but keeps teh code compatible. Thanks, I applied it along with the additional change you sent off the list.  The combined change is attached below as a single changeset. jwe # HG changeset patch # User David Bateman <[hidden email]> # Date 1221167006 14400 # Node ID 3b2346046d32ad8a819b26236c575a6fc2a1436a # Parent  c066714ee5d53d68fe5db9c69f2e47b8edfaab14 improve speed of cell2mat diff --git a/scripts/ChangeLog b/scripts/ChangeLog --- a/scripts/ChangeLog +++ b/scripts/ChangeLog @@ -1,3 +1,7 @@ +2008-09-11  David Bateman  <[hidden email]> + + * general/cell2mat.m: Improve the speed. +  2008-09-09  John W. Eaton  <[hidden email]>     * time/datestr.m: Convert format and use strftime to do most of diff --git a/scripts/general/cell2mat.m b/scripts/general/cell2mat.m --- a/scripts/general/cell2mat.m +++ b/scripts/general/cell2mat.m @@ -48,20 +48,46 @@      else        error ("cell2mat: all elements of cell array must be numeric, logical or char");      endif +  elseif (ndims (c) == 2) +    nr = rows (c); +    c1 = cell (nr, 1); +    for i = 1 : nr +      c1{i} = [c{i : nr : end}]; +    endfor +    ## This is faster than "c = cat(1, c{:})" +    m = [cellfun(@(x) x.', c1, "UniformOutput", false){:}].';    else -    ## n dimensions case -    for k = ndims (c):-1:2, +   nd = ndims (c); +   for k = nd : -1 : 2        sz = size (c); +      if (k > ndims (c) || sz(end) == 1) + continue; +      endif        sz(end) = 1;        c1 = cell (sz); -      for i = 1:(prod (sz)) -        c1{i} = cat (k, c{i:(prod (sz)):end}); -      endfor +      sz = prod (sz); +      if (k == 2) +        for i = 1 : sz +  c1{i} = [c{i : sz : end}]; +        endfor +      else +        ## This is faster than +        ##   for i = 1:sz, c1{i} = cat (k, c{i:(prod (sz)):end}); endfor + idx = [1, k, (3 : (k - 1)), 2, ((k + 1): nd)]; +        c = cellfun(@(x) permute (x, idx), c, "UniformOutput", false); +        for i = 1: sz +  c1{i} = ipermute ([c{i : sz : end}], idx); +        endfor +      endif        c = c1;      endfor -    m = cat (1, c1{:}); +    if (numel (c) > 1) +      idx = [2, 1, 3 : nd]; +      m = ipermute([cellfun(@(x) permute (x, idx), c, "UniformOutput", false){:}], idx); +    else +      m = c{1}; +    endif    endif -  endfunction    ## Tests _______________________________________________ Help-octave mailing list [hidden email] https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
Open this post in threaded view
|

Re: [Changeset} Re: cellfunc vs cell2mat speed?

Open this post in threaded view
|

Re: [Changeset} Re: cellfunc vs cell2mat speed?

 On 15-Sep-2008, David Bateman wrote: | John W. Eaton wrote: | > On 10-Sep-2008, David Bateman wrote: | > | > | I'd suggest something like teh attached changeset that improves the | > | speed but keeps teh code compatible. | > | > Thanks, I applied it along with the additional change you sent | > off the list.  The combined change is attached below as a single | > changeset. | > | > jwe | > | >   | | Thinking about this further we should in fact have single type | concatenation specializations in Fcat as well in the same manner as in | pt-mat.cc. The attached patch does this and then reworks cell2mat again | for even better speed. I applied this changeset. Thanks, jwe _______________________________________________ Help-octave mailing list [hidden email] https://www-old.cae.wisc.edu/mailman/listinfo/help-octave