Thread Subject: remove element from list

I have an array of structures, P(1)...P(N), where N is a large number.
Then I want to remove an element, P(M), where M is between 1 and N. Then I could shift all elements P(K) with K>M down an index but that is kind of a pain.
Or I could use linked lists and then just unlink an element. But I would still be left with a huge array.
Is there a better way to remove elements and shrink an array without having to shift everything around?

Dear Matt!

> I have an array of structures, P(1)...P(N), where N is a large number.
> Then I want to remove an element, P(M), where M is between 1 and N. Then I could shift all elements P(K) with K>M down an index but that is kind of a pain.
> Or I could use linked lists and then just unlink an element. But I would still be left with a huge array.
> Is there a better way to remove elements and shrink an array without having to shift everything around?

Please explain, what "kind of pain" means. Usually Matlab shifts the data for you and for the array of structures this is not really slow: even the pointers to the structs are shifted, not the contents itself.

Another, faster, idea is using logical indices. Then you do not operate on the whole array P, but just on the subarray P(ActiveIndex) with:
  ActiveIndex = true(1, numel(P));
Then "deleting" an element is done by:
  ActiveIndex(M) = false.
No shifting, no re-allocation. And using P(ActiveIndex) e.g. for searching does usually not create a copy of the array, so it is not slower than the method of removing elements from P --- at least for large arrays and with some limitations: if almost all ActiveIndex are false, a refresh of P is helpful:
  P = P(ActiveIndex); ActiveIndex = true(1, numel(P));

Have fun, Jan

"Jan Simon" <matlab.THIS_YEAR@nMINUSsimon.de> wrote in message <hbo2pl$aso$1@fred.mathworks.com>...
> Dear Matt!
>
> > I have an array of structures, P(1)...P(N), where N is a large number.
> > Then I want to remove an element, P(M), where M is between 1 and N. Then I could shift all elements P(K) with K>M down an index but that is kind of a pain.
> > Or I could use linked lists and then just unlink an element. But I would still be left with a huge array.
> > Is there a better way to remove elements and shrink an array without having to shift everything around?
>
> Please explain, what "kind of pain" means. Usually Matlab shifts the data for you and for the array of structures this is not really slow: even the pointers to the structs are shifted, not the contents itself.
>
> Another, faster, idea is using logical indices. Then you do not operate on the whole array P, but just on the subarray P(ActiveIndex) with:
> ActiveIndex = true(1, numel(P));
> Then "deleting" an element is done by:
> ActiveIndex(M) = false.
> No shifting, no re-allocation. And using P(ActiveIndex) e.g. for searching does usually not create a copy of the array, so it is not slower than the method of removing elements from P --- at least for large arrays and with some limitations: if almost all ActiveIndex are false, a refresh of P is helpful:
> P = P(ActiveIndex); ActiveIndex = true(1, numel(P));
>
> Have fun, Jan

Hi Jan, Thanks for excellent answer. Let me make the problem a little more complicated and see how that goes.
You have 10 churches and 100 members. Each member belongs to 1 church.
So the Church structure has the church name, and a list of who belongs to that church and it could have the active index.
Church(1).Name='Trinity'
Church(1).Members=[1 3 4 6];
Church(1).ActiveIndex=1;
Church(2).Name='Quadrinity'
Church(2).Members=[2 3 19 50];
Church(2).ActiveIndex=1;
Church(3).Name='Pentitude'
Church(3).Members=[45 50 55];
Church(3).ActiveIndex=1;
...
and the MyChurch array tells us which Church a certain member belongs to.
MyChurch(1)=1
MyChurch(2)=1
MyChurch(3)=2
Now if Church(2) closes and all its members shift to Church(3),we could update the Church array as suggested above, Church=Church(ActiveIndex). But then all the indices would shift, so the MyChurch array would have to be updated as well? How would that be done. Thanks Matt

Dear Matt!

> You have 10 churches and 100 members. Each member belongs to 1 church.
> So the Church structure has the church name, and a list of who belongs to that church and it could have the active index.
> Church(1).Name='Trinity'
> Church(1).Members=[1 3 4 6];
> Church(1).ActiveIndex=1;
> Church(2).Name='Quadrinity'
> Church(2).Members=[2 3 19 50];
> Church(2).ActiveIndex=1;
> Church(3).Name='Pentitude'
> Church(3).Members=[45 50 55];
> Church(3).ActiveIndex=1;
> ...
> and the MyChurch array tells us which Church a certain member belongs to.
> MyChurch(1)=1
> MyChurch(2)=1
> MyChurch(3)=2
> Now if Church(2) closes and all its members shift to Church(3),we could update the Church array as suggested above, Church=Church(ActiveIndex). But then all the indices would shift, so the MyChurch array would have to be updated as well? How would that be done. Thanks, Matt

I have the same problem again and again. I'm using a logical index vector and have to select the n.th TRUE value. Although this works with some FIND statements to switch to index vectors, the speed advantage of the logical indexing disappears. I have not found an efficient solution yet by my own or in the FEX. I think, I'll create a MEX for this task.

Kind regards, Jan

