How to tell when a job is too big for the pattern matcher?

Question

Pattern matching is great but it has its limitations. Consider sorting a list of numbers from smallest to largest:

RandomSample[Range[10]] //. {a___, b_, c_, d___} /; b > c :> {a, c, b, d}

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

However, running

RandomSample[Range[1000]] //. {a___, b_, c_, d___} /; b > c :> {a, c, b, d}

ReplaceRepeated::rrlim: Exiting after {<<1000>>} scaned 65536 times. >>
{1, 2, 3, 4, 5, 6, 7, 9, 11, 13, <<990>>}

is a different story. The code takes a long time to run and the resulting output is not sorted properly.

Now, obviously, we would want to use Sort in this type of scenario, but now I'm curious to know: at what point does a job become too computationally intensive for the pattern matcher?

Answer 1

Rather than it being "too big" for the pattern matcher, the problem here is because of the use of //. which applies the rule repeatedly till the result no longer changes (i.e. the list is sorted). In other words, the issue is that of the complexity of the algorithm you're using (//. with ___) rather than the programming paradigm that you've chosen (pattern matching). If you implemented the same algorithm in a procedural style, you'll experience the same degree of "slowness".

You can perform a simple test to see how your algorithm scales:

ClearAll@iters
iters[n_Integer] := iters[n] = 
    Table[FixedPointList[
            ReplaceAll[#, {a___, b_, c_, d___} /; b > c :> {a, c, b, d}] &, 
            RandomSample[Range[n]]
        ] // Length, 
        {10}] // Mean // N

plot = DiscretePlot[iters[n], {n, 50}]

This looks like $\mathcal{O}(n^2)$, which you can confirm with

fit = FindFit[iters /@ Range@50, c x^n, {c, n}, x]
(* {c -> 0.227266, n -> 2.02332} *)

plot ~Show~ Plot[c x^n /. fit, {x, 0, 50}, PlotStyle -> Red]

So it is not surprising that for $n=1000$, you are performing ~ 267,000 replacements, which is the primary reason for your slowness.

As Oleksandr has pointed out, you can modify MaxIterations to remove the soft limit of 65536 iterations, but I'd strongly advise against making a habit of it, and instead urge you to investigate the specific pattern/choice of algorithm used.