How to remove duplicate elements from two separated lists efficiently?

Question

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}, 
    t = Thread[{indices, values}];
    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?

Answer 1

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]]]

Answer 2

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 = Internal`Bag[{}]},
    f[y_] := (i++; f[y] := (Internal`StuffBag[bag, {++i}]; Nothing); y);
    {f /@ list1, Delete[list2, Internal`BagPart[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_] := 
   Transpose[DeleteDuplicatesBy[MapThread[List, {list1, list2}], First]];

xavier[list1_, list2_] := Module[{f, i = 0, bag = Internal`Bag[{}]},
   f[y_] := (i++; f[y] := (Internal`StuffBag[bag, {++i}]; Nothing); y);
   {f /@ list1, Delete[list2, Internal`BagPart[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}]]

Answer 3

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]

data = MapThread[List, {indices, values}]

ans = Transpose[DD2[data]]

Why different answers?

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}};

mapping = Association[Thread[indices -> values]];
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}}}