인기 태그：
가상화 DNS 보안 형식적 검증 도달 가능성 분석 C언어 경제 컴파일러 오류 매크로 충돌 웹 확장 기능 개발 프레임워크 모든 태그

개선된 p-fast Trie: 매우 효율적인 접두사 매칭 알고리즘

2025-08-10

이 글에서는 문자열 집합에서 쿼리 문자열과 가장 일치하는 접두사 또는 가장 가까운 선행자/후속자를 찾는 매우 효율적인 알고리즘인 개선된 p-fast Trie 데이터 구조를 소개합니다. 이전 버전과 비교하여 이 개선된 버전은 더 간결하고 공간 효율적입니다. 고유한 접두사마다 해시 테이블을 사용하고 각 접두사의 가능한 후속 문자를 비트맵으로 표현하여 O(log k)의 시간 복잡도를 달성합니다(k는 키의 길이). 선행자 검색에는 더 많은 프로브가 필요할 수 있지만, 성능은 기존 qp-trie를 능가합니다.

더 보기
(dotat.at)
개발 접두사 매칭

컴파일러 최적화: Lemire의 거의 나눗셈 없는 난수 생성 개선

2025-03-09

저자는 범위 내의 난수를 생성하는 거의 나눗셈이 없는 알고리즘(Lemire 알고리즘)을 개선했습니다. 이전 버전에서는 빠른 경로를 인라인화하여 코드 팽창을 줄였지만, 컴파일러 최적화는 제한적이었습니다. 저자는 상한이 컴파일 시 상수인 경우, 기각 임계값을 컴파일 시에 계산할 수 있으며, 나눗셈 회피는 불필요하다는 것을 발견했습니다. 새로운 구현에서는 난수 생성기 호출이 한 번만 이루어지며, 상한이 2의 거듭제곱인 경우 컴파일러가 루프를 자동으로 제거합니다. 이는 작년 버전보다 효율적이며, 저자는 Rust에서 유사한 컴파일 시 최적화 기술에 대해 논의하고 있습니다.

더 보기
(dotat.at)
개발 난수 생성 Lemire 알고리즘