MATLAB Central Newsreader - how to insert/delete rows in a matrix without copy the rest of matrix

how to insert/delete rows in a matrix without copy the rest of matrix

Chenyang — Wed, 25 Jul 2007 13:50:59 -0400

Matlab is very slow add/delete a row in a matrix.
It always trying to copy the whole matrix
e.g.,

a = rand(5000);
tic
a(:,1) = [];
toc
tic
a = [a(:,1),a];
toc
Elapsed time is 0.447241 seconds.
Elapsed time is 0.556416 seconds.

I need to insert/delete a row into a large matrix.
How to make it fast?

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Daphne W — Wed, 25 Jul 2007 15:03:46 -0400

The speed of the calculation partially depends on the system you're workin on.
On my laptop got
Elapsed time is 0.415618 seconds.
Elapsed time is 0.415288 seconds.
For your code.

Trying to do this faster, I simply redefined the a matrix without the first column as you have:

a=rand(5000);
tic; a=a(:,2:end); toc
Elapsed time is 0.250436 seconds.
Not great, but a bit better.

Daphne

"Chenyang " <john.doe.nospam@mathworks.com> wrote in
message <f87kg3$9ri$1@fred.mathworks.com>...
> Matlab is very slow add/delete a row in a matrix.
> It always trying to copy the whole matrix
> e.g.,
>
> a = rand(5000);
> tic
> a(:,1) = [];
> toc
> tic
> a = [a(:,1),a];
> toc
> Elapsed time is 0.447241 seconds.
> Elapsed time is 0.556416 seconds.
>
> I need to insert/delete a row into a large matrix.
> How to make it fast?
>

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Chenyang — Wed, 25 Jul 2007 16:20:01 -0400

Thank you, but this is not a "true" solution. The codes are just for illustration of the problem. What if you want to delete/add the 99th row?

The problem lies Matlab copying whole matrix while actually only a very small portion of the matrix being modified.
I guess to really solve this problem we have to find a data-structure that allows a matrix to span multiple memory segments and are somehow linked together by indexing pointers.

"Daphne W" <daphnew_too_nospam@yahoo.com> wrote in message <f87ooi$rma$1@fred.mathworks.com>...
>
> The speed of the calculation partially depends on the system you're workin on.
> On my laptop got
> Elapsed time is 0.415618 seconds.
> Elapsed time is 0.415288 seconds.
> For your code.
>
> Trying to do this faster, I simply redefined the a matrix without the first column as you have:
>
> a=rand(5000);
> tic; a=a(:,2:end); toc
> Elapsed time is 0.250436 seconds.
> Not great, but a bit better.
>
> Daphne
>
>
>
> "Chenyang " <john.doe.nospam@mathworks.com> wrote in
> message <f87kg3$9ri$1@fred.mathworks.com>...
> > Matlab is very slow add/delete a row in a matrix.
> > It always trying to copy the whole matrix
> > e.g.,
> >
> > a = rand(5000);
> > tic
> > a(:,1) = [];
> > toc
> > tic
> > a = [a(:,1),a];
> > toc
> > Elapsed time is 0.447241 seconds.
> > Elapsed time is 0.556416 seconds.
> >
> > I need to insert/delete a row into a large matrix.
> > How to make it fast?
> >
>

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Tim Davis — Wed, 25 Jul 2007 16:43:01 -0400

"Chenyang " <john.doe.nospam@mathworks.com> wrote in message <f87t7h$mje$1@fred.mathworks.com>...
> Thank you, but this is not a "true" solution. The codes are just for illustration of the problem. What if you want to delete/add the 99th row?
>
> The problem lies Matlab copying whole matrix while actually only a very small portion of the matrix being modified.
> I guess to really solve this problem we have to find a data-structure that allows a matrix to span multiple memory segments and are somehow linked together by indexing pointers.
>

MATLAB stores a dense matrix in an m-by-n array, in column major form, without pointers. Using pointers would cause a dreadful slowdown in any matrix computations other than

a (:,1) = [ ] ;

which is why no pointers are used (the BLAS do not use pointers).

So the problem is intrinsically difficult.

