Rust 사전 아나그램 묶기, 글자별 소수곱으로 64비트 키 구성

David G. Andersen은 글자 하나를 바꾸거나 더하고 빼거나 아나그램으로 바꾸며 단어 사이를 이동하는 Word Ladder 변형 퍼즐을 풀 Rust 프로그램을 만들면서, 사전 전체에서 아나그램 단어를 묶는 인덱스를 최적화했습니다. 측정 대상은 이미 메모리에 읽어 둔 Scrabble 사전 178,690개 항목으로 인덱스를 만드는 구간입니다. Andersen은 이 아나그램 그룹을 다음 글의 퍼즐 풀이에 이용하겠다고 밝혔습니다.

첫 구현은 각 단어의 글자를 알파벳순으로 정렬한 문자열을 해시 키로 삼고, 같은 키를 가진 단어를 Vec에 모았습니다. 이 방식은 31ms, 항목당 173ns가 걸렸습니다. 키마다 단어 목록용 Vec를 만들거나 늘려야 했는데, 사전 항목은 178,690개인 반면 키는 161,019개여서 대부분의 그룹에는 단어가 하나씩만 들어갔습니다.

Andersen은 단어가 하나뿐인 그룹은 원본 사전의 단어 번호로 바로 가리키고, 여러 단어가 있는 그룹만 연결 배열로 저장했습니다. 해시 테이블 값에 쓰는 u32의 상위 비트를 표시로 활용해, 직접 저장한 단어 번호와 next·word 배열을 참조하는 목록 위치를 구별했습니다. 이 변경으로 인덱스 구축 시간은 20ms, 항목당 112ns로 줄었습니다.

다음에는 정렬된 문자열 대신 글자별 개수를 키로 썼습니다. 대문자 A-Z의 각 개수를 4비트로 저장하면, 글자 하나가 15번을 넘게 반복되지 않는다는 전제 아래 총 104비트가 필요해 u128에 담을 수 있습니다. 정렬과 새 문자열 생성이 사라져 시간이 5.6ms로 줄었습니다. 이 단계부터 결과도 달라졌습니다. 아나그램이 없는 단어까지 포함한 사전 대신, 실제 아나그램 그룹만 반환했습니다. 이어 공격자가 해시 입력을 고르는 상황을 고려할 필요가 없는 경우 더 빠른 FxHashMap을 사용해 4.1ms를 기록했습니다.

글자별 소수를 곱해 단어의 키를 만드는 방식에서는, 곱이 64비트 범위를 넘지 않는 한 소인수분해의 유일성에 따라 글자 순서가 달라도 같은 글자 구성은 같은 값을 만들고 다른 구성은 다른 값을 만듭니다. 반대로 곱이 정수 범위를 넘으면 값이 순환해 서로 다른 구성이 같은 키를 얻을 수 있습니다. 알파벳 순서대로 작은 소수를 배정한 기본안은 Scrabble 사전의 365번째 단어 ABORTIVENESSES에서 64비트 범위를 넘었습니다.

Andersen은 사전의 단어 길이와 글자 반복 패턴에 맞춰 소수 배정표를 조정했습니다. 예컨대 E에는 2, N에는 19, S에는 17을 배정했고, J가 두 번 이상 나오는 가장 긴 단어가 12글자라는 점을 반영해 J에는 101을 썼습니다. 처음 오버플로를 일으키는 단어를 찾아 관련 소수를 낮은 값으로 바꾸는 프로그램도 만들었습니다. 이렇게 조정한 배정표는 해당 Scrabble 사전의 모든 단어를 처리할 때 오버플로가 발생하지 않았고, 인덱스 구축 시간은 2.6ms였습니다. 충돌 없는 키라는 성질은 이 소수 배정에 사용한 사전의 범위에 적용됩니다.

마지막 최적화에서는 사전 단어를 문자당 5비트로 u128에 담고, 곱을 두 개의 독립 누산기로 계산했습니다. 이 단계에서 시간은 2.3ms로 줄었습니다. 이어 모든 단어를 16글자로 처리하고, 뒤쪽의 빈 자리는 소수표에서 값이 1인 항목에 대응시켜 반복문의 길이 확인 분기를 없앴습니다. 곱 계산과 해시 테이블 삽입도 분리해 컴파일러가 곱셈 반복을 자동 벡터화하도록 했습니다. 최종 인덱스 구축 시간은 1.96ms, 항목당 10.9ns였습니다.

초기 방식과 최종 구현을 비교한 15.8배라는 수치에는 데이터 구조와 키 표현의 변경뿐 아니라 중간 단계부터 반환 결과를 실제 아나그램 그룹으로 좁힌 효과도 들어갑니다. 모든 시간은 Andersen이 자신의 MacBook Pro M1에서 측정한 값입니다. 특정 단어 하나의 아나그램만 찾는 경우에는 더 단순한 해시 테이블로도 충분할 수 있다고 덧붙였습니다.