2
$\begingroup$

SequencePosition returns only the first sequence in a list that matches a given pattern with

SequencePosition[list,pattern,1]

But it looks like it still pattern-matches the entire list anyway! This code gives it a trivial example which should be constant time but in fact exhibits exponential time complexity:

trailingCharacters[n_] := 
  trailingCharacters[n] = 
   Characters["abcdefg"]~Join~
    RandomChoice[CharacterRange["a", "z"], Floor[10^n]];

Table[trailingCharacters[n], {n, 1, 8, 0.25}];

ListLogPlot[Table[
  Timing[
    SequencePosition[
        trailingCharacters[n],
        Characters["abcdefg"],
        1
     ]
    ][[1]],
  {n, 1, 8, 0.25}
  ]]

Is this a bug? If it's not a bug, is there a slick way to tell Mathematica to stop pattern-matching after finding the first sequence?

$\endgroup$
3
  • 1
    $\begingroup$ You are timing not only execution of SequencePosition but also creation of the list by trailingCharacters and also joining it with another list in Characters["abcdefg"]~Join~ so your code has no relevance in judging performance of SequencePosition. First create all the joined lists and then time only execution of SequencePosition on those lists. $\endgroup$ Dec 6, 2022 at 19:47
  • $\begingroup$ @azerbajdzan you are correct about the Join operation but not about the creation of trailingCharacters, which is memoized. I'll change the post but it doesn't have a qualitative effect. $\endgroup$
    – Diffycue
    Dec 6, 2022 at 20:35
  • $\begingroup$ So once you removed Join from Timing all timings are zero, i.e. all equally fast executed by SequencePosition. $\endgroup$ Dec 6, 2022 at 21:00

1 Answer 1

4
$\begingroup$

No exponential increase of time can be seen bellow:

data = Table[
   Characters["abcdefg"]~Join~
    RandomChoice[CharacterRange["a", "z"], Floor[10^n]], {n, 1, 8, 
    0.25}];
AbsoluteTiming[SequencePosition[#, Characters["abcdefg"], 1]] & /@ data
Clear[data]

(* {{0.000144, {{1, 7}}}, {0.0000632, {{1, 7}}}, {0.0000572, {{1, 
    7}}}, {0.0000536, {{1, 7}}}, {0.0000528, {{1, 
    7}}}, {0.0000481, {{1, 7}}}, {0.000052, {{1, 
    7}}}, {0.0000497, {{1, 7}}}, {0.000053, {{1, 
    7}}}, {0.0000505, {{1, 7}}}, {0.0000498, {{1, 
    7}}}, {0.0000514, {{1, 7}}}, {0.0000564, {{1, 
    7}}}, {0.000051, {{1, 7}}}, {0.0000474, {{1, 
    7}}}, {0.0000502, {{1, 7}}}, {0.0000491, {{1, 
    7}}}, {0.0000503, {{1, 7}}}, {0.0000569, {{1, 
    7}}}, {0.0000503, {{1, 7}}}, {0.000063, {{1, 
    7}}}, {0.0000502, {{1, 7}}}, {0.0000459, {{1, 
    7}}}, {0.0000501, {{1, 7}}}, {0.0000474, {{1, 
    7}}}, {0.0000485, {{1, 7}}}, {0.0000466, {{1, 
    7}}}, {0.0000481, {{1, 7}}}, {0.0000459, {{1, 7}}}} *)

On the other hand if we use OP code we can see that first time table of trailingCharacters is executed it takes some increasing time. On the second execution of the same table we have all zeros times because the result was memorized from first run.

But then if we execute Timing[Identity[trailingCharacters[8]]][[1]] twice in a row we again have big time for the first run and zero for the second run even though no SequencePosition was used but just Identity.

Why it happens? I think maybe because of using memory caching because trailingCharacters[8] is quite large about 4GB.

trailingCharacters[n_] := 
  trailingCharacters[n] = 
   Characters["abcdefg"]~Join~
    RandomChoice[CharacterRange["a", "z"], Floor[10^n]];

Table[Timing[trailingCharacters[n]][[1]], {n, 1, 8, 0.25}]
Table[Timing[trailingCharacters[n]][[1]], {n, 1, 8, 0.25}]

Timing[Identity[trailingCharacters[8]]][[1]]
Timing[Identity[trailingCharacters[8]]][[1]]

Out[3]= {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., \
0., 0., 0., 0.015625, 0., 0.03125, 0.03125, 0.046875, 0.09375, \
0.15625, 0.265625, 0.484375, 0.78125, 1.53125}

Out[4]= {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., \
0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.}

Out[5]= 1.53125

Out[6]= 0.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.