Erlangコンパイラ - パターンマッチングのパフォーマンスと基盤となるデータ構造

Question

基本的なデータ構造の使い方と、パターンマッチングのパフォーマンスはどうですか？特に、Trieを検索するパフォーマンスと比較します。

更新：私は、Erlangコンパイラによってどのようなパターンマッチングが実装されているかを簡潔かつ正確に理解しています。基礎となるデータ構造とは何ですか。パターンの検索効率はどれくらいですか？

Answer 1

パターンマッチングコンパイルはそれ自体が「基本的なデータ構造」を持たず、パターンのセットに従って任意のデータ構造を分解し、一致するものがあるかどうかを判断するのに必要なステップ数を最小限に抑えるための戦略です、または一致が不可能かどうかを判定します。

入力が文字列であり、パターンがその文字列の接頭辞である場合、その動作はtrie検索と同様です。 https://en.wikipedia.org/wiki/Trieから例をとるとアーラン・ケース・スイッチとしてそれを発現する：

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

句を複雑に全くガード表現が存在しないので、コンパイラは（種類および値によってそれらをソートする）より優れた効率のためにそれらを並べ替えるために自由です同じプレフィックスを共有するすべてのパターンが隣接するようにします。これはプログラマーにとって便利です。プログラマーは、手動でリストを整理しておくことに気にする必要はありません。

その後、コンパイラは、一連の句を最小数のテストを実行する多数のネストされた小文字の式に変換します。まず、最初の文字がA、i、またはtであるかどうかをチェックします。そうでない場合は、一致するものはありません。そうでない場合は、残りの文字列を調べるために分岐します。たとえば、最初の文字がiだった場合は、次の文字がnか文字列の最後かどうかを確認します。また、どちらも一致しない場合は、一致しない可能性があります。そうでない場合は、再び分岐します。そして、すべてのパターンのすべての枝を調べるためのコードを生成します。