Thread Subject: Efficient remove of first or last element in vector

Hello to all,

Can anyone suggest an efficient wat to remove one element in vector?
Thea easy part is that is for example first element.
One way to do it is something like this.

x = [1,2,3,4,5,6,7];
y = x(2:length(x));

but it is not really efficient because of length() function call. Is
there some other and more efficient way?

I need to remove first element in my vector because first element is
due to some earlier processing either minimal or maximal element in my
data series. I need to either remove this element or set it to average
for example.

I also tried with and max function that returnd ivdex of minimal or
maximal element in a vector, but not sure how to use it efficiently
because I have a really big vector.

Thank for help

AsimV wrote:
> Can anyone suggest an efficient wat to remove one element in vector?
> Thea easy part is that is for example first element.
> One way to do it is something like this.
>
> x = [1,2,3,4,5,6,7];
> y = x(2:length(x));

y = x(2:end);

Or

y = x; y(1) = [];

AsimV <asimvod@gmail.com> wrote in message <9f3fe49a-73db-4253-918b-0cbbdd748ba7@q18g2000vbn.googlegroups.com>...
> Hello to all,
>
> Can anyone suggest an efficient wat to remove one element in vector?
> Thea easy part is that is for example first element.
> One way to do it is something like this.
>
> x = [1,2,3,4,5,6,7];
> y = x(2:length(x));
>
> but it is not really efficient because of length() function call. Is
> there some other and more efficient way?
>
> I need to remove first element in my vector because first element is
> due to some earlier processing either minimal or maximal element in my
> data series. I need to either remove this element or set it to average
> for example.
>
> I also tried with and max function that returnd ivdex of minimal or
> maximal element in a vector, but not sure how to use it efficiently
> because I have a really big vector.
>
> Thank for help

I don't know why you think why the length() call makes it particularly inefficient. That's the small part of the job. The big part of the job is copying all the data (less one element) to a new variable. E.g., here is another way:

y = x(2:end);

But it will run essentially the same as your posted method, with most of the work being the data copying. You *can* make a mex routine that very efficiently removes the *last* element of a vector without any data copying by simply changing the dimensions of the variable in place (completely safe, btw). It would run extremely fast compared to any method that removed the first element. Let me know if you want that code.

James Tursa

"James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message <gobo1s$k9u$1@fred.mathworks.com>...
> You *can* make a mex routine that very efficiently removes the *last* element of a vector without any data copying by simply changing the dimensions of the variable in place (completely safe, btw). It would run extremely fast compared to any method that removed the first element. Let me know if you want that code.
>

Here is the mex code. It is a bare bones version with no argument checking, but it shows you the concept.

James Tursa

--------------------------------------

#include "mex.h"

// You may need to uncomment the next line
//#define mwSize int

void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
    mwSize n;
    if( n = mxGetN(prhs[0]) )
        mxSetN(prhs[0], n - 1);
}

"James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message
> #include "mex.h"
>
> // You may need to uncomment the next line
> //#define mwSize int
>
> void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
> {
> mwSize n;
> if( n = mxGetN(prhs[0]) )
> mxSetN(prhs[0], n - 1);
> }

James,

Does the above produces a memory leak of one element?

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gobp7c$4f3$1@fred.mathworks.com>...
> "James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message
> > #include "mex.h"
> >
> > // You may need to uncomment the next line
> > //#define mwSize int
> >
> > void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
> > {
> > mwSize n;
> > if( n = mxGetN(prhs[0]) )
> > mxSetN(prhs[0], n - 1);
> > }
>
> James,
>
> Does the above produces a memory leak of one element?
>
> Bruno

No, it is completely safe. The memory manager allocates memory for the real and imag data, and the memory manager knows how much memory is *really* there to free when the variable gets cleared. This is completely independent of the variable size parameters kept in the structure. The above scheme works even if you call it successively and run the column size down to zero, and it works safely even if the variable is sharing data memory with another variable. All of the memory will get freed appropriately in either case.

