Easiest/most efficient way to delete duplicates from one list at the positions of another?

Question

This question is somewhat related to How to efficiently find positions of duplicates? , although I'm interested in something a little bit simpler since I'm not really interested in a list of all the positions of duplicates in a list. I just want to delete duplicates of a given list based on the duplicates of another list.

As a simple example, let's say I have one list

myList = {1,3,1,2};

I perform some operations on this list, which yields a different list, but preserves the length

myNewList = {7,2,2,2};

After deleting duplicates, this list now becomes

myNewListReduced = {7,2};

Now, I would like to remove elements from my original list wherever the duplicates occurred in the new list. I do not necessarily care which of the positions are removed. In myNewList, the duplicates occurred at positions 2,3 and 4. I would like to delete elements in my original list corresponding to that definition of duplicates, so that the following are all acceptable:

myListDuplicatesDeleted = {1,3};

myListDuplicatesDeleted = {1,1};

myListDuplicatesDeleted = {1,2};

That is, 3,1 and 2 from myList are all considered duplicates.

Thank you very much.

Answer 1

You can accomplish this using DeleteDuplicatesBy, by first taking your two input lists and making a matrix out of them, and then deleting the rows where the last element (the element that came from myNewList) is a duplicate. Then you transpose back and assign the sublists of the reduced matrix to the new lists you want.

{myListDuplicatesDeleted, myNewListReduced} = 
 Transpose@DeleteDuplicatesBy[Transpose@{myList, myNewList}, Last]
(* {{1, 3}, {7, 2}} *)

Or, slightly shorter and only returning the myListDuplicatesDeleted list,

First /@ DeleteDuplicatesBy[Transpose@{myList, myNewList}, Last]

And why not have yet another option to do this, we can use GatherBy. I'm writing this in two equivalent ways to further confusion - the first uses Part, which I always prefer, and the second uses First, which people use a lot.

GatherBy[Transpose@{myList, myNewList}, Last][[All, 1, 1]]
Map[First, GatherBy[Transpose@{myList, myNewList}, Last], 2]

Comparing the available methods,

First /@ DeleteDuplicatesBy[Transpose@{myList, myNewList}, 
   Last] // RepeatedTiming
Map[First, GatherBy[Transpose@{myList, myNewList}, Last], 
  2] // RepeatedTiming

(* method by garej *)
Lookup[Thread[myNewList -> myList], 
  DeleteDuplicates@myNewList] // RepeatedTiming

(* method by Kuba *)
Module[{f}, f[x_] := (f[x] = 0; 1); 
  Pick[myList, f /@ myNewList, 1]] // RepeatedTiming