Your best solution would be to avoid the need to delete rows/columns at all. Can you set the row or column to delete to zero, for example?

Another alternative would be to keep a list of rows and columns that have not been "deleted", but not to change a itself. Try this:

a = rand (5000) ;

delrow = 99 ;

tic
b = [a(1:delrow-1,:) ; a(delrow+1:end,:)] ;
toc

tic
a (delrow,:) = [ ];
toc

[m n] = size (a)
p = logical (ones (m, 1)) ;
q = logical (ones (1, n)) ;
nrows = m ;
ncols = n ;

% to delete a row in a:
p (delrow) = 0 ;
nrows = nrows - 1 ;

% to delete a colum in a:
q (101) = 0 ;
ncols = ncols - 1 ;

tic
b = a(p,q) ;
toc

% try using a(p,q) explicitly:
x = rand (ncols,1) ;
tic
y = a(p,q) * x ;
toc

tic
y = b*x ;
toc

The logical indexing is a little faster.

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Robert — Wed, 25 Jul 2007 17:51:32 -0400

do you know a priori how large the matrix will be (or at least estimate an upper bound)? pre-allocating large structures is generally the solution for problems like this.

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Sterren Latsky — Thu, 08 Nov 2007 14:37:47 -0500

Hi guys. I have a similar query.

> MATLAB stores a dense matrix in an m-by-n array, in column
major form, without pointers. Using pointers would cause a
dreadful slowdown in any matrix computations other than
>
> a (:,1) = [ ] ;

I want to delete a row and column in an arbitrary position
in a very large matrix (up to 2000 rows / columns). The
matrix is a sparse matrix, so I am assuming it uses pointers
to non zero elements in rows and columns.
Theoretically, if it does this, there must be an easier way
to delete a row or column. Does anyone know how?

Thanks,

Sterren

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Tim Davis — Fri, 16 Nov 2007 02:30:02 -0500

"Sterren Latsky" <stez17@hotmail.com> wrote in message
<fgv6vr$d7c$1@fred.mathworks.com>...
> Hi guys. I have a similar query.
>
> > MATLAB stores a dense matrix in an m-by-n array, in column
> major form, without pointers. Using pointers would cause a
> dreadful slowdown in any matrix computations other than
> >
> > a (:,1) = [ ] ;
>
> I want to delete a row and column in an arbitrary position
> in a very large matrix (up to 2000 rows / columns). The
> matrix is a sparse matrix, so I am assuming it uses pointers
> to non zero elements in rows and columns.
> Theoretically, if it does this, there must be an easier way
> to delete a row or column. Does anyone know how?
>
> Thanks,
>
> Sterren

Check out Loren's March 1st blog for details of how MATLAB
stores its sparse matrices.

MATLAB stores its sparse matrices by column. Deleting a row
or column requires a complete copy of the matrix, even if
you were to do it in a C mexFunction. The data structure is
designed for fast whole-matrix operations, not for the (less
frequently used) a(:,1)=[] kind of operation.

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Kevin Lin — Sun, 18 Nov 2007 00:10:58 -0500

If I want to delete arbitrary m rows (for simplicity, say
m=2 and 3) in a matrix, what can I do? Thanks if any of you
can help.

