# Fast find sublist in a list procedure (for packed arrays of integers)

I want to find a first position of sublist inside a list, where both lists are packed arrays of integers. A typical list has millions of elements, while sublist has just a few elements. The question is: how to do this efficiently?

Built in function SequencePosition unpacks the arrays (even more than once) and is therefore very slow:

On["Packing"]

list = Reverse[Range[10^7]];
sublist = {5, 4, 3, 2, 1};

RepeatedTiming[SequencePosition[list, sublist]]


{1.0, {{9999996, 10000000}}}

It takes about one second, but I expect that a good string search algorithm should run much faster. It is clear that SequencePosition is too general for this task, because it also accepts patterns instead of sublist.

After some research I found that SequencePosition calls undocumented built-in function GroupTheoryToolsSublistPosition, but if I call it directly, I get very modest performance improvement and arrays are still getting unpacked:

RepeatedTiming[GroupTheoryToolsSublistPosition[list, sublist, Infinity, True, True]]


{0.68, {{9999996, 10000000}}}

Is there an efficient procedure to find the first position of sublist inside a list without unpacking?

• Have a look at the seqposC function from this answer. My measurements show that it is about 20 - 25x faster (requires a C compiler). – Leonid Shifrin May 1 '17 at 18:28