La clasificación de cadenas por comparación (ej. Estándar QuickSort + función strcmp) puede ser un poco lenta, especialmente para cadenas largas que comparten un prefijo común (la función de comparación toma O (s) tiempo, donde s es el longitud de la cadena), por lo tanto, una solución estándar tiene la complejidad de O (s * nlog n). ¿Hay algún algoritmo conocido más rápido?Algoritmo eficiente de clasificación de cadenas
Respuesta
Si sabe que la cadena consta solo de ciertos caracteres (que casi siempre es el caso), puede usar una variante de BucketSort o RadixSort.
Hice una solución híbrida para primero ordenar los sufijos de cadenas usando quicksort y luego el resto usando radixsort. Funciona bastante rápido. No quería ir con la clasificación de radix puro, ya que algunas cadenas son largas, pero los sufijos son bastante diferentes, por lo que no me costó clasificarlos usando la orden rápida. Creo que todavía hay margen de mejora, pero por ahora esta solución es suficiente. Gracias –
Puede construir un trie, que debería ser O(s*n)
, creo.
+1, perdí demasiado tiempo para calcular la complejidad :-) –
@tyz: La inserción en un trie debe ser 'O (s)', y debe hacerlo 'n' veces. –
Tengo que pensarlo, en la implementación directa parece estar un poco hambriento de memoria. –
Busque "Sedgewick Multikey quick sort" (Sedgewick escribió famosos libros de texto de algoritmos en C y Java). Su algoritmo es relativamente fácil de implementar y bastante rápido. Evita el problema al que te refieres arriba. Existe el algoritmo de clasificación de ráfaga que dice ser más rápido, pero no conozco ninguna implementación.
Hay un artículo Fast String Sort in C# and F# que describe el algoritmo y tiene una referencia al código de Sedgewick así como al código C#. (divulgación: es un artículo y código que escribí basado en el artículo de Sedgewick).
- 1. Un algoritmo de clasificación
- 2. Algoritmo Problema Clasificación
- 3. Análisis de cadenas y clasificación
- 4. eficiente algoritmo de producto cartesiano
- 5. Algoritmo de clasificación más eficiente para un gran conjunto de números
- 6. ¿Qué es una implementación de algoritmo de clasificación externa eficiente y estable (escrita en c)?
- 7. ¿Algún algoritmo de clasificación eficiente para una lista casi ordenada que contiene datos de tiempo?
- 8. Java: clasificación complicada de cadenas prefijadas (ArrayLists)
- 9. ¿Qué algoritmo de clasificación de múltiples criterios usar?
- 10. ¿Qué algoritmo (s) de clasificación utiliza MySQL?
- 11. Algoritmo de clasificación basado en comparación
- 12. ¿Qué algoritmo de clasificación usa PHP?
- 13. ¿Cuándo se usa cada algoritmo de clasificación?
- 14. Medición del rendimiento del algoritmo de clasificación
- 15. ¿Qué algoritmo de clasificación utiliza LINQ "OrderBy"?
- 16. ¿Existe un algoritmo de "clasificación binaria"?
- 17. ¿Qué algoritmo de clasificación implementa .NET Framework?
- 18. ¿Algoritmo más eficiente para encontrar la primera concordancia de prefijo de una matriz de cadenas ordenadas?
- 19. Algoritmo de potencia de memoria eficiente
- 20. Algoritmo eficiente de codificación de palabras
- 21. Clasificación de cadenas usando Combinar Ordenar
- 22. Clasificación de cadenas basada en Ontology
- 23. manera eficiente de buscar cadenas en la lista de cadenas?
- 24. Algoritmo para dibujar árboles de manera eficiente
- 25. algoritmo de disposición eficiente en java
- 26. Algoritmo de empaque eficiente para polígonos irregulares
- 27. Algoritmo de embalaje eficiente para polígonos regulares
- 28. Eficiente problema de búsqueda de cadenas masivas
- 29. Reemplazo eficiente de cadenas de Javascript
- 30. ¿Cuáles son los criterios para elegir un algoritmo de clasificación?
¿Está causando que su código sea lento? Si no, no te preocupes por eso. – tjameson
No es la primera vez que encuentro este problema, pero sí, en el momento en que esta clasificación es una parte, donde mi programa pasa mucho tiempo. –