"Tim Davis" <davis@cise.ufl.edu> wrote in message
<f87uil$ggh$1@fred.mathworks.com>...
> "Chenyang " <john.doe.nospam@mathworks.com> wrote in
message <f87t7h$mje$1@fred.mathworks.com>...
> > Thank you, but this is not a "true" solution. The codes
are just for illustration of the problem. What if you want
to delete/add the 99th row?
> >
> > The problem lies Matlab copying whole matrix while
actually only a very small portion of the matrix being modified.
> > I guess to really solve this problem we have to find a
data-structure that allows a matrix to span multiple memory
segments and are somehow linked together by indexing pointers.
> >
>
>
> MATLAB stores a dense matrix in an m-by-n array, in column
major form, without pointers. Using pointers would cause a
dreadful slowdown in any matrix computations other than
>
> a (:,1) = [ ] ;
>
> which is why no pointers are used (the BLAS do not use
pointers).
>
> So the problem is intrinsically difficult.
>
> Your best solution would be to avoid the need to delete
rows/columns at all. Can you set the row or column to
delete to zero, for example?
>
> Another alternative would be to keep a list of rows and
columns that have not been "deleted", but not to change a
itself. Try this:
>
> a = rand (5000) ;
>
> delrow = 99 ;
>
> tic
> b = [a(1:delrow-1,:) ; a(delrow+1:end,:)] ;
> toc
>
> tic
> a (delrow,:) = [ ];
> toc
>
> [m n] = size (a)
> p = logical (ones (m, 1)) ;
> q = logical (ones (1, n)) ;
> nrows = m ;
> ncols = n ;
>
> % to delete a row in a:
> p (delrow) = 0 ;
> nrows = nrows - 1 ;
>
> % to delete a colum in a:
> q (101) = 0 ;
> ncols = ncols - 1 ;
>
> tic
> b = a(p,q) ;
> toc
>
> % try using a(p,q) explicitly:
> x = rand (ncols,1) ;
> tic
> y = a(p,q) * x ;
> toc
>
> tic
> y = b*x ;
> toc
>
>
> The logical indexing is a little faster.

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Kevin Lin — Sun, 18 Nov 2007 00:14:41 -0500

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Kevin Lin — Sun, 18 Nov 2007 01:39:04 -0500

More precisely, suppose that matrix A has n rows. I want to
get all sub-matrices (the total number of sub-matrices
should be m choosing from n) by removing m rows from A.
Again, for simplicity, we can say m=2 or 3. Is there any
good way to code it in Matlab? Thanks.

"Kevin Lin" <klin@mathworks.com> wrote in message
<fho05h$3be$1@fred.mathworks.com>...
> If I want to delete arbitrary m rows (for simplicity, say
> m=2 and 3) in a matrix, what can I do? Thanks if any of you
> can help.
>
> "Tim Davis" <davis@cise.ufl.edu> wrote in message
> <f87uil$ggh$1@fred.mathworks.com>...
> > "Chenyang " <john.doe.nospam@mathworks.com> wrote in
> message <f87t7h$mje$1@fred.mathworks.com>...
> > > Thank you, but this is not a "true" solution. The codes
> are just for illustration of the problem. What if you want
> to delete/add the 99th row?
> > >
> > > The problem lies Matlab copying whole matrix while
> actually only a very small portion of the matrix being
modified.
> > > I guess to really solve this problem we have to find a
> data-structure that allows a matrix to span multiple memory
> segments and are somehow linked together by indexing
pointers.
> > >
> >
> >
> > MATLAB stores a dense matrix in an m-by-n array, in column
> major form, without pointers. Using pointers would cause a
> dreadful slowdown in any matrix computations other than
> >
> > a (:,1) = [ ] ;
> >
> > which is why no pointers are used (the BLAS do not use
> pointers).
> >
> > So the problem is intrinsically difficult.
> >
> > Your best solution would be to avoid the need to delete
> rows/columns at all. Can you set the row or column to
> delete to zero, for example?
> >
> > Another alternative would be to keep a list of rows and
> columns that have not been "deleted", but not to change a
> itself. Try this:
> >
> > a = rand (5000) ;
> >
> > delrow = 99 ;
> >
> > tic
> > b = [a(1:delrow-1,:) ; a(delrow+1:end,:)] ;
> > toc
> >
> > tic
> > a (delrow,:) = [ ];
> > toc
> >
> > [m n] = size (a)
> > p = logical (ones (m, 1)) ;
> > q = logical (ones (1, n)) ;
> > nrows = m ;
> > ncols = n ;
> >
> > % to delete a row in a:
> > p (delrow) = 0 ;
> > nrows = nrows - 1 ;
> >
> > % to delete a colum in a:
> > q (101) = 0 ;
> > ncols = ncols - 1 ;
> >
> > tic
> > b = a(p,q) ;
> > toc
> >
> > % try using a(p,q) explicitly:
> > x = rand (ncols,1) ;
> > tic
> > y = a(p,q) * x ;
> > toc
> >
> > tic
> > y = b*x ;
> > toc
> >
> >
> > The logical indexing is a little faster.
>

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Jens Christiansen — Mon, 21 Jul 2008 23:04:05 -0400

