Erlang 编译器 - 模式匹配性能和底层数据结构

Question

我想知道使用的底层数据结构是什么，模式匹配的性能如何？特别是，与搜索 Trie 的性能相比。

更新：我正在寻找对 Erlang 编译器实现的模式匹配是什么的简明而准确的理解。底层数据结构是什么，搜索模式的效率如何？

Answer 1

模式匹配编译本身没有 "underlying data structure" - 它只是一种根据一组模式分解任何给定数据结构并最小化判断匹配是否匹配所需的步骤数的策略找到，或者是否无法匹配。

如果您的输入是一个字符串并且模式是该字符串的前缀，那么行为就像 trie 搜索一样。以 https://en.wikipedia.org/wiki/Trie 中的示例并将其表示为 Erlang 大小写开关：

case String of
    "tea" ->  3;
    "ted" ->  4;
    "inn" ->  5;
    "to"  ->  7;
    "in"  ->  9;
    "i"   -> 11;
    "ten" -> 12;
    "A"   -> 15
end

由于没有保护表达式使子句复杂化，编译器可以自由地对它们重新排序以提高效率（按类型和值对它们进行排序），以便共享相同前缀的所有模式都是相邻的。这对程序员来说很方便，他们不必关心手动保持列表的顺序。

之后，编译器会将子句集转换为许多嵌套的较小 case 表达式，执行最少数量的测试。首先，它会检查第一个字符是 A、i 还是 t。如果不是，则不能匹配，否则分支检查字符串的其余部分；例如，如果第一个字符是 i，则检查下一个字符是 n 还是字符串的结尾。同样，如果两者都不是，则不能匹配，否则再次分支。依此类推，生成代码来检查所有模式的所有分支。

Erlang 编译器 - 模式匹配性能和底层数据结构

Erlang Compiler - Pattern Matching Performance and Underlying Data Structure

compiler-construction

erlang

pattern-matching