7
$\begingroup$

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 GroupTheory`Tools`SublistPosition, but if I call it directly, I get very modest performance improvement and arrays are still getting unpacked:

RepeatedTiming[GroupTheory`Tools`SublistPosition[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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.