James Tursa

"James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message <gobtal$ppf$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gobp7c$4f3$1@fred.mathworks.com>...
> > "James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message
> > > #include "mex.h"
> > >
> > > // You may need to uncomment the next line
> > > //#define mwSize int
> > >
> > > void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
> > > {
> > > mwSize n;
> > > if( n = mxGetN(prhs[0]) )
> > > mxSetN(prhs[0], n - 1);
> > > }
> >
> > James,
> >
> > Does the above produces a memory leak of one element?
> >
> > Bruno
>
> No, it is completely safe. The memory manager allocates memory for the real and imag data, and the memory manager knows how much memory is *really* there to free when the variable gets cleared. This is completely independent of the variable size parameters kept in the structure. The above scheme works even if you call it successively and run the column size down to zero, and it works safely even if the variable is sharing data memory with another variable. All of the memory will get freed appropriately in either case.
>
> James Tursa

Depending on the size of the problem, the time savings can be quite dramatic, even for a moderately sized problem. e.g.,

>> a=rand(1,100000);
>> tic;for k=1:100000;a=a(2:end);end;toc
Elapsed time is 62.323502 seconds.
>> a=rand(1,100000);
>> tic;for k=1:100000;deletelastcolumn(a);end;toc
Elapsed time is 0.152585 seconds.

James Tursa

"James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message <goc0ek$krn$1@fred.mathworks.com>...
> "James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message <gobtal$ppf$1@fred.mathworks.com>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gobp7c$4f3$1@fred.mathworks.com>...
> > > "James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message
> > > > #include "mex.h"
> > > >
> > > > // You may need to uncomment the next line
> > > > //#define mwSize int
> > > >
> > > > void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
> > > > {
> > > > mwSize n;
> > > > if( n = mxGetN(prhs[0]) )
> > > > mxSetN(prhs[0], n - 1);
> > > > }
> > >
> > > James,
> > >
> > > Does the above produces a memory leak of one element?
> > >
> > > Bruno
> >
> > No, it is completely safe. The memory manager allocates memory for the real and imag data, and the memory manager knows how much memory is *really* there to free when the variable gets cleared. This is completely independent of the variable size parameters kept in the structure. The above scheme works even if you call it successively and run the column size down to zero, and it works safely even if the variable is sharing data memory with another variable. All of the memory will get freed appropriately in either case.
> >
> > James Tursa
>
> Depending on the size of the problem, the time savings can be quite dramatic, even for a moderately sized problem. e.g.,
>
> >> a=rand(1,100000);
> >> tic;for k=1:100000;a=a(2:end);end;toc
> Elapsed time is 62.323502 seconds.
> >> a=rand(1,100000);
> >> tic;for k=1:100000;deletelastcolumn(a);end;toc
> Elapsed time is 0.152585 seconds.
>
> James Tursa

The drawback to this mex approach is, of course, that the full memory is still allocated. So if you start with a 100MB array and then run some algorithm to clip the last column all the way down to zero, you still have 100MB allocated even though the variable size is zero. So you would need to be aware of this and clear the variable when appropriate to get the memory back.

James Tursa

In article <gobtal$ppf$1@fred.mathworks.com>,
aclassyguywithaknotac@hotmail.com says...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gobp7c$4f3$1@fred.mathworks.com>...
> > "James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message
> > > #include "mex.h"
> > >
> > > // You may need to uncomment the next line
> > > //#define mwSize int
> > >
> > > void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
> > > {
> > > mwSize n;
> > > if( n = mxGetN(prhs[0]) )
> > > mxSetN(prhs[0], n - 1);
> > > }
> >
> > James,
> >
> > Does the above produces a memory leak of one element?
> >
> > Bruno
>
> No, it is completely safe. The memory manager allocates memory for the real and imag data, and the memory manager knows how much memory is *really* there to free when the variable gets cleared. This is completely independent of the variable size parameters kept in the structure. The above scheme works even if you call it successively and run the column size down to zero, and it works safely even if the variable is sharing data memory with another variable. All of the
memory will get freed appropriately in either case.
>
> James Tursa
>

