Remove from list

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Remove from list

Nathan Hüsken
Hi,

is it possible to remove an element from a list by using the position
(maybe via iterator)?
Because I am doing something like this:

for (e in list) {
  if(shouldBeRemoved(e)) {
    list.remove(e);
  }
}

And remove potentially goes every the whole list every time ...

Regards,
Nathan

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Remove from list

Johann Borck
On 10/14/2011 03:42 PM, Nathan Hüsken wrote:

> Hi,
>
> is it possible to remove an element from a list by using the position
> (maybe via iterator)?
> Because I am doing something like this:
>
> for (e in list) {
>    if(shouldBeRemoved(e)) {
>      list.remove(e);
>    }
> }
Hi,
you probably want to use list.filter(shouldBeRemoved), it is more efficient in most cases.

regards,
Johann

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Remove from list

Yanis Benson

Removing element from list has complexity O(N). Johann's approach has O(N*N) complexity. More than that, list.filter is faster even for a list of 1 element. So, filter will be faster in every case. Also, if you want to remove exactly 1 element, you can write a method which will be two times faster on average.

On 14 Oct 2011 18:52, "Johann Borck" <[hidden email]> wrote:
On 10/14/2011 03:42 PM, Nathan Hüsken wrote:
Hi,

is it possible to remove an element from a list by using the position
(maybe via iterator)?
Because I am doing something like this:

for (e in list) {
  if(shouldBeRemoved(e)) {
    list.remove(e);
  }
}
Hi,
you probably want to use list.filter(shouldBeRemoved), it is more efficient in most cases.

regards,
Johann

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Remove from list

Johann Borck
On 10/14/2011 07:03 PM, Yanis Benson wrote:
>
> Removing element from list has complexity O(N). Johann's approach has O(N*N) complexity. More than
> that, list.filter is faster even for a list of 1 element. So, filter will be faster in every case.
> Also, if you want to remove exactly 1 element, you can write a method which will be two times
> faster on average.
>
It really depends, list.filter constructs a new list, remove does not, so actual runtime costs
depend on quite a few factors. If shouldBeRemoved matches only the first element of a big list,
filter will likely be both slower and less space efficient.

But the more problematic issue with the presented code is that it might also depend on the
implementations of List and its iterator on the respective targets what exactly happens when you
mutate the list while iterating over it. I'm not sure haxe specifies that behavior, it might give
surprising results. Consider:

class T {
     public static function main(){
     var l = [1,2,3,4,5,6,7,8,9,10];
     for (i in l){
         trace(i);
         if (i % 2 != 0){
             l.remove(i);
         }
         trace (l);
     }
     }
}

which, using neko, produces

T.hx:7: 1
T.hx:11: [2, 3, 4, 5, 6, 7, 8, 9, 10]
T.hx:7: 3
T.hx:11: [2, 4, 5, 6, 7, 8, 9, 10]
T.hx:7: 5
T.hx:11: [2, 4, 6, 7, 8, 9, 10]
T.hx:7: 7
T.hx:11: [2, 4, 6, 8, 9, 10]
T.hx:7: 9
T.hx:11: [2, 4, 6, 8, 10]

as output, which might very well not be what one expects. In Nathans code this would result in
shouldBeRemoved not being called on elements directly following elements for which the function
returns true. Almost certainly not Nathans intent.  It is questionable style at the very least, many
consider it bad practice.  Code like that should be avoided in favor of something that communicates
the programmers intent more clearly and doesn't rely on implementation details.

regards,
Johann


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: Remove from list

Yanis Benson

Actually, I believe such usage of iterators is prohibited. Sorry about filter part, I thought it mutates the list(I use my own lists, so...).

On 14 Oct 2011 23:59, "Johann Borck" <[hidden email]> wrote:
On 10/14/2011 07:03 PM, Yanis Benson wrote:

Removing element from list has complexity O(N). Johann's approach has O(N*N) complexity. More than that, list.filter is faster even for a list of 1 element. So, filter will be faster in every case. Also, if you want to remove exactly 1 element, you can write a method which will be two times faster on average.

It really depends, list.filter constructs a new list, remove does not, so actual runtime costs depend on quite a few factors. If shouldBeRemoved matches only the first element of a big list, filter will likely be both slower and less space efficient.

But the more problematic issue with the presented code is that it might also depend on the implementations of List and its iterator on the respective targets what exactly happens when you mutate the list while iterating over it. I'm not sure haxe specifies that behavior, it might give surprising results. Consider:

class T {
   public static function main(){
   var l = [1,2,3,4,5,6,7,8,9,10];
   for (i in l){
       trace(i);
       if (i % 2 != 0){
           l.remove(i);
       }
       trace (l);
   }
   }
}

which, using neko, produces

T.hx:7: 1
T.hx:11: [2, 3, 4, 5, 6, 7, 8, 9, 10]
T.hx:7: 3
T.hx:11: [2, 4, 5, 6, 7, 8, 9, 10]
T.hx:7: 5
T.hx:11: [2, 4, 6, 7, 8, 9, 10]
T.hx:7: 7
T.hx:11: [2, 4, 6, 8, 9, 10]
T.hx:7: 9
T.hx:11: [2, 4, 6, 8, 10]

as output, which might very well not be what one expects. In Nathans code this would result in shouldBeRemoved not being called on elements directly following elements for which the function returns true. Almost certainly not Nathans intent.  It is questionable style at the very least, many consider it bad practice.  Code like that should be avoided in favor of something that communicates the programmers intent more clearly and doesn't rely on implementation details.

regards,
Johann


--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org