Burstsort - Burstsort

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Července 2017) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Burstsort a jeho varianty jsou algoritmy pro třídění účinné v mezipaměti struny. Jsou to varianty tradičního radix sort ale rychlejší pro velké datové sady běžných řetězců, poprvé publikovaných v roce 2003, s některými optimalizačními verzemi publikovanými v pozdějších letech.^[1]

Burstortovy algoritmy používají a trie ukládat předpony řetězců s pěstitelné pole ukazatelů jako koncových uzlů obsahujících tříděné, jedinečné přípony (označované jako kbelíky). Některé varianty kopírují ocasy řetězců do kbelíků. Jak kbelíky rostou nad předem stanovenou prahovou hodnotu, kbelíky jsou „rozbité“ do pokusů a dávají názvu jeho název. Novější varianta používá index segmentu s menšími dílčími segmenty ke snížení využití paměti. Většina implementací deleguje na multikey quicksort, rozšíření třícestného radix quicksort, aby seřadil obsah kbelíků. Rozdělením vstupu na kbelíky s běžnými předponami lze třídění provést efektivně pomocí mezipaměti.

Burstsort byl představen jako druh, který je podobný Třídění MSD radix,^[1] ale je rychlejší díky vědomí toho, že ukládání do mezipaměti a souvisejících radixů je uloženo blíže k sobě kvůli specifikům struktury trie. Využívá specifika řetězců, s nimiž se obvykle setkáváme v reálném světě. A i když asymptoticky je to stejné jako radix sort, s časovou složitostí Ó(wn) (w - délka slova a n - počet řetězců, které mají být tříděny), ale kvůli lepší distribuci paměti to má tendenci být dvakrát rychlejší u velkých datových sad řetězců. Bylo označováno jako „nejrychleji známý algoritmus pro třídění velkých sad řetězců“.^[2]

Reference

• Burstortový derivát (C-burstort), rychlejší než burstort: Sinha, Ranjan; Zobel, Justin; Ring, David (leden 2006). "Třídění řetězců pomocí mezipaměti pomocí kopírování" (PDF). Journal of Experimental Algorithmics. 11 (1.2): 1.2. CiteSeerX  10.1.1.85.3498. doi:10.1145/1187436.1187439. Archivovány od originál (PDF) dne 01.10.2007. Citováno 2007-05-31.
• Datový typ použitý v burstortu: Heinz, Steffen; Zobel, Justin; Williams, Hugh E. (duben 2002). „Burst Tries: Rychlá a efektivní datová struktura pro řetězce kláves“ (PDF). Transakce ACM v informačních systémech. 20 (2): 192–223. CiteSeerX  10.1.1.18.3499. doi:10.1145/506309.506312. Archivovány od originál (PDF) dne 2013-12-05. Citováno 2007-09-25.
• Sinha, Ranjan; Zobel, Justin (2003). „Efektivní třídění velkých sad řetězců podle trie“ (PDF). Sborník z 26. australasské konference o informatice. 16. str. 11–18. CiteSeerX  10.1.1.12.2757. ISBN  978-0-909-92594-9.
• Sinha, Ranjan; Wirth, Anthony (březen 2010). „Engineering Burstsort: Směrem k rychlému třídění řetězců na místě“ (PDF). ACM Journal of Experimental Algorithmics. 15 (2.5): 1–24. doi:10.1145/1671970.1671978.

externí odkazy

• Burstortová implementace v Javě: burstsort4j
• Judy pole jsou typem kopírování: C implementace