(50g) Removing Objects From Lists Quickly

[DavidM]

(01-05-2019 05:16 PM)John Keith Wrote:  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
\>>

That's a clever approach! I doubt I'd have ever come up with something like that.

I was curious to see how Diff worked, so I took a look at what it does. GoferList's Diff is essentially:

Code:

« SWAP « Delete » Foldl »

Foldl internally uses STREAM, which is reasonably efficient, but I think the slowdown comes from repeated calls to Delete in this case. It looks for the matching item, and if found it then splits the source list into "before the found item" and "after the found item" sublists, then concatenates them. That results in the remaining list objects having to be copied into new objects two separate times for each found (common) object, which slows things down considerably.

The ListExt-based program you came up with only has to replicate the source data twice (as opposed to twice per found object). The first replication occurs with LREPL, and the second with LRMOV.

While looking through the Diff code, I also realized that it handles duplicates differently than the ListExt version. For example:

Code:

{ 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 }
{ 1 1 2 3 4 5 }
Diff

...gives this result:
{ 1 2 2 3 3 4 4 5 5 }

Using the ListExt sequence with the same list objects yields an empty list result. I can see both possibilities being appropriate in different circumstances, though.

Nice implementations, John!