知识卡片

普通读书笔记卡 · 1914.f.1

成功加速不保证失败成本可控

理解等级:中级

传统回溯式引擎可在首次完整成功后停止,但失败需要排除仍可行的路径。把逐字符处理改为连续段,可能减少成功时的循环,却同时增加失败时的分段组合。验证效率至少要分别考虑匹配与不匹配,并选择能触发关键分支的输入;原书的极大耗时是模型说明,不能直接当作当今某引擎的实测上界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      如果没有完整匹配,即使是传统型NFA也需要尝试所有的可能,在找到之前。即使是前面提到的"No·\"match\"·here这样短短的字符串,在报告失败之前,也需要尝试8 192种可能。 在正则引擎忙于尝试这些数量庞大的可能时,整个程序看起来好像“锁死(lock up)”

    参考来源

    - 位置:《精通正则表达式(第3版)》典型示例(spine 39;来源项目book-sources,`extracted/精通正则表达式(第3版)/_epub-src/text/part0011_split_001.html`;来源键`s039-ch06-011`)。 - 结论依据:本项全文及执行图/代码/结果表已实际读取;统计只作原书模型和原书测试说明,未实际运行。 - 原始内容:如果没有完整匹配,即使是传统型NFA也需要尝试所有的可能,在找到之前。即使是前面提到的"No·\"match\"·here这样短短的字符串,在报告失败之前,也需要尝试8 192种可能。 在正则引擎忙于尝试这些数量庞大的可能时,整个程序看起来好像“锁死(lock up)”