(* method by Hubble07 *)
Module[{dups = DeleteDuplicates[myNewList], pos},
   pos = Flatten[
     First@Position[myNewList, dups[[#]]] & /@ Range[Length[dups]]];
   myList[[pos]]
   ]; // RepeatedTiming


(* {0.0000131, {1, 3}} *)
(* {5.7*10^-6, {1, 3}} *)
(* {2.6*10^-6, {1, 3}} *)
(* {0.00001488, {1, 3}} *)
(* {0.0000192, {1, 3}}  *)

It appears that garej's method is the fastest (I still don't really understand it, but I have a blind spot for associations). But for a list this size they are all pretty equivalent, what about for a much larger list? Let's look at the timing for the GatherBy and Lookup methods for a couple of cases. First, we have a large number of elements (100,000) in both lists, but only 200 unique elements in the myNewList. In this case, the Lookup method is still faster (by 30%)

myList = Range[100000];
myNewList = RandomInteger[200, 100000];

Map[First, GatherBy[Transpose@{myList, myNewList}, Last], 
   2]; // RepeatedTiming

Lookup[Thread[myNewList -> myList], 
   DeleteDuplicates@myNewList]; // RepeatedTiming
(* {0.0537, Null} *)
(* {0.038, Null} *)

But what if we had just as many elements, but now we have far more unique elements in myNewList. In this case, the cost of using Lookup comes into play,

myList = Range[100000];
myNewList = RandomInteger[50000, 100000];

Map[First, GatherBy[Transpose@{myList, myNewList}, Last], 
   2]; // RepeatedTiming

Lookup[Thread[myNewList -> myList], 
   DeleteDuplicates@myNewList]; // RepeatedTiming
(* {0.11, Null} *)
(* {12.6, Null} *)

For this case, with a large list and many unique elements, Kuba's Pick method scales nearly as well as the GatherBy method, while Hubble07's straightforward method scales poorly.

Edit The fastest method for doing this on a large list is garej's AssociationThread method, which when applied to the above large list gives

Values@
   AssociationThread[myNewList -> myList]; // RepeatedTiming
(* {0.031, Null} *)

This method fulfills the OP's requirements, but goes about it in an unintuitive way by keeping the last association rather than the first. Consider these two lists,

myList = Range[10]
myNewList = Range[5, 7]~Join~Range[7]
(* {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} *)
(* {5, 6, 7, 1, 2, 3, 4, 5, 6, 7} *)

and the two new lists that can be made from these lists

myList = Range[10]
myNewList = Range[5, 7]~Join~Range[7]
(* {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} *)
(* {5, 6, 7, 1, 2, 3, 4, 5, 6, 7} *)

Map[First, GatherBy[Transpose@{myList, myNewList}, Last], 2]
Values@AssociationThread[myNewList -> myList]
(* {1, 2, 3, 4, 5, 6, 7} *)
(* {8, 9, 10, 4, 5, 6, 7} *)

So for the value 5 which was duplicated in the myNewList, the AssociationThread method keeps the 8 from myList instead of the 1, which all the other methods pick. This is fine and fits the requirements. But while AssociationThread picks the correct elements to keep, it also changes their order, which may or may not be acceptable.

Answer 2

Comparable to other results:

Lookup[Thread[myNewList -> myList], DeleteDuplicates@myNewList]

{1,3}

Seems most appropriate (fast and concise) for the OP task (V.10):

Values@AssociationThread[myNewList -> myList]

{1,2}

P.S. Learned the general idea from this post of Mr.Wizard.

---

Addenum: Some notes concerning speed.

@Mr.Wizard suggested to compare two methods (one may play with k - list length - and 0.27 - ratio described below - to see what is going on):

k = 10^6;
a = RandomReal[1, k];
b = Round[a*(k * 0.27)];

positionDuplicates[list_] := GatherBy[Range@Length@list, list[[#]] &]

Values @ AssociationThread[b -> a] // Length // RepeatedTiming
a [[positionDuplicates[b][[All, 1]]]] // Length // RepeatedTiming

(* {1.02, 263300} *)
(* {1.02, 263300} *)

It is interesting to see that it is ratio of number of unique elements to list length that is important. If the ratio is less than 0.27 (empirically) GatherBy on average three times faster. (It is demonstrated in Mr.Wizard's example with the ratio 0.03). But when the ratio is higher than 0.27 Association method on average performs a bit better.

Note also that toy OP example is a bit misleading in this sense: it seems to have high density of duplicates in absolute terms, but the above ratio is 0.5. It would be nice to know the real case. I also hope that these results are not pure artefact of my system.

Answer 3

Module[{f}, f[x_] := (f[x] = 0; 1); Pick[myList, f /@ myNewList, 1]]

{1, 3}

Answer 4

I love the brevity and elegance of garej's second method and I would probably Accept it for that reason if nothing else, were this my Question. Nevertheless it seems that using the position method referenced in the question is actually faster.

positionDuplicates[list_] := GatherBy[Range @ Length @ list, list[[#]] &]

a = RandomReal[1, 1*^6];
b = Round[30000*a];

Values @ AssociationThread[b -> a]     // Length // RepeatedTiming
a[[ positionDuplicates[b][[All, 1]] ]] // Length // RepeatedTiming

{0.215, 30001}

{0.0777, 30001}

Answer 5

dups = DeleteDuplicates[myNewList];
pos = Flatten[
 First@Position[myNewList, dups[[#]]] & /@ Range[Length[dups]]];
myList[[pos]]

{1, 3}