(50g) Removing Objects From Lists Quickly

+- HP Forums (http://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (50g) Removing Objects From Lists Quickly (/thread-12107.html)

(50g) Removing Objects From Lists Quickly - John Keith - 01-05-2019 11:16 AM

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


RE: (50g) Removing Objects From Lists Quickly - John Keith - 01-07-2019 11:19 AM

I also came up with a similar program for set intersection. It is also much faster than GoferLists' Intersect:

Code:

\<< SWAP DUP ROT LSORT LGRP DUP HEAD UNROT PICK3 OVER SIZE LMRPT LREPL SWAP MPOS LPICK
\>>

The order of commands may seem strange but gives correct results faster than any other program I could come up with. Others are encouraged to improve the code, and especially to test it for correctness.