Message334956
| Author | benspiller |
|---|---|
| Recipients | benspiller, ezio.melotti, mrabarnett |
| Date | 2019-02-06.16:57:17 |
| SpamBayes Score | -1.0 |
| Marked as misclassified | Yes |
| Message-id | <1549472237.36.0.409975452288.issue35915@roundup.psfhosted.org> |
| In-reply-to |
| Content | |
|---|---|
Running this command:
time python -c "import re; re.compile('y.*x').search('y'*(N))"
It's clearly quadratic:
N=100,000 time=7s
N=200,000 time=18s
N=400,000 time=110s
N=1,000,000 time=690s
This illustrates how a simple program that's working correctly can quickly degrade to a very long period of unresponsiveness after some fairly modest increases in size of input string. |
|
| History | |||
|---|---|---|---|
| Date | User | Action | Args |
| 2019-02-06 16:57:18 | benspiller | set | recipients: + benspiller, ezio.melotti, mrabarnett |
| 2019-02-06 16:57:17 | benspiller | set | messageid: <1549472237.36.0.409975452288.issue35915@roundup.psfhosted.org> |
| 2019-02-06 16:57:17 | benspiller | link | issue35915 messages |
| 2019-02-06 16:57:17 | benspiller | create | |