"Chenyang " <john.doe.nospam@mathworks.com> wrote in message
<f87kg3$9ri$1@fred.mathworks.com>...
> Matlab is very slow add/delete a row in a matrix.
> It always trying to copy the whole matrix
> e.g.,
>
> a = rand(5000);
> tic
> a(:,1) = [];
> toc
> tic
> a = [a(:,1),a];
> toc
> Elapsed time is 0.447241 seconds.
> Elapsed time is 0.556416 seconds.
>
> I need to insert/delete a row into a large matrix.
> How to make it fast?
>

One fast way of doing this is to first fill the rows with
zeros, and then delete them using the 'any' function as follows:

tic
x = rand(50000,10);
for i = 50000:-100:1
x(i,:) = [];
end
toc

>>Elapsed time is 4.813505 seconds.

tic
x = rand(50000,10);
for i = 50000:-100:1
x(i,:) = 0;
end
x(~any(x,2),:) = [];
toc

>>Elapsed time is 0.058070 seconds.

I cannot give a technical explanation for why the second
method is so much faster, but I would like to hear one if
anyone knows... I guess it has to do with the logical
indexing. My own problem was to delete very many irregularly
spaced rows from a matrix of app. the dimensions above, and
this method does the job very quickly.

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Peter Boettcher — Tue, 22 Jul 2008 13:21:44 -0400

"Jens Christiansen" <jenschristiansen@gmail.com> writes:

> "Chenyang " <john.doe.nospam@mathworks.com> wrote in message
> <f87kg3$9ri$1@fred.mathworks.com>...
>> Matlab is very slow add/delete a row in a matrix.
>> It always trying to copy the whole matrix
>> e.g.,
>>
>> a = rand(5000);
>> tic
>> a(:,1) = [];
>> toc
>> tic
>> a = [a(:,1),a];
>> toc
>> Elapsed time is 0.447241 seconds.
>> Elapsed time is 0.556416 seconds.
>>
>> I need to insert/delete a row into a large matrix.
>> How to make it fast?
>>
>
>
> One fast way of doing this is to first fill the rows with
> zeros, and then delete them using the 'any' function as follows:
>
> tic
> x = rand(50000,10);
> for i = 50000:-100:1
> x(i,:) = [];
> end
> toc
>
>>>Elapsed time is 4.813505 seconds.
>
> tic
> x = rand(50000,10);
> for i = 50000:-100:1
> x(i,:) = 0;
> end
> x(~any(x,2),:) = [];
> toc
>
>>>Elapsed time is 0.058070 seconds.
>
> I cannot give a technical explanation for why the second
> method is so much faster, but I would like to hear one if
> anyone knows... I guess it has to do with the logical
> indexing. My own problem was to delete very many irregularly
> spaced rows from a matrix of app. the dimensions above, and
> this method does the job very quickly.

I believe it has to do with memory reallocation / copying. Think of
deleting rows much like adding rows... if you don't preallocate, each
time you add elements, MATLAB is forced to reallocate memory to the new
larger size, and copy all the data over.

Your trick is like "preallocation" for deleting. In the loop you only
compute and save (in some manner) the rows to be deleted. Then the
actual delete happens at once, which means only a single reallocation.

My guess is that in this case, a "vectorized" delete would be even
faster. You really shouldn't time "rand", as that isn't part of the
delete process.

x1 = rand(50000,10);
x2 = rand(50000,10);

tic
for i = 50000:-100:1
x1(i,:) = 0;
end
x1(~any(x1,2),:) = [];
toc

tic
rows = 50000:-100:1;
x2(rows,:) = [];
toc

Elapsed time is 0.009575 seconds.
Elapsed time is 0.006921 seconds.

-Peter

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Jesse Sipple — Tue, 14 Jun 2011 19:04:04 -0400

You can just create a condition vector, then use that condition vector to remove the rows of your matrix

test=rand(500,3);
test(49,:)=0;
test(200,:)=0;

