8
$\begingroup$

While working on a solution to another question, I noticed some performance regression slow performance of SequenceCases and friends. Consider a problem of finding zeroes of a function, given a sorted table of its values:

$Version (* "13.2.0 for Mac OS X x86 (64-bit) (November 18, 2022)" *)

zeros[lst_] := SequenceCases[lst, {a_, b_} /; Sign[a[[2]]] != Sign[b[[2]]]]

For simplicity, instead of finding zeros, we find intervals containing them.

zeros[Table[{t, Sin[t]}, {t, 0, 5, 0.1}]] 
(* {{{0., 0.}, {0.1, 0.0998334}}, {{3.1, 0.0415807}, {3.2, -0.0583741}}} *)

Using SequenceCases with pattern matching results in a very compact code. Unfortunately, this code has some terrible performance characteristics: e.g., asking SequenceCases to process a list of 1000 elements takes considerable time:

zeros[Table[{t, Sin[t]}, {t, 0, 100, 0.1}]] // Length // AbsoluteTiming
(* {1.68121, 32} *)

zeros[Table[{t, Sin[t]}, {t, 0, 200, 0.1}]] // Length // AbsoluteTiming 
(* {12.2768, 64} *)

Notice that non-linear growth in the execution time: it increases by 7.3x while the input double in size.

Now compare this to a straightforward alternative using a loop, which is almost instantaneous:

fastZeros[lst_] := 
 First[Reap[
    Do[If[Sign[lst[[i, 2]]] != Sign[lst[[i + 1, 2]]], 
      Sow[{lst[[i]], lst[[i + 1]]}]], {i, Length[lst] - 1}]][[2]], {}]

With[{data = Table[{t, Sin[t]}, {t, 0, 5, 0.1}]}, 
 fastZeros[data] == zeros[data]] (* True *)

fastZeros[Table[{t, Sin[t]}, {t, 0, 200, 0.1}]] // Length // AbsoluteTiming 
(* {0.003667, 64} *)

While I expect to have some speed tradeoff when using more powerful language constructs like pattern matching, it still seems like a severe performance penalty. Similar things were discussed before.

Does anyone has any more charitable explanation of the observed behavior other than "it's a bug that should be reported to Wolfram Research"?

Update. Notice, in particular, that it's not the pattern matching that is slow - it's speedy:

zeros2[lst_] := 
 Cases[Partition[lst, 2, 1], {a_, b_} /; Sign[a[[2]]] != Sign[b[[2]]]]

With[{data = Table[{t, Sin[t]}, {t, 0, 5, 0.1}]}, 
 fastZeros[data] == zeros[data] == zeros2[data]]
(* True *)

zeros2[Table[{t, Sin[t]}, {t, 0, 200, 0.1}]] // 
  Length // AbsoluteTiming
(* {0.004051, 64} *)

Update. Meanwhile, I've submitted [CASE:4999270].

$\endgroup$
11
  • 3
    $\begingroup$ Just wanted to point out that this is not a speed regression as far as I can tell. It was (alas) always this slow. $\endgroup$ Jan 25, 2023 at 17:56
  • $\begingroup$ Thanks, @DanielLichtblau - you are right. I shouldn't call it a "regression" which presumes a deterioration of performance. I changed the title to reflect that. Rather, it's an observation that a pretty useful function is not optimized for what seems to be a natural use case. $\endgroup$
    – Victor K.
    Jan 25, 2023 at 18:02
  • 2
    $\begingroup$ With SeedRandom[0]; data = RandomInteger[1000, 2000];, Compare SequenceCases[data, {11, x_}] // AbsolutTiming versus SequenceCases[data, {11, x_} /; True] // AbsolutTiming Seems to be a consequence of using Condition $\endgroup$
    – Michael E2
    Jan 25, 2023 at 18:20
  • 2
    $\begingroup$ (@MichaelE2 bat me to this) I just noticed we have an open bug report to the effect that Condition can severely slow SequenceCases. Also using Alternatives causes a severe speed degradation as compared to two cases without alternatives. $\endgroup$ Jan 25, 2023 at 18:25
  • 1
    $\begingroup$ This example is now in a suggestion/bug report. $\endgroup$ Jan 26, 2023 at 17:46

1 Answer 1

4
$\begingroup$

As of 13.3.1, this particular performance issue is fixed:

enter image description here

$\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.