Efficient way of identifying the indices of first occurrences

Question

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?

Answer 1

Here's a faster way:

Clear[f]
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

Answer 2

An approach using Reap and Sow:

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

For:

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

then

f[list]//Timing

takes 0.9375 seconds.

Answer 3

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.)

Answer 4

Prompted by some conversation in comments elswhere, my method.

Module[{o},
   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.