Algoritmo de clasificación más eficiente para un gran conjunto de números

Question

Estoy trabajando en un proyecto grande, no me molestaré en resumirlo aquí, pero esta sección del proyecto es tomar un documento de texto muy grande (mínimo de alrededor de 50,000 palabras (no únicas)), y da salida a cada palabra única en orden del más usado al menos utilizado (probablemente los tres primeros serán "a" "an" y "el").

Mi pregunta es, por supuesto, ¿cuál sería el mejor algoritmo de clasificación para usar? Estaba leyendo sobre el tipo de conteo, y me gusta, pero me preocupa que el rango de valores sea demasiado grande en comparación con el número de palabras únicas.

¿Alguna sugerencia?

Answer 1

En primer lugar, necesitará un mapa de la palabra -> recuento. 50,000 palabras no es mucho, se ajustará fácilmente en la memoria, por lo que no hay nada de qué preocuparse. En C++ puede usar el STD std :: map estándar.

Luego, una vez que tenga el mapa, puede copiar todas las claves del mapa en un vector.

Luego, ordene este vector usando un operador de comparación personalizado: en lugar de comparar las palabras, compare los recuentos del mapa. (No se preocupe por el algoritmo de clasificación específico: su matriz no es tan grande, por lo que cualquier clasificación de biblioteca estándar funcionará para usted)

Answer 2

Comenzaría con un quicksort e iré desde allí.

Consulte el wiki page on sorting algorithms, sin embargo, para conocer las diferencias.

Answer 3

Eche un vistazo al enlace. Una representación pictórica de cómo funciona el algoritmo diferente. ¡Esto te dará una pista!

Sorting Algorithms

Answer 4

Usted debe tratar de una especie MSD radix. Clasificará sus entradas en lexicographical order. Aquí hay un google code project que podría interesarle.

Answer 5

Esto es un poco complicado porque quiere un mapa de palabras -> frecuencia, y desea ordenar por el valor en lugar de la clave (que es común). Hay un ejemplo de Java here que muestra cómo hacerlo usando un comparador personalizado.

El algoritmo particular que utiliza no va a tener mucho efecto, por lo que me limitaría a la implementación de su biblioteca estándar.

Answer 6

Puede obtener un mejor rendimiento que el quicksort con este problema en particular suponiendo que si dos palabras ocurren el mismo número de veces, entonces no importa en qué orden las emite.

Primer paso: Cree un mapa hash con las palabras como valores clave y la frecuencia como los valores asociados. Llenaremos este mapa hash al analizar el archivo. Mientras haces esto, asegúrate de hacer un seguimiento de la frecuencia más alta encontrada. Este paso es O (n) complejidad.

Segundo paso: Cree una lista con el número de entradas igual a la frecuencia más alta desde el primer paso. El índice de cada ranura en esta lista contendrá una lista de las palabras con el recuento de frecuencias igual al índice. Por lo tanto, las palabras que aparecen 3 veces en el documento irán en la lista [3] por ejemplo. Itere a través del mapa hash e inserte las palabras en los lugares apropiados de la lista. Este paso es O (n) complejidad.

Tercer paso: Revise la lista en orden inverso y emita todas las palabras. Este paso es O (n) complejidad.

En general, este algoritmo cumplirá su tarea en O (n) tiempo en lugar de O (nlogn) requerido por quicksort.

Answer 7

creo que quiere hacer algo, como se explica en el post de abajo:

http://karephul.blogspot.com/2008/12/groovy-closures.html

Idiomas que apoyan el cierre hacen la solución más fácil, como LINQ como Eric mencionó.

Answer 8

En casi todos los casos que he probado, Quicksort funcionó lo mejor para mí. Sin embargo, tuve dos casos en que Combsort fue el mejor. Podría haber sido que combsort fue mejor en esos casos porque el código era muy pequeño, o debido a alguna peculiaridad en la forma en que se ordenaron los datos.

Cada vez que aparece la ordenación en mi perfil, pruebo los principales géneros. Nunca he tenido algo que haya superado tanto a Quicksort como a Combsort.

Answer 9

Para grandes conjuntos se pueden utilizar lo que se conoce como la "indexación basada tipo" en la recuperación de información, pero para 50.000 palabras se pueden utilizar los siguientes:

• leer todo el archivo en una memoria intermedia.
• analiza el búfer y crea un vector token con struct token {char * term, int termlen; } término es un puntero a la palabra en el búfer.
• ordena la tabla por términos (orden lexicográfico).
• establece entrynum = 0, itera a través del vector de término, cuando el término es nuevo, guárdalo en un vector: struct {char * term; int frecuencia; } en el índice entrynum, configure la frecuencia en 1 e incremente el número de entrada, de lo contrario, incremente la frecuencia.
• ordena el vector por frecuencia en orden descendente.

Answer 10

También puede intentar implementar árboles digitales también conocidos como Trie. Aquí está el link