Burstsort - Burstsort
Clase | Algoritmo de clasificación |
---|---|
Estructura de datos | Trie |
Rendimiento en el peor de los casos | O ( wn ) |
Complejidad espacial en el peor de los casos | O ( wn ) |
Burstsort y sus variantes son algoritmos eficientes en caché para ordenar cadenas . Son variantes del tipo de radix tradicional, pero más rápidas para grandes conjuntos de datos de cadenas comunes, publicadas por primera vez en 2003, con algunas versiones optimizadoras publicadas en años posteriores.
Los algoritmos Burstsort utilizan un trie para almacenar prefijos de cadenas, con matrices de punteros que se pueden aumentar como nodos finales que contienen sufijos únicos y ordenados (denominados depósitos ). Algunas variantes copian las colas de las cuerdas en los cubos. A medida que los cubos crecen más allá de un umbral predeterminado, los cubos se "reventan" en intentos, dando al género su nombre. Una variante más reciente usa un índice de depósito con subgrupos más pequeños para reducir el uso de memoria. La mayoría de las implementaciones delegan en el ordenamiento rápido de múltiples claves, una extensión del ordenamiento rápido de radix de tres vías, para ordenar el contenido de los depósitos. Al dividir la entrada en depósitos con prefijos comunes, la clasificación se puede realizar de manera eficiente en caché.
Burstsort se introdujo como un tipo que es similar al tipo de radix de MSD , pero es más rápido debido a que es consciente de que el almacenamiento en caché y los radixes relacionados se almacenan más cerca entre sí debido a las características específicas de la estructura de trie. Aprovecha las características específicas de las cadenas que normalmente se encuentran en el mundo real. Y aunque asintóticamente es lo mismo que el ordenamiento por radix, con una complejidad de tiempo de O ( wn ) ( w - longitud de palabra yn - número de cadenas a ordenar), pero debido a una mejor distribución de la memoria, tiende a ser el doble de rápido en grandes conjuntos de datos de cadenas. Ha sido catalogado como el "algoritmo conocido más rápido para clasificar grandes conjuntos de cadenas".
Referencias
- Un derivado de burstsort (C-burstsort), más rápido que burstsort: Sinha, Ranjan; Zobel, Justin; Ring, David (enero de 2006). "Clasificación de cadenas con uso de caché eficaz mediante copia" (PDF) . Revista de algoritmos experimentales . 11 (1,2): 1,2. CiteSeerX 10.1.1.85.3498 . doi : 10.1145 / 1187436.1187439 . S2CID 3184411 . Archivado desde el original (PDF) el 2007-10-01 . Consultado el 31 de mayo de 2007 .
- El tipo de datos utilizado en burstsort: Heinz, Steffen; Zobel, Justin; Williams, Hugh E. (abril de 2002). "Burst Tries: una estructura de datos rápida y eficiente para claves de cadena" (PDF) . Transacciones ACM sobre sistemas de información . 20 (2): 192-223. CiteSeerX 10.1.1.18.3499 . doi : 10.1145 / 506309.506312 . S2CID 14122377 . Archivado desde el original (PDF) el 5 de diciembre de 2013 . Consultado el 25 de septiembre de 2007 .
- Sinha, Ranjan; Zobel, Justin (2003). "Clasificación eficiente basada en Trie de grandes conjuntos de cadenas" (PDF) . Actas de la 26ª Conferencia de Ciencias de la Computación de Australasia . 16 . págs. 11-18. CiteSeerX 10.1.1.12.2757 . ISBN 978-0-909-92594-9. Archivado desde el original (PDF) el 8 de febrero de 2012 . Consultado el 25 de septiembre de 2007 .
- Sinha, Ranjan; Wirth, Anthony (marzo de 2010). "Engineering Burstsort: Hacia una clasificación rápida de cadenas en el lugar" (PDF) . Revista ACM de algoritmos experimentales . 15 (2.5): 1–24. doi : 10.1145 / 1671970.1671978 . S2CID 16410080 .
enlaces externos
- Una implementación de burstsort en Java: burstsort4j
- Las matrices Judy son un tipo de copia burstsort: implementación de C