"Jan Simon" <matlab.THIS_YEAR@nMINUSsimon.de> wrote in message <hbp7fg$8ve$1@fred.mathworks.com>...
> Dear Matt!
>
> > You have 10 churches and 100 members. Each member belongs to 1 church.
> > So the Church structure has the church name, and a list of who belongs to that church and it could have the active index.
> > Church(1).Name='Trinity'
> > Church(1).Members=[1 3 4 6];
> > Church(1).ActiveIndex=1;
> > Church(2).Name='Quadrinity'
> > Church(2).Members=[2 3 19 50];
> > Church(2).ActiveIndex=1;
> > Church(3).Name='Pentitude'
> > Church(3).Members=[45 50 55];
> > Church(3).ActiveIndex=1;
> > ...
> > and the MyChurch array tells us which Church a certain member belongs to.
> > MyChurch(1)=1
> > MyChurch(2)=1
> > MyChurch(3)=2
> > Now if Church(2) closes and all its members shift to Church(3),we could update the Church array as suggested above, Church=Church(ActiveIndex). But then all the indices would shift, so the MyChurch array would have to be updated as well? How would that be done. Thanks, Matt
>
> I have the same problem again and again. I'm using a logical index vector and have to select the n.th TRUE value. Although this works with some FIND statements to switch to index vectors, the speed advantage of the logical indexing disappears. I have not found an efficient solution yet by my own or in the FEX. I think, I'll create a MEX for this task.
>
> Kind regards, Jan

I have faced some of these challenges as well; for me, they generally arise when I try to use structures kinda like relational databases, which they aren't.

One thing that springs to mind here is that if the church numbering is subject to change, then that's not a good reference for your MyChurch array. Instead, could you make MyChurch a cell array, referencing Church.Name?

the cyclist

"the cyclist" <thecyclist@gmail.com> wrote in message <hbplbu$6ir$1@fred.mathworks.com>...
> "Jan Simon" <matlab.THIS_YEAR@nMINUSsimon.de> wrote in message <hbp7fg$8ve$1@fred.mathworks.com>...
> > Dear Matt!
> >
> > > You have 10 churches and 100 members. Each member belongs to 1 church.
> > > So the Church structure has the church name, and a list of who belongs to that church and it could have the active index.
> > > Church(1).Name='Trinity'
> > > Church(1).Members=[1 3 4 6];
> > > Church(1).ActiveIndex=1;
> > > Church(2).Name='Quadrinity'
> > > Church(2).Members=[2 3 19 50];
> > > Church(2).ActiveIndex=1;
> > > Church(3).Name='Pentitude'
> > > Church(3).Members=[45 50 55];
> > > Church(3).ActiveIndex=1;
> > > ...
> > > and the MyChurch array tells us which Church a certain member belongs to.
> > > MyChurch(1)=1
> > > MyChurch(2)=1
> > > MyChurch(3)=2
> > > Now if Church(2) closes and all its members shift to Church(3),we could update the Church array as suggested above, Church=Church(ActiveIndex). But then all the indices would shift, so the MyChurch array would have to be updated as well? How would that be done. Thanks, Matt
> >
> > I have the same problem again and again. I'm using a logical index vector and have to select the n.th TRUE value. Although this works with some FIND statements to switch to index vectors, the speed advantage of the logical indexing disappears. I have not found an efficient solution yet by my own or in the FEX. I think, I'll create a MEX for this task.
> >
> > Kind regards, Jan
>
> I have faced some of these challenges as well; for me, they generally arise when I try to use structures kinda like relational databases, which they aren't.
>
> One thing that springs to mind here is that if the church numbering is subject to change, then that's not a good reference for your MyChurch array. Instead, could you make MyChurch a cell array, referencing Church.Name?
>
> the cyclist

Thanks for comments. Here is a possible way to create a lookup table.
poki=[0 1 1 0 1 0 0 0 1 1 0 ]; % array with ones and zeros
smoki=zeros(1,length(poki)); % copy array
smoki(find(poki))=[1:length(find(poki))]; % create a matrix with labelled find elements

Regards Matt

Dear Matt!

> Thanks for comments. Here is a possible way to create a lookup table.
> poki=[0 1 1 0 1 0 0 0 1 1 0 ]; % array with ones and zeros
> smoki=zeros(1,length(poki)); % copy array
> smoki(find(poki))=[1:length(find(poki))]; % create a matrix with labelled find elements

This looks fine! It does exactly the application of a logical index vector to the TRUE elements on another.

Slightly modifications:
  poki = logical([0 1 1 0 1 0 0 0 1 1 0 ]);
  smoki(poki) = 1:length(find(poki));

Pre-allocation of smoki is not needed.

Brackets around a vector create a vector of a vector, which is a vector in Matlab, so it is enough to create a vector with the colon operator and converting the vector into a vector is not needed, because it wastes time.

poki is faster as logical index, so avoid the unneeded FIND --- this is not always true, please ask <us> for comparing speeds for arguments on different sizes, modern Matlab versions and multi-core computers.

I'll try to apply this (actually trivial method - but I haven't figured this out before) to the original problem.

Kind regards, Jan

Dear Matt!
Sorry, I did not meant, that I want to use your method to solve *your* problem, but:
http://www.mathworks.com/matlabcentral/newsreader/view_thread/263646
Thanks, Jan