20
$\begingroup$

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.

Improve this question
$\endgroup$
0

5 Answers 5

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ there is another option: Values@AssociationThread[myNewList -> myList] $\endgroup$ Commented Jan 19, 2016 at 14:13
  • $\begingroup$ @garej, That one takes the cake timewise. For a larger list, it's hard to see how it chooses which of the elements in myList to keep for the various duplicates, but I think it does it correctly. All the other methods choose the first corresponding entry, making it easy to check visually on a small list that it did the right thing. I can add it here, or you can add it to your answer, on a large list it's the fastest method. $\endgroup$ Commented Jan 19, 2016 at 14:35
  • $\begingroup$ @JasonB it always keeps the last one per key, isn't it? It's like <|1 -> old, 1->new|>. $\endgroup$ Commented Jan 19, 2016 at 15:10
  • $\begingroup$ @Kuba, that's it, the old one is replaced by the new one. $\endgroup$ Commented Jan 19, 2016 at 15:11
  • 1
    $\begingroup$ If order is important you can Reverse both the old and new lists, perform the operation, then Reverse the result, and you'll have the original order. $\endgroup$ Commented Jan 20, 2016 at 0:41
14
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I love the new method! Using the automatic duplicate removal of associations is great. $\endgroup$ Commented Jan 19, 2016 at 23:46
  • $\begingroup$ @Mr.Wizard, thank you, your opinion is indispensable $\endgroup$ Commented Jan 19, 2016 at 23:54
  • 1
    $\begingroup$ My appreciation for your elegant and insightful coding is not diminished but I feel it necessary to assert that the method implied in the question is actually faster than any of the existing answers, including this one. I posted an example as an answer below. If you have a counterexample please include it here. $\endgroup$ Commented Jan 20, 2016 at 0:39
  • 1
    $\begingroup$ Nice analysis and rebuttal. :-) $\endgroup$ Commented Jan 21, 2016 at 1:04
5
$\begingroup$ 
Module[{f}, f[x_] := (f[x] = 0; 1); Pick[myList, f /@ myNewList, 1]] 
{1, 3}
Improve this answer
$\endgroup$
4
$\begingroup$

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}
Improve this answer
$\endgroup$
0
3
$\begingroup$ 
dups = DeleteDuplicates[myNewList]; pos = Flatten[ First@Position[myNewList, dups[[#]]] & /@ Range[Length[dups]]]; myList[[pos]]

{1, 3}

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.