# How to remove duplicate elements from two separated lists efficiently?

I have two lists of elements:

indices = {Prime /@ Range[5000], Prime /@ Range[100, 300]} // Flatten;
values = RandomReal[100, 3] & /@ Range[Length[indices]];


where the i-th element in indices corresponds to the i-th element in values.

Now I want to remove the duplicates in indices as well as their corresponding elements in values.

I do it in this way:

removeDuplicates[indices_, values_] := Block[{t},
DeleteDuplicates[t, First[#1] == First[#2] &] // Transpose
];


However, it takes a long time to run:

removeDuplicates[indices, values]; // AbsoluteTiming

(* {9.7083, Null} *)


If I only remove elements in indices, it is actually quite fast:

DeleteDuplicates[indices]; // AbsoluteTiming

(* {0.000545, Null} *)


Is there a simple way to remove pairing duplicates efficiently?

DeleteDuplicates[t, First[#1] == First[#2] & needs to compare every element with every other - that's O(n^2) comparisons, that's why it's so much slower. If you have a recent version of MMA, you can simply use DeleteDuplicatesBy: (e.g. DeleteDuplicatesBy[t, First]) instead.

If you have an older version of MMA, you could use associations to map from modifies index-sets to value-sets quickls:

mapping = Association[Thread[indices -> values]];
uniqueIndices = DeleteDuplicates[indices];
{uniqueIndices, mapping /@ uniqueIndices}


ADD: As @Chris pointed out, Association is relatively new, too. Another way would be using GatherBy:

Transpose[GatherBy[Transpose[{indices, values}], First][[All, 1]]]

• +1 However, associations also only appeared in version 10. Dec 10, 2015 at 11:52
• Thank you. Transpose[GatherBy[Transpose[{indices, values}], First][[All, 1]]] runs pretty much faster than DeleteDuplicatesBy[t, First]. Dec 10, 2015 at 12:49

Proposition

Just for fun, here is a version inspired by the DeleteDuplicates code of Mr.Wizard in this answer,

deleteDuplicates[list1_, list2_] := Module[{f, i = 0, bag = InternalBag[{}]},
f[y_] := (i++; f[y] := (InternalStuffBag[bag, {++i}]; Nothing); y);
{f /@ list1, Delete[list2, InternalBagPart[bag, All]]}]


For Mathematica versions older than 10.2, Nothing can be replaced by Unevaluated@Sequence[].

Timings

This code is much faster than OP's but is slower than the best solutions by a factor of roughly 3. Considering OP's data

indices = {Prime /@ Range[5000], Prime /@ Range[100, 300]} // Flatten;
values = RandomReal[100, 3] & /@ Range[Length[indices]];


and gathering the solutions posted so far

nikie1[list1_, list2_] := Module[{uniqueIndices = DeleteDuplicates[list1]},
{uniqueIndices, Association[Thread[indices -> values]] /@ uniqueIndices}];

nikie2[list1_, list2_] := Transpose[
GatherBy[Transpose[{list1, list2}], First][[All, 1]]];

chris1[list1_, list2_] := Module[{data = MapThread[List, {list1, list2}]},
Part[data, Sort[Part[Range[Length@data][[#]],
Most@FoldList[Plus, 1, Length /@ Split[data[[All, 1]][[#]]]]]]] &@
Ordering[First /@ data] // Transpose];

chris2[list1_, list2_] :=

xavier[list1_, list2_] := Module[{f, i = 0, bag = InternalBag[{}]},
f[y_] := (i++; f[y] := (InternalStuffBag[bag, {++i}]; Nothing); y);
{f /@ list1, Delete[list2, InternalBagPart[bag, All]]}]


I get the following timings on my computer

timings = Through[Map[Composition[AbsoluteTiming, #] &,
{nikie1, nikie2, chris1, chris2, xavier}][indices, values]][[All, 1]];

TableForm[Transpose[{{nikie1, nikie2, chris1, chris2, xavier}, timings}]]


• Nice comparison. It seems that nikie2 is the fastest and most simple way to achieve this goal. Dec 11, 2015 at 6:12
• +1. I would just add, an advantage of the more low level methods (like DD2) is that they're more open to modification for adding new functionality which may not be provided by the higher-level methods. Dec 11, 2015 at 12:44

Borrowing from a method here, this will work on older versions.

DD2[data_] := Part[data,
Sort[Part[
Range[Length@data][[#]],
Most@FoldList[Plus, 1, Length /@ Split[data[[All, 1]][[#]]]]
]]
] &@Ordering[First /@ data]

ans = Transpose[DD2[data]]


Actually I would have expected the answer from DD2, but which duplicate wasn't specified.

indices = {1163, 919, 1163, 919};
values = {
{41.71, 31.16, 34.19},
{60.68, 23.29, 87.79},
{0.22, 58.81, 76.78},
{0.76, 94.68, 19.81}};

uniqueIndices = DeleteDuplicates[indices];
{uniqueIndices, mapping /@ uniqueIndices}


{{1163, 919}, {{0.22, 58.81, 76.78}, {0.76, 94.68, 19.81}}}

The association is picking up the last match associated with a duplicate.

All the following solutions arrive at the same answer.

data = MapThread[List, {indices, values}];
Transpose[DD2[data]]


{{1163, 919}, {{41.71, 31.16, 34.19}, {60.68, 23.29, 87.79}}}

Transpose[DeleteDuplicatesBy[data, First]]


{{1163, 919}, {{41.71, 31.16, 34.19}, {60.68, 23.29, 87.79}}}

Transpose[GatherBy[Transpose[{indices, values}], First][[All, 1]]]


{{1163, 919}, {{41.71, 31.16, 34.19}, {60.68, 23.29, 87.79}}}

• The results are different from DeleteDuplicatesBy[t, First]. Dec 10, 2015 at 12:51
• I find they match. Please see my edit. The same applies for the full dataset. Dec 10, 2015 at 15:25
• Yes, they match. Sorry about the mistake. Dec 11, 2015 at 6:11