Advanced

Cost of a pattern

A pattern that fails can spend a long time failing. The cost comes from backtracking, and the shape of the pattern decides how much.

What you will see

About 1 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Check the cost shape.

Nested run.

import re print(bool(re.match("(a+)+b", "aaaaab")))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

True

Flat run.

import re print(bool(re.match("a+b", "aaaaab")))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

True

Give back fails.

import re print(bool(re.match("a*b", "aaa")))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

False

Input length.

text = "a" * 6 print(len(text))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Data Flow

The engine walks the text, and on a failure it returns to earlier choices, each one costing another pass.

1 walk the text

↓

2 hit a failure

↓

3 return to a choice

↓

4 pay another pass

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

import re sets nothing on screen

print(bool(re.match("(a+)+b", "aaaaab"))) True

Why this works

Backtracking is the cost

Each give back is another try. A pattern with two nested repetitions can try an exponential number of splits.

Cap the input

A length limit fixes the worst case without changing the pattern. That is the cheapest fix when the pattern is shared.

Examples

Nested repetition

import re
print(bool(re.match("(a+)+b", "aaaaab")))

A repetition inside a repetition can try many splits of the same run.

A class instead

import re
print(bool(re.match("a+b", "aaaaab")))

One run of a class has one way to split. The cost stays linear.

Anchored failure

import re
print(bool(re.match("a*b", "aaa")))

The star gives back every a before failing. That is linear give back.

No give back

import re
print(bool(re.match("a+b", "aaa")))

A flat run has one split, so a failure costs one pass.

Time the miss

import re
print(len(re.findall("a*b", "aaa")))

Time the failing input, not the matching one. The miss is where the cost hides.

Bound the input

text = "a" * 6
print(len(text))

A length cap makes the worst case fixed. That is cheaper than a smarter pattern.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Validating a value

Previous Lesson

Validating a value

Next Lesson

Pattern tools

Pattern tools →