Компилятор 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 

Поскольку нет защитного выражения усложнять положения, компилятор может свободно изменять порядок их для лучшей эффективности (сортировки их по типу и стоимости) , так что все шаблоны, которые имеют один и тот же префикс, смежны. Это удобно для программиста, которому не нужно заботиться о том, чтобы вручную вести список в порядке.

После этого компилятор превратит набор предложений в несколько вложенных меньших выражений case, выполняющих минимальное количество тестов. Во-первых, он будет проверять, является ли первый символ A, i или t. Если нет, не может быть соответствия, иначе ветвь для проверки остальной части строки; например, если первый символ был i, проверьте, является ли следующий символ n или концом строки. Опять же, если это не так, тогда не может быть соответствия, иначе ветвь снова. И так далее, генерируя код для изучения всех ветвей всех шаблонов.