知识卡片
嵌套量词引爆回溯
当内部重复和外部重复都能分配同一串字符时,如普通字符段+再被外部*重复,同一文本可有大量不同分段。首条成功路径看起来很快,缺少闭合符等失败输入却可能迫使回溯遍历这些分割,工作量随长度急剧增长。问题是重叠的分配选择,不是看到嵌套符号就必定指数,也不能凭成功样例排除失败风险。实际优化、上限与输入结构会改变表现。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 嵌套量词引爆回溯
原书出处 · 1 处
- · 查看原书依据
加号和星号二者分割(divvy up)字符串的可能性是成指数形式增长的。如果目标字符串是 makudonarudo,是星号会迭代12次,每一次迭代中「[^\\"]+」匹配一个字符(就像这样)?还是星号迭代3次,内部的「[^\\"]+」分别匹配 5、3、4 个字符(’)?
参考来源
- 位置:《精通正则表达式(第3版)》典型示例(spine 39;来源项目book-sources,`extracted/精通正则表达式(第3版)/_epub-src/text/part0011_split_001.html`;来源键`s039-ch06-008`)。
- 结论依据:本项全文及执行图/代码/结果表已实际读取;统计只作原书模型和原书测试说明,未实际运行。
- 原始内容:加号和星号二者分割(divvy up)字符串的可能性是成指数形式增长的。如果目标字符串是 makudonarudo,是星号会迭代12次,每一次迭代中「[^\\"]+」匹配一个字符(就像这样)?还是星号迭代3次,内部的「[^\\"]+」分别匹配 5、3、4 个字符(’)?