condition=test(:,1)==0;
test(condition,:)=[];

size(test)

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Henrique — Wed, 07 Sep 2011 19:52:28 -0400

tim davis;

you may be able to help me out. a 2007 posting of yours below is somewhat related to an issue i am having. if you have time, please see here;

http://www.mathworks.com/matlabcentral/answers/15316-joining-matrices-while-combining-columns

thanks in advance.

kiko

"Tim Davis" <davis@cise.ufl.edu> wrote in message <f87uil$ggh$1@fred.mathworks.com>...
> "Chenyang " <john.doe.nospam@mathworks.com> wrote in message <f87t7h$mje$1@fred.mathworks.com>...
> > Thank you, but this is not a "true" solution. The codes are just for illustration of the problem. What if you want to delete/add the 99th row?
> >
> > The problem lies Matlab copying whole matrix while actually only a very small portion of the matrix being modified.
> > I guess to really solve this problem we have to find a data-structure that allows a matrix to span multiple memory segments and are somehow linked together by indexing pointers.
> >
>
>
> MATLAB stores a dense matrix in an m-by-n array, in column major form, without pointers. Using pointers would cause a dreadful slowdown in any matrix computations other than
>
> a (:,1) = [ ] ;
>
> which is why no pointers are used (the BLAS do not use pointers).
>
> So the problem is intrinsically difficult.
>
> Your best solution would be to avoid the need to delete rows/columns at all. Can you set the row or column to delete to zero, for example?
>
> Another alternative would be to keep a list of rows and columns that have not been "deleted", but not to change a itself. Try this:
>
> a = rand (5000) ;
>
> delrow = 99 ;
>
> tic
> b = [a(1:delrow-1,:) ; a(delrow+1:end,:)] ;
> toc
>
> tic
> a (delrow,:) = [ ];
> toc
>
> [m n] = size (a)
> p = logical (ones (m, 1)) ;
> q = logical (ones (1, n)) ;
> nrows = m ;
> ncols = n ;
>
> % to delete a row in a:
> p (delrow) = 0 ;
> nrows = nrows - 1 ;
>
> % to delete a colum in a:
> q (101) = 0 ;
> ncols = ncols - 1 ;
>
> tic
> b = a(p,q) ;
> toc
>
> % try using a(p,q) explicitly:
> x = rand (ncols,1) ;
> tic
> y = a(p,q) * x ;
> toc
>
> tic
> y = b*x ;
> toc
>
>
> The logical indexing is a little faster.

Re: how to insert/delete rows in a matrix without copy the rest of matrix

Bruno Luong — Wed, 07 Sep 2011 20:33:29 -0400

"Henrique " <hademelo@mtu.edu> wrote in message <j48i1s$1t6$1@newscl01ah.mathworks.com>...
>
> tim davis;
>
> you may be able to help me out. a 2007 posting of yours below is somewhat related to an issue i am having. if you have time, please see here;
>
> http://www.mathworks.com/matlabcentral/answers/15316-joining-matrices-while-combining-columns
>

I'm no Tim, and exceptionally I'll answer to a question that is asked somewhere else (I think it's better to replicate the question here for the convenience).

% Data
A=1+zeros(6)
B=2+zeros(6)
C=3+zeros(6)
D=4+zeros(6)
E=5+zeros(6)
F=6+zeros(6)
ABC = cat(3,A,B,C)
DEF = cat(3,D,E,F)
% joint
% [A D;
% B E;
% C F];
% That's how we want the input to be:
I = cat(4,ABC,DEF)

% Engine, working on I
[m n p q] = size(I);
[R C] = ndgrid(1:m,1:n);
shift_r = (0:p-1)*4; % 4 is non ovelapping size < m
shift_c = (0:q-1)*4; % idem

R = bsxfun(@plus, R, reshape(shift_r, 1,1,[],1));
C = bsxfun(@plus, C, reshape(shift_c, 1,1,1,[]));
R = repmat(R, [1 1 1 q]);
C = repmat(C, [1 1 p 1]);
JOINT = accumarray([R(:) C(:)], I(:))./ accumarray([R(:) C(:)], 1)