It seems to me like identifying the first occurrence of unique elements should take about the same amount of time as it takes to delete duplicates. My data sets are much larger than this (a is 10-20k and b is 1-10k).

With[{a = 1000, b = 10}, list = RandomInteger[a, b a]];
Timing[uniques = DeleteDuplicates@list;]
Timing[firstOccurrenceIndices = Position[list, #, 1, 1] & /@ uniques // Flatten;]

{0.000116, Null}

{0.653104, Null}

Any ideas?


4 Answers 4


Here's a faster way:

Timing[MapIndexed[If[Not@IntegerQ@f[#1], f[#1] = First[#2]] &, list];]

Now f[elem] will tell you the position of the first occurrence of elem. On my machine this is approximately 8-10 times faster than your approach for a list of 10000 elements.

The timing for a=5000, b=100 is 1.3 s on my machine.

In general I expect your solution to have complexity $O(a^2 b)$ while mine should be $O(ab \ln a)$, in terms of $a,b$ as used in your question and $b>1$. I haven't measured it though. For larger lists the speedup will be more significant though.

An alternative:

dt = Dispatch@Thread[list -> Range@Length[list]];

This takes 1.07 s on my machine for the same list as above.

Now to get the first index of elem just do elem /. dt.

Another much faster alternative:

firstOccurrenceIndices = GatherBy[Range@Length[list], list[[#]] &][[All, 1]];

This takes 0.04 s on my machine.

In the Raspberry Pi version (which is a beta of v10) the function PositionIndex will provide a direct solution to this problem

  • $\begingroup$ I should mention that my elements are strings, rather than integers. Not sure if that affects your solution. $\endgroup$ Dec 13, 2013 at 21:02
  • $\begingroup$ @TimothyWofford It doesn't. The values of f are positions which are integers but you could replace IntegerQ by ValueQ here. $\endgroup$
    – Szabolcs
    Dec 13, 2013 at 21:06
  • $\begingroup$ I see, so to get my list of first indices I guess I follow this with firstIndices=DeleteDuplicates@(f/@list) $\endgroup$ Dec 13, 2013 at 21:14
  • $\begingroup$ @TimothyWofford it's more efficient to do f/@DeleteDuplicates[list] instead $\endgroup$
    – Szabolcs
    Dec 13, 2013 at 21:16
  • 1
    $\begingroup$ hahahah... I was about to add an answer using that method, starting my post with: "Poor Szabolcs seems to be suffering from senility (like me), as he has forgotten his own method..." $\endgroup$
    – Mr.Wizard
    Dec 14, 2013 at 1:10

An approach using Reap and Sow:

f[list_]:=Reap[MapIndexed[Sow[First@#2, #1] &, 
    list], _, #1 -> First@#2 &][[2]]


list=With[{a = 5000, b = 100}, list = RandomInteger[a, b a]];



takes 0.9375 seconds.


Of the non-GatherBy methods, the fastest are those that use the same approach as Leonid Shifrin's positionOfDuplicates. In v5.2 I use

posi[list_] := Sort@Part[Range[Length@list][[#]],
  Most@FoldList[Plus,1,Length/@Split@list[[#]]]]& @ Ordering@list

which gives the position of the initial instance of each value in list, in the order in which they occur. (If Sort is omitted then the positions are ordered by the values in list, which is sometimes more convenient.)


Prompted by some conversation in comments elswhere, my method.

   If[OrderedQ[#], Most@Accumulate@Prepend[Tally[#][[All, 2]], 1],
    o = Ordering[#];
    o[[Most@Prepend[Accumulate[Tally[#[[o]]][[All, 2]]] + 1, 1]]]]] &[targetListHere]

Can clobber GatherBy method by over an order of magnitude (e.g. on RandomInteger[1*^6,1*^5] my tests showed ~11X faster). On the same test size with a sorted list, this was around ~30X faster than GatherBy. Much more frugal RAM use compared to GB also...

Of course, taking advantage of the structure of your data (non-negative integers of a fairly limited range) this and all the other posted methods can be clobbered performance-wise with

findFirstOccurPos[list_] := 
 Module[{z = ConstantArray[0, Max[list] + 1]},
  z[[Reverse@(list + 1)]] = Range@Length@list;
  (Length@list + 1) - SparseArray[z]["NonzeroValues"]]

Taking further advantage of the structure and random distribution of your example, we can boost performance another 5-6X with selective list "snooping" that short-circuits the process:

findFirstOccurPosSC[list_] := 
 Module[{lens = Ceiling[Length@list/{100, 50, 20, 10, 5, 1}], 
   z = ConstantArray[0, Max[list] + 1], 
   need = Length@DeleteDuplicates@list, result, l},
  Catch[Do[l = list[[;; curlen]];
    z[[Reverse@(l + 1)]] = Range@curlen;
    result = (curlen + 1) - SparseArray[z]["NonzeroValues"];
    If[Length@result == need, Throw[result]];
    , {curlen, lens}]; result]]

This will be in general ~30X faster than using GatherBy on large lists.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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