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

[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!

[John Keith]

Thanks, David.

From my (limited) understanding of set theory, the difference function (as well as intersection and, of course, union) should eliminate any duplicates. Set functions in Mathematica work this way. All three of those functions in GoferLists return lists with duplicate objects in some circumstances. I believe that this behavior is erroneous. (Maybe not- see post #11 below.)

Along those lines, 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.

[DavidM]

(01-07-2019 05:19 PM)John Keith Wrote:  From my (limited) understanding of set theory, the difference function (as well as intersection and, of course, union) should eliminate any duplicates. Set functions on the Prime and in Mathematica work this way.

I'm not even remotely a mathematician, so I'll take your word for it that removing duplicates is the correct way to go. Python sets don't even allow duplicates to begin with, so you could also include that as another reference supporting that premise.

(01-07-2019 05:19 PM)John Keith Wrote:  Along those lines, I also came up with a similar program for set intersection. It is also much faster than GoferLists' Intersect and never returns lists with duplicate objects:

Code:


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

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.

Once again, an interesting approach. You are indeed creative!

I've got some ideas for implementations of Union/Difference/Intersection that involve parts of the underlying code behind LDDUP/LREPL/LRMOV. I'll add that investigation to my stack of "look at this sometime" items. Those would seem to be useful and a natural fit for ListExt.

[John Keith]

(01-07-2019 08:05 PM)DavidM Wrote:  Those would seem to be useful and a natural fit for ListExt.

I strongly concur!

[DavidM]

So...

Union seems fairly straightforward, and in this case would be functionally similar to "+ LDDUP" (though implemented a bit more efficiently).

Intersection doesn't have a short-and-sweet equivalent, but seems functionally understandable as well (list of unique elements that are in both lists).

Difference may need some clarification, though. Am I correct in assuming that the target here is what is described on this page as the "relative complement"? That would imply that order of arguments is important (ie. "difference" is not commutative).

[Thomas Klemm]

(01-09-2019 06:29 PM)DavidM Wrote:  Difference may need some clarification, though. Am I correct in assuming that the target here is what is described on this page as the "relative complement"?

Yes.

There's also a symmetric difference:

[John Keith]

(01-09-2019 06:29 PM)DavidM Wrote:  Difference may need some clarification, though. Am I correct in assuming that the target here is what is described on this page as the "relative complement"? That would imply that order of arguments is important (ie. "difference" is not commutative).

There is definitely some confusing terminology in this area. "difference" as implemented by GoferLists as Diff and my difference program, is what Wikipedia refers to as "relative complement". Called Complement in Mathematica. Confusingly, the Prime's DIFFERENCE command implements symmetric difference, not complement.

You are correct that set difference aka complement is non-commutative.

[John Keith]

(01-09-2019 08:31 PM)Thomas Klemm Wrote:  

(01-09-2019 06:29 PM)DavidM Wrote:  Difference may need some clarification, though. Am I correct in assuming that the target here is what is described on this page as the "relative complement"?

Yes.

There's also a symmetric difference:

Yes, there is.

Assuming my difference program is called DIFF:

Code:


\<<DUP2 DIFF UNROT SWAP DIFF +
\>>

I'm sure this could be greatly improved by rewriting it directly rather than in terms of DIFF, but I haven't attempted to do so yet.

[Thomas Klemm]

(01-09-2019 10:34 PM)John Keith Wrote:  Confusingly, the Prime's DIFFERENCE command implements symmetric difference, not complement.

Ouch!

[John Keith]

In addition to the terminological confusion, there seem to be several differences (pun intended) in the way these functions are implemented. In Mathematica, both Complement and Union return sorted lists; GoferLists and the Prime return lists containing elements in the original order that they occurred in the input lists.

Also, I have noticed that INTERSECT on the Prime does return lists with some duplicate elements if the first input list contains duplicates. Therefor I am removing the final LDDUP command in my intersection program in post #3. The program will be faster, and users can always execute LDDUP themselves afterwards if they wish.