# 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
add comment

## 3 Answers

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
show 3 more comments

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.

-
add comment

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

-
add comment