6
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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]]]
$\endgroup$
  • $\begingroup$ +1 However, associations also only appeared in version 10. $\endgroup$ – Chris Degnen Dec 10 '15 at 11:52
  • $\begingroup$ Thank you. Transpose[GatherBy[Transpose[{indices, values}], First][[All, 1]]] runs pretty much faster than DeleteDuplicatesBy[t, First]. $\endgroup$ – Purboo Dec 10 '15 at 12:49
4
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ Nice comparison. It seems that nikie2 is the fastest and most simple way to achieve this goal. $\endgroup$ – Purboo Dec 11 '15 at 6:12
  • $\begingroup$ +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. $\endgroup$ – Chris Degnen Dec 11 '15 at 12:44
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.