在 BQN 里解析嵌套列表：三条路，一次段错误，四毫秒的最快解
来源：saltysylvi.github.io — 2023-01-23
📋 概述
Advent of Code 2022 第 13 天要解析 [1,[2,[3,[4,[5,6,7]]]],8,9] 这类嵌套列表，作者用 BQN 给出三种解法并做了基准测试。第一种是「作弊」：把方括号换成 BQN 的 ⟨⟩，交给 •BQN 求值——单行解析很轻松，但把整份输入拼成一个巨大列表时直接 core dumped，只能退回逐行解析，速度约 0.074 秒/次，非常慢。第二种是常规的递归下降：先分词再解析，作者强调这不是入门教程，而是想说明「普通算法在 BQN 里同样适用」，Singeli 本身就用了递归下降。第三种是数组风格解析器，两版迭代后是最快的（0.0043 秒），但作者形容实现过程极其难懂。
🔑 核心要点
- 最省事的 •BQN 方案只在 逐行解析时可用，拼成一个大列表就 core dumped，作者也没搞清具体原因。
- 递归下降版比 •BQN 快一个数量级：0.0071 秒对 0.074 秒，且对大列表同样有效。
- 数组风格解析器最终版 0.0043 秒，是唯一在「单个大字符串」路径上更快的方案，实现难度也最高。
- 关键技巧是把括号深度算成排序键，用 ⍋+\` 与 Group 一次批量组装子列表，不做逐层递归。
- 作者给了实用结论：AoC 这种量级用 •BQN 就够了；只有数据量很大、要反复复用解析器时，数组解法才值得写。
💡 金句
A well-written array style parser is the fastest (and coolest obviously), but wow is it confusing to implement!
← 返回 Lobsters 首页
👍 0
👎 0