얼랭 컴파일러 - 패턴 매칭 성능과 기본 데이터 구조

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 또는 문자열의 끝인지 확인하십시오. 다시 말하지만, 둘 다 아니면 일치가 없거나, 다시 분기 할 수 있습니다. 그리고 모든 패턴의 모든 가지를 검사하는 코드를 생성합니다.