Appears to remove the last element, but not the first, which was another
part of OP request.

--
Loren
http://blogs.mathworks.com/loren

Loren Shure <loren@mathworks.com> wrote in message <MPG.2415bd4a7b82867a989949@news.mathworks.com>...
> In article <gobtal$ppf$1@fred.mathworks.com>,
> aclassyguywithaknotac@hotmail.com says...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gobp7c$4f3$1@fred.mathworks.com>...
> > > "James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message
> > > > #include "mex.h"
> > > >
> > > > // You may need to uncomment the next line
> > > > //#define mwSize int
> > > >
> > > > void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
> > > > {
> > > > mwSize n;
> > > > if( n = mxGetN(prhs[0]) )
> > > > mxSetN(prhs[0], n - 1);
> > > > }
> > >
> > > James,
> > >
> > > Does the above produces a memory leak of one element?
> > >
> > > Bruno
> >
> > No, it is completely safe. The memory manager allocates memory for the real and imag data, and the memory manager knows how much memory is *really* there to free when the variable gets cleared. This is completely independent of the variable size parameters kept in the structure. The above scheme works even if you call it successively and run the column size down to zero, and it works safely even if the variable is sharing data memory with another variable. All of the
> memory will get freed appropriately in either case.
> >
> > James Tursa
> >
>
> Appears to remove the last element, but not the first, which was another
> part of OP request.
>
> --
> Loren
> http://blogs.mathworks.com/loren

Right. Title of OP's post was remove either first or last, and text of OP's post was just to remove first, so I assumed he was interested in either.

Any mex approach to removing the first element (I didn't show that code) will have to do the same work as any MATLAB m-code approach, namely copying most of the data, so there isn't much of an advantage with the mex approach. I suppose you could copy the data in-place and avoid an allocation step, but then you run into memory sharing issues so that is not a safe thing to do.

The only real advantage of the mex approach is for the specific problem of removing the last column or element of an array, and that is the code shown.

James Tursa

"James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message <goh0m8$c69$1@fred.mathworks.com>...

>
> Any mex approach to removing the first element (I didn't show that code) will have to do the same work as any MATLAB m-code approach, namely copying most of the data, so there isn't much of an advantage with the mex approach. I suppose you could copy the data in-place and avoid an allocation step, but then you run into memory sharing issues so that is not a safe thing to do.
>

Could you just move the data pointer forward? Or by doing so you risk to mess with Matlab malloc/free calling ?

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <goh171$fc7$1@fred.mathworks.com>...
> "James Tursa" <aclassyguywithaknotac@hotmail.com> wrote in message <goh0m8$c69$1@fred.mathworks.com>...
>
> >
> > Any mex approach to removing the first element (I didn't show that code) will have to do the same work as any MATLAB m-code approach, namely copying most of the data, so there isn't much of an advantage with the mex approach. I suppose you could copy the data in-place and avoid an allocation step, but then you run into memory sharing issues so that is not a safe thing to do.
> >
>
> Could you just move the data pointer forward? Or by doing so you risk to mess with Matlab malloc/free calling ?
>
> Bruno

That would mess up the memory manager. When it came time to clear the variable the data pointer would not match anything the memory manager had for allocated block addresses. I don't know how the MATLAB memory manager works, but in C the result of doing a free call with an invalid pointer for that call is undefined ... anything from ignoring it to the program crashing could be the result. Probably a memory leak at the very least. You might think you could temporarily move the data pointer forward and then put it back to the original state just before clearing it, but that ignores the reality of data sharing ... there might be other variables sharing the memory of the temporary pointer by the time you got around to clearing your original variable. You really have no way to track this down after the fact. You would have to be *very* careful how you used the original variable to avoid this,
but I suppose it could be done in some cases.

James Tursa