버스토트

Burstsort
버스토트
클래스정렬 알고리즘
데이터 구조트라이
최악의 경우 공연O(wn)
최악의 경우 공간 복잡성O(wn)

버스토트와 그 변형은 문자열을 정렬하기 위한 캐시 효율적 알고리즘이다.그것들은 전통적인 라딕스 종류의 변형이지만 2003년에 처음 출판된 공통 문자열의 대용량 데이터 세트에서는 더 빠르며, 일부 최적화 버전은 후년에 출판되었다.[1]

버스트포트 알고리즘은 문자열 접두사를 저장하기 위해 트라이를 사용하며, 포인터 배열이 정렬되고 고유하며 접미사가 포함된 엔드 노드(버킷이라고도 함)로 확장 가능한 포인터 배열을 사용한다.어떤 변형들은 끈 꼬리를 양동이에 복사한다.버킷이 미리 정해진 임계값을 초과하여 증가하면 버킷이 "버스트"되어 시도되며, 이 버킷의 이름이 지정된다.보다 최근의 변종은 메모리 사용을 줄이기 위해 하위 버킷이 더 작은 버킷 색인을 사용한다.대부분의 구현은 버킷의 내용을 정렬하기 위해 3방향 라디ix 퀵 소트의 확장인 멀티키 퀵 소트에 위임한다.입력을 공통 접두사가 있는 버킷으로 나누면 캐시 효율적 방식으로 정렬이 가능하다.

버스토트는 MSD라믹스 종류와 비슷하지만 트리 구조의 특성상 캐싱과 관련 라디스가 서로 가까이 저장되는 것을 인지하고 있어 속도가 빠르다.[1]그것은 보통 현실에서 마주치는 현악의 세부사항을 악용한다.그리고 무증상으로는 라딕스 분류와 동일하지만, 시간 복잡성은 O(wn) (w - word length 및 n - 정렬할 문자열 수)이지만 메모리 분포가 좋아져 문자열의 빅데이터 집합에서는 2배 빠른 경향이 있다.그것은 "큰 문자열 집합을 정렬하는 가장 빠른 알고리즘"[2]으로 간주되었다.

참조

  1. ^ a b Sinha, R.; Zobel, J. (2005). "Cache-conscious sorting of large sets of strings with dynamic tries" (PDF). Journal of Experimental Algorithmics. 9: 1.5. CiteSeerX 10.1.1.599.861. doi:10.1145/1005813.1041517. S2CID 10807318.
  2. ^ "Burstsort: Fastest known algorithm to sort large set of strings Hacker News".
  • Aburstsort 유도체(C-burstsort), 더 빨리 burstsort보다 신하, 인도의;Zobel, 저스틴, 반지, 데이비드(2006년 1월)."Cache-Efficient 현악 분류를 이용한 카핑"(PDF).실험 Algorithmics의. 11(1.2):는. CiteSeerX 10.1.1.85.3498. doi:10.1145/1187436.1187439.S2CID 3184411.2007-10-01에 있는 원본(PDF)에서 Archived.2007-05-31 Retrieved.
  • 데이터 형식 burstsort에:.하인즈, 콘래드, Zobel, 저스틴, 윌리엄스, 휴 E.(2002년 4월)."CPU사용 Tries:A패스트, 효율적 데이터 구조 String키에"(PDF).정보 시스템에 ACMTransactions이. 20(2):192–223.CiteSeerX 10.1.1.18.3499. doi:10.1145/506309.506312.S2CID 14122377.2013-12-05에 있는 원본(PDF)에서 Archived.2007-09-25 Retrieved.
  • Sinha, Ranjan; Zobel, Justin (2003). "Efficient Trie-Based Sorting of Large Sets of Strings" (PDF). Proceedings of the 26th Australasian Computer Science Conference. Vol. 16. pp. 11–18. CiteSeerX 10.1.1.12.2757. ISBN 978-0-909-92594-9. Archived from the original (PDF) on 2012-02-08. Retrieved 2007-09-25.
  • Sinha, Ranjan; Wirth, Anthony (March 2010). "Engineering Burstsort: Towards Fast In-Place String Sorting" (PDF). ACM Journal of Experimental Algorithmics. 15 (2.5): 1–24. doi:10.1145/1671970.1671978. S2CID 16410080.

외부 링크