(50g) Removing Objects From Lists Quickly

[John Keith]

Note: The examples in this post require the libraries GoferLists and ListExt. The last example also requires LSORT.

The GoferLists command Filter selects elements of a list on stack level 2 that meet criteria described by a user program on level 1. For instance:

Code:


{  1 2 3 4 5 6 7 8 9 } 
\<< 2 MOD \>> Filter

{ 1 3 5 7 9 }

Filter can similarly be used to remove items from a list by inverting the logic of the program, e.g. 2 MOD NOT will return the even numbers from the list.

If one wants to remove multiple instances of one object from a list, Filter can be used like so:

Code:


{ 1 2 3 2 4 5 2 6 }
\<< 2 SAME NOT \>> Filter

{ 1 3 4 5 6 }

but Filter is quite slow for that purpose. A much faster method is illustrated by the following short program using ListExt commands:

Code:


\<< OVER UNROT MPOS LRMOV
\>>

with the list on level 2 and the object to be removed on level 1.

If one wants to remove all instances of multiple objects from a list, one can use the GoferLists command Diff (set difference). Diff is reasonably fast for small lists but slows down appreciably for larger lists. The following program is a bit slower than Diff for small lists but more than 10 times as fast for lists containing hundreds of objects:

Code:


\<< DUP HEAD UNROT PICK3 OVER SIZE LMRPT LREPL DUP ROT MPOS LRMOV
\>>

A similar case involves removing duplicate objects from a list. The GoferLists command Nub does this, and so does the ListExt command LDDUP, which is quite a bit faster. Both commands preserve the order of the (unique) objects in the list.

If preserving the order of list objects is not required or, especially, if sorting them is desirable, the following short sequence is much faster:

Code:


\<< LSORT LGRP
\>>