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

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?

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?
>

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?
> >
>

"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.

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.

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

"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.

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.

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.

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.
>

"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.

"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