# Efficient way of identifying the indices of first occurrences

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?

-
Very closely related: How to efficiently find positions of duplicates? –  Mr.Wizard Dec 14 '13 at 1:12

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

-
I should mention that my elements are strings, rather than integers. Not sure if that affects your solution. –  Timothy Wofford Dec 13 '13 at 21:02
@TimothyWofford It doesn't. The values of f are positions which are integers but you could replace IntegerQ by ValueQ here. –  Szabolcs Dec 13 '13 at 21:06
I see, so to get my list of first indices I guess I follow this with firstIndices=DeleteDuplicates@(f/@list) –  Timothy Wofford Dec 13 '13 at 21:14
@TimothyWofford it's more efficient to do f/@DeleteDuplicates[list] instead –  Szabolcs Dec 13 '13 at 21:16
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..." –  Mr.Wizard Dec 14 '13 at 1:10

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.

-

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.

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.

-