c# - memoria - terabyte equivalencia
Analizando un terabyte de texto y contando eficientemente el número de ocurrencias de cada palabra (16)
Recientemente me encontré con una pregunta de entrevista para crear un algoritmo en cualquier idioma que debería hacer lo siguiente
- Lee 1 terabyte de contenido
- Haz un recuento por cada palabra recurrente en ese contenido
- Enumere las 10 mejores palabras que ocurren con mayor frecuencia
¿Podría hacerme saber la mejor manera posible de crear un algoritmo para esto?
Editar:
OK, digamos que el contenido está en inglés. ¿Cómo podemos encontrar las 10 palabras principales que aparecen con mayor frecuencia en ese contenido? Mi otra duda es que, si a propósito están dando datos únicos, nuestro búfer caducará con el desbordamiento del tamaño del montón. Necesitamos manejar eso también.
Respuesta a la entrevista
Esta tarea es interesante sin ser demasiado compleja, por lo que es una excelente manera de iniciar una buena discusión técnica. Mi plan para abordar esta tarea sería:
- Dividir datos de entrada en palabras, usando espacios en blanco y puntuación como delimitadores
- Alimente cada palabra encontrada en una estructura Trie , con un contador actualizado en nodos que representan la última letra de una palabra
- Recorra el árbol completamente poblado para encontrar nodos con conteos más altos
En el contexto de una entrevista ... demostraría la idea de Trie dibujando el árbol en una pizarra o papel. Comience desde el vacío, luego genere el árbol basándose en una sola oración que contenga al menos una palabra recurrente. Di "el gato puede atrapar el ratón" . Finalmente, muestre cómo se puede atravesar el árbol para encontrar los conteos más altos. Luego justificaría cómo este árbol proporciona un buen uso de la memoria, una buena velocidad de búsqueda de palabras (especialmente en el caso del lenguaje natural para el que se derivan muchas palabras) y es adecuado para el procesamiento en paralelo.
Dibujar en el tablero
Manifestación
El programa C # a continuación pasa por 2 GB de texto en 75 segundos en un xeon W3520 de 4 núcleos, maximizando 8 hilos. El rendimiento es de alrededor de 4.3 millones de palabras por segundo con un código de análisis de entrada inferior al óptimo. Con la Trie para almacenar palabras, la memoria no es un problema cuando se procesa la entrada de lenguaje natural.
Notas:
- Texto de prueba obtenido del proyecto Gutenberg.
- el código de análisis de entrada asume saltos de línea y es bastante subóptimo
- la eliminación de la puntuación y otras palabras que no sean palabras no se realiza muy bien
- el manejo de un archivo grande en lugar de uno más pequeño requeriría una pequeña cantidad de código para comenzar a leer los hilos entre el desplazamiento especificado dentro del archivo.
using System;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.IO;
using System.Threading;
namespace WordCount
{
class MainClass
{
public static void Main(string[] args)
{
Console.WriteLine("Counting words...");
DateTime start_at = DateTime.Now;
TrieNode root = new TrieNode(null, ''?'');
Dictionary<DataReader, Thread> readers = new Dictionary<DataReader, Thread>();
if (args.Length == 0)
{
args = new string[] { "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt",
"war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt" };
}
if (args.Length > 0)
{
foreach (string path in args)
{
DataReader new_reader = new DataReader(path, ref root);
Thread new_thread = new Thread(new_reader.ThreadRun);
readers.Add(new_reader, new_thread);
new_thread.Start();
}
}
foreach (Thread t in readers.Values) t.Join();
DateTime stop_at = DateTime.Now;
Console.WriteLine("Input data processed in {0} secs", new TimeSpan(stop_at.Ticks - start_at.Ticks).TotalSeconds);
Console.WriteLine();
Console.WriteLine("Most commonly found words:");
List<TrieNode> top10_nodes = new List<TrieNode> { root, root, root, root, root, root, root, root, root, root };
int distinct_word_count = 0;
int total_word_count = 0;
root.GetTopCounts(ref top10_nodes, ref distinct_word_count, ref total_word_count);
top10_nodes.Reverse();
foreach (TrieNode node in top10_nodes)
{
Console.WriteLine("{0} - {1} times", node.ToString(), node.m_word_count);
}
Console.WriteLine();
Console.WriteLine("{0} words counted", total_word_count);
Console.WriteLine("{0} distinct words found", distinct_word_count);
Console.WriteLine();
Console.WriteLine("done.");
}
}
#region Input data reader
public class DataReader
{
static int LOOP_COUNT = 1;
private TrieNode m_root;
private string m_path;
public DataReader(string path, ref TrieNode root)
{
m_root = root;
m_path = path;
}
public void ThreadRun()
{
for (int i = 0; i < LOOP_COUNT; i++) // fake large data set buy parsing smaller file multiple times
{
using (FileStream fstream = new FileStream(m_path, FileMode.Open, FileAccess.Read))
{
using (StreamReader sreader = new StreamReader(fstream))
{
string line;
while ((line = sreader.ReadLine()) != null)
{
string[] chunks = line.Split(null);
foreach (string chunk in chunks)
{
m_root.AddWord(chunk.Trim());
}
}
}
}
}
}
}
#endregion
#region TRIE implementation
public class TrieNode : IComparable<TrieNode>
{
private char m_char;
public int m_word_count;
private TrieNode m_parent = null;
private ConcurrentDictionary<char, TrieNode> m_children = null;
public TrieNode(TrieNode parent, char c)
{
m_char = c;
m_word_count = 0;
m_parent = parent;
m_children = new ConcurrentDictionary<char, TrieNode>();
}
public void AddWord(string word, int index = 0)
{
if (index < word.Length)
{
char key = word[index];
if (char.IsLetter(key)) // should do that during parsing but we''re just playing here! right?
{
if (!m_children.ContainsKey(key))
{
m_children.TryAdd(key, new TrieNode(this, key));
}
m_children[key].AddWord(word, index + 1);
}
else
{
// not a letter! retry with next char
AddWord(word, index + 1);
}
}
else
{
if (m_parent != null) // empty words should never be counted
{
lock (this)
{
m_word_count++;
}
}
}
}
public int GetCount(string word, int index = 0)
{
if (index < word.Length)
{
char key = word[index];
if (!m_children.ContainsKey(key))
{
return -1;
}
return m_children[key].GetCount(word, index + 1);
}
else
{
return m_word_count;
}
}
public void GetTopCounts(ref List<TrieNode> most_counted, ref int distinct_word_count, ref int total_word_count)
{
if (m_word_count > 0)
{
distinct_word_count++;
total_word_count += m_word_count;
}
if (m_word_count > most_counted[0].m_word_count)
{
most_counted[0] = this;
most_counted.Sort();
}
foreach (char key in m_children.Keys)
{
m_children[key].GetTopCounts(ref most_counted, ref distinct_word_count, ref total_word_count);
}
}
public override string ToString()
{
if (m_parent == null) return "";
else return m_parent.ToString() + m_char;
}
public int CompareTo(TrieNode other)
{
return this.m_word_count.CompareTo(other.m_word_count);
}
}
#endregion
}
Aquí el resultado de procesar el mismo 20 MB de texto 100 veces en 8 subprocesos.
Counting words...
Input data processed in 75.2879952 secs
Most commonly found words:
the - 19364400 times
of - 10629600 times
and - 10057400 times
to - 8121200 times
a - 6673600 times
in - 5539000 times
he - 4113600 times
that - 3998000 times
was - 3715400 times
his - 3623200 times
323618000 words counted
60896 distinct words found
Bueno, el primer pensamiento es administrar una base de datos en forma de tabla hash / Array o lo que sea para guardar cada aparición de palabras, pero de acuerdo con el tamaño de los datos, preferiría:
- Obtenga las primeras 10 palabras encontradas donde aparece> = 2
- Obtenga la cantidad de veces que aparecen estas palabras en toda la cadena y elimínelas mientras cuenta
- Comience de nuevo, una vez que tenga dos conjuntos de 10 palabras cada uno, obtendrá las 10 palabras más frecuentes de ambos conjuntos.
- Haga lo mismo para el resto de la cadena (que dosnt ya contiene estas palabras).
Incluso puede intentar ser más eficiente y comenzar con la primera vez que encuentre 10 palabras donde aparece> = 5 por ejemplo o más, si no lo encuentra, reduzca este valor hasta que se encuentren 10 palabras. A través de esto, tiene una buena oportunidad de evitar el uso intensivo de la memoria al guardar todas las palabras, lo que es una gran cantidad de datos, y puede guardar rondas de escaneo (en un buen caso)
Pero en el peor de los casos es posible que tenga más rondas que en un algoritmo convencional.
Por cierto, es un problema que intentaría resolver con un lenguaje de programación funcional en lugar de OOP.
Bueno, personalmente, dividí el archivo en diferentes tamaños de, por ejemplo, 128 mb, manteniendo dos en la memoria todo el tiempo mientras exploraba, cualquier palabra descubierta se agrega a una lista de hash, y el recuento de la Lista de listas, luego itero la lista De lista al final para encontrar los 10 mejores ...
Como un algoritmo general rápido haría esto.
Create a map with entries being the count for a specific word and the key being the actual string.
for each string in content:
if string is a valid key for the map:
increment the value associated with that key
else
add a new key/value pair to the map with the key being the word and the count being one
done
Entonces puedes encontrar el valor más grande en el mapa.
create an array size 10 with data pairs of (word, count)
for each value in the map
if current pair has a count larger than the smallest count in the array
replace that pair with the current one
print all pairs in array
Depende de los requisitos, pero si puede permitirse algún error, los algoritmos de transmisión y las estructuras de datos probabilísticas pueden ser interesantes porque son muy eficientes en tiempo y espacio y son muy fáciles de implementar, por ejemplo:
- Golpes pesados (por ejemplo, Ahorro de espacio), si está interesado solo en las primeras n palabras más frecuentes
- Boceto Count-Min, para obtener un conteo estimado de cualquier palabra
Esas estructuras de datos requieren muy poco espacio constante (la cantidad exacta depende del error que pueda tolerar).
Consulte http://alex.smola.org/teaching/berkeley2012/streams.html para obtener una excelente descripción de estos algoritmos.
El método a continuación solo leerá sus datos una vez y puede ajustarse para los tamaños de memoria.
- Lea el archivo en trozos de 1GB
- Por cada fragmento, haga una lista de, digamos, las 5000 palabras más frecuentes con su frecuencia.
- Combinar las listas según la frecuencia (1000 listas con 5000 palabras cada una)
- Devuelve los 10 primeros de la lista fusionada
Teóricamente, puedes perder las palabras, aunque creo que la posibilidad es muy pequeña.
En primer lugar, solo recientemente "descubrí" la estructura de datos de Trie y la respuesta de zeFrenchy fue excelente para ponerme al día.
Vi en los comentarios a varias personas que hacían sugerencias sobre cómo mejorar su rendimiento, pero eran solo algunos ajustes menores, así que pensé en compartir con ustedes lo que encontré para ser el verdadero cuello de botella ... el ConcurrentDictionary.
Quería jugar con el almacenamiento local de subprocesos y su muestra me dio una gran oportunidad para hacer eso y, después de algunos cambios menores, usar un Diccionario por subproceso y luego combinar los diccionarios después de que Join () viera una mejora en el rendimiento ~ 30% (el procesamiento de 20 MB 100 veces en 8 subprocesos pasó de ~ 48 segundos a ~ 33 segundos en mi caja).
El código se pega a continuación y notará que la respuesta aprobada no ha cambiado mucho.
PD: No tengo más de 50 puntos de reputación, por lo que no pude poner esto en un comentario.
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;
namespace WordCount
{
class MainClass
{
public static void Main(string[] args)
{
Console.WriteLine("Counting words...");
DateTime start_at = DateTime.Now;
Dictionary<DataReader, Thread> readers = new Dictionary<DataReader, Thread>();
if (args.Length == 0)
{
args = new string[] { "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt",
"war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt" };
}
List<ThreadLocal<TrieNode>> roots;
if (args.Length == 0)
{
roots = new List<ThreadLocal<TrieNode>>(1);
}
else
{
roots = new List<ThreadLocal<TrieNode>>(args.Length);
foreach (string path in args)
{
ThreadLocal<TrieNode> root = new ThreadLocal<TrieNode>(() =>
{
return new TrieNode(null, ''?'');
});
roots.Add(root);
DataReader new_reader = new DataReader(path, root);
Thread new_thread = new Thread(new_reader.ThreadRun);
readers.Add(new_reader, new_thread);
new_thread.Start();
}
}
foreach (Thread t in readers.Values) t.Join();
foreach(ThreadLocal<TrieNode> root in roots.Skip(1))
{
roots[0].Value.CombineNode(root.Value);
root.Dispose();
}
DateTime stop_at = DateTime.Now;
Console.WriteLine("Input data processed in {0} secs", new TimeSpan(stop_at.Ticks - start_at.Ticks).TotalSeconds);
Console.WriteLine();
Console.WriteLine("Most commonly found words:");
List<TrieNode> top10_nodes = new List<TrieNode> { roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value };
int distinct_word_count = 0;
int total_word_count = 0;
roots[0].Value.GetTopCounts(top10_nodes, ref distinct_word_count, ref total_word_count);
top10_nodes.Reverse();
foreach (TrieNode node in top10_nodes)
{
Console.WriteLine("{0} - {1} times", node.ToString(), node.m_word_count);
}
roots[0].Dispose();
Console.WriteLine();
Console.WriteLine("{0} words counted", total_word_count);
Console.WriteLine("{0} distinct words found", distinct_word_count);
Console.WriteLine();
Console.WriteLine("done.");
Console.ReadLine();
}
}
#region Input data reader
public class DataReader
{
static int LOOP_COUNT = 100;
private TrieNode m_root;
private string m_path;
public DataReader(string path, ThreadLocal<TrieNode> root)
{
m_root = root.Value;
m_path = path;
}
public void ThreadRun()
{
for (int i = 0; i < LOOP_COUNT; i++) // fake large data set buy parsing smaller file multiple times
{
using (FileStream fstream = new FileStream(m_path, FileMode.Open, FileAccess.Read))
using (StreamReader sreader = new StreamReader(fstream))
{
string line;
while ((line = sreader.ReadLine()) != null)
{
string[] chunks = line.Split(null);
foreach (string chunk in chunks)
{
m_root.AddWord(chunk.Trim());
}
}
}
}
}
}
#endregion
#region TRIE implementation
public class TrieNode : IComparable<TrieNode>
{
private char m_char;
public int m_word_count;
private TrieNode m_parent = null;
private Dictionary<char, TrieNode> m_children = null;
public TrieNode(TrieNode parent, char c)
{
m_char = c;
m_word_count = 0;
m_parent = parent;
m_children = new Dictionary<char, TrieNode>();
}
public void CombineNode(TrieNode from)
{
foreach(KeyValuePair<char, TrieNode> fromChild in from.m_children)
{
char keyChar = fromChild.Key;
if (!m_children.ContainsKey(keyChar))
{
m_children.Add(keyChar, new TrieNode(this, keyChar));
}
m_children[keyChar].m_word_count += fromChild.Value.m_word_count;
m_children[keyChar].CombineNode(fromChild.Value);
}
}
public void AddWord(string word, int index = 0)
{
if (index < word.Length)
{
char key = word[index];
if (char.IsLetter(key)) // should do that during parsing but we''re just playing here! right?
{
if (!m_children.ContainsKey(key))
{
m_children.Add(key, new TrieNode(this, key));
}
m_children[key].AddWord(word, index + 1);
}
else
{
// not a letter! retry with next char
AddWord(word, index + 1);
}
}
else
{
if (m_parent != null) // empty words should never be counted
{
m_word_count++;
}
}
}
public int GetCount(string word, int index = 0)
{
if (index < word.Length)
{
char key = word[index];
if (!m_children.ContainsKey(key))
{
return -1;
}
return m_children[key].GetCount(word, index + 1);
}
else
{
return m_word_count;
}
}
public void GetTopCounts(List<TrieNode> most_counted, ref int distinct_word_count, ref int total_word_count)
{
if (m_word_count > 0)
{
distinct_word_count++;
total_word_count += m_word_count;
}
if (m_word_count > most_counted[0].m_word_count)
{
most_counted[0] = this;
most_counted.Sort();
}
foreach (char key in m_children.Keys)
{
m_children[key].GetTopCounts(most_counted, ref distinct_word_count, ref total_word_count);
}
}
public override string ToString()
{
return BuildString(new StringBuilder()).ToString();
}
private StringBuilder BuildString(StringBuilder builder)
{
if (m_parent == null)
{
return builder;
}
else
{
return m_parent.BuildString(builder).Append(m_char);
}
}
public int CompareTo(TrieNode other)
{
return this.m_word_count.CompareTo(other.m_word_count);
}
}
#endregion
}
Estaría bastante tentada de usar un DAWG ( wikipedia , y una revisión de C # con más detalles ). Es lo suficientemente simple como para agregar un campo de conteo en los nodos de hoja, memoria eficiente y funciona muy bien para las búsquedas.
EDITAR: ¿Aunque ha intentado simplemente usar un Dictionary<string, int> ? Donde <string, int > representa word y count? ¿Quizás intentas optimizar demasiado pronto?
Nota del editor: esta publicación originalmente vinculada a este artículo de wikipedia , que parece tener otro significado del término DAWG: una forma de almacenar todas las subcadenas de una palabra, para una concordancia de cadenas aproximada eficiente.
Intente pensar en una estructura de datos especial para abordar este tipo de problemas. En este caso, un tipo especial de árbol como trie para almacenar cadenas de manera específica, muy eficiente. O la segunda forma de construir tu propia solución como contar palabras. Supongo que este TB de datos estaría en inglés, entonces tenemos alrededor de 600,000 palabras en general, por lo que será posible almacenar solo esas palabras y contando qué cadenas se repetirían + esta solución necesitará una expresión regular para eliminar algunos caracteres especiales. La primera solución será más rápida, estoy bastante seguro.
Aquí está la implementación de neumáticos en Java.
http://algs4.cs.princeton.edu/52trie/TrieST.java.html
La tormenta es la tecnología a considerar. Separa la función de la entrada de datos (salidas) de los procesadores (tornillos). El capítulo 2 de The Storm Book resuelve su problema exacto y describe muy bien la arquitectura del sistema: http://www.amazon.com/Getting-Started-Storm-Jonathan-Leibiusky/dp/1449324010
Storm es un procesamiento más en tiempo real en comparación con el procesamiento por lotes con Hadoop. Si sus datos son existentes, puede distribuir cargas a diferentes surtidores y distribuirlos para procesarlos a diferentes pernos.
Este algoritmo también permitirá el soporte para que los datos crezcan más allá de los terabytes, ya que la fecha se analizará a medida que llegue en tiempo real.
Mucho depende de algunas cosas que no han sido especificadas. Por ejemplo, ¿estamos tratando de hacer esto una vez , o estamos tratando de construir un sistema que lo haga de manera regular y continua? ¿Tenemos algún control sobre la entrada? ¿Estamos tratando con texto que está todo en un solo idioma (por ejemplo, inglés) o hay muchos idiomas representados (y si es así, cuántos)?
Estos importan porque
- Si los datos comienzan en un solo disco duro, el conteo paralelo (p. Ej., Reducción de mapa) no servirá de nada: el cuello de botella será la velocidad de transferencia desde el disco. Hacer copias a más discos para que podamos contar más rápido será más lento que solo contar directamente desde un disco.
- Si estamos diseñando un sistema para hacer esto de manera regular, la mayor parte de nuestro énfasis está en el hardware, específicamente, tenemos muchos discos en paralelo para aumentar nuestro ancho de banda y al menos estar un poco más cerca de mantenernos al día con el UPC.
- No importa la cantidad de texto que esté leyendo, hay un límite en el número de palabras discretas con las que debe tratar, ya sea que tenga un terabyte de incluso un petabyte de texto en inglés, no verá nada como miles de millones de diferentes palabras en ingles Haciendo una revisión rápida, el Oxford English Dictionary enumera aproximadamente 600,000 palabras en inglés.
- Aunque las palabras reales son obviamente diferentes entre los idiomas, el número de palabras por idioma es aproximadamente constante, por lo que el tamaño del mapa que construimos dependerá en gran medida de la cantidad de idiomas representados.
Eso deja en su mayor parte la cuestión de cuántos idiomas podrían representarse. Por el momento, asumamos el peor de los casos. ISO 639-2 tiene códigos para 485 idiomas humanos. Supongamos un promedio de 700,000 palabras por idioma y una longitud promedio de palabras de, por ejemplo, 10 bytes de UTF-8 por palabra.
Solo almacenado como una simple lista lineal, eso significa que podemos almacenar cada palabra en cada idioma en la tierra junto con un conteo de frecuencia de 8 bytes en un poco menos de 6 gigabytes. Si usamos algo como un trie de Patricia, es probable que podamos planear reducirlo al menos un poco, posiblemente a 3 gigabytes o menos, aunque no sé lo suficiente sobre todos esos idiomas para estar seguro.
Ahora, la realidad es que es casi seguro que hemos sobreestimado los números en varios lugares allí. Un buen número de idiomas comparten un buen número de palabras, muchos idiomas (especialmente los más antiguos) probablemente tienen menos palabras que el inglés y miran a través de En la lista, parece que se incluyen algunos que probablemente no tienen ningún formulario escrito.
Resumen: Casi cualquier escritorio / servidor razonablemente nuevo tiene suficiente memoria para mantener el mapa completamente en la RAM, y más datos no lo cambiarán. Para uno (o unos pocos) discos en paralelo, vamos a estar vinculados a la E / S de todos modos, por lo que el conteo paralelo (y tal) probablemente será una pérdida neta. Probablemente necesitemos decenas de discos en paralelo antes de que cualquier otra optimización signifique mucho.
Pregunta muy interesante. Se relaciona más con el análisis lógico que con la codificación. Con el supuesto de que el idioma inglés y las oraciones válidas es más fácil.
No tiene que contar todas las palabras, solo las que tienen una longitud menor o igual a la longitud de palabra promedio del idioma dado (para inglés es 5.1). Por lo tanto no tendrás problemas con la memoria.
En cuanto a la lectura del archivo, debe elegir un modo paralelo, leer fragmentos (tamaño de su elección) manipulando las posiciones de los archivos para los espacios en blanco. Si decides leer fragmentos de 1 MB, por ejemplo, todos los fragmentos, excepto el primero, deberían ser un poco más anchos (+22 bytes desde la izquierda y +22 bytes desde la derecha, donde 22 representa la palabra más larga en inglés, si tengo razón). Para el procesamiento paralelo, necesitará un diccionario concurrente o colecciones locales que fusionará.
Tenga en cuenta que normalmente terminará con un top ten como parte de una lista de palabras vacías válidas (este es probablemente otro enfoque inverso que también es válido siempre que el contenido del archivo sea normal).
Puede intentar un enfoque de reducción de mapa para esta tarea. La ventaja de map-reduce es la escalabilidad, por lo que incluso para 1TB, 10TB o 1PB, el mismo enfoque funcionará, y no tendrá que hacer mucho trabajo para modificar su algoritmo para la nueva escala. El marco también se encargará de distribuir el trabajo entre todas las máquinas (y núcleos) que tenga en su clúster.
Primero - Crea los pares (word,occurances) .
El pseudo código para esto será algo así:
map(document):
for each word w:
EmitIntermediate(w,"1")
reduce(word,list<val>):
Emit(word,size(list))
En segundo lugar, puede encontrar los que tienen las mejores k ocurrencias más altas fácilmente con una única iteración sobre los pares. Este hilo explica este concepto. La idea principal es mantener un montón mínimo de elementos K superiores, y mientras se realiza la iteración, asegúrese de que el montón siempre contenga los elementos K superiores vistos hasta ahora. Cuando haya terminado, el montón contiene los elementos K superiores.
Una alternativa más escalable (aunque más lenta si tiene pocas máquinas) es usar la funcionalidad de clasificación de reducción de mapas, ordenar los datos de acuerdo con las ocurrencias y solo obtener la K superior.
Tres cosas a tener en cuenta para esto.
Específicamente: archivo demasiado grande para guardar en la memoria, lista de palabras (potencialmente) demasiado grande para guardar en la memoria, cantidad de palabras puede ser demasiado grande para un int de 32 bits.
Una vez que haya superado esas advertencias, debería ser sencillo. El juego está administrando la lista de palabras potencialmente grande.
Si es más fácil (para evitar que la cabeza gire).
"Está ejecutando una máquina Z-80 de 8 bits, con 65K de RAM y tiene un archivo de 1MB ..."
El mismo problema exacto.
Una solución diferente podría ser usar una tabla SQL y permitir que el sistema maneje los datos tan bien como sea posible. Primero cree la tabla con la word campo único, para cada palabra en la colección.
Luego use la consulta (perdón por el problema de la sintaxis, mi SQL está oxidado, en realidad es un pseudocódigo):
SELECT DISTINCT word, COUNT(*) AS c FROM myTable GROUP BY word ORDER BY c DESC
La idea general es generar primero una tabla (que se almacena en el disco) con todas las palabras y luego usar una consulta para contar y ordenar (word,occurances) por usted. A continuación, puede tomar la K superior de la lista recuperada.
A todos: si tengo alguna sintaxis u otros problemas en la declaración de SQL: no dude en editar
Mapa reducido
WordCount se puede lograr de manera eficiente a través de mapreduce usando hadoop. https://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html#Example%3A+WordCount+v1.0 Los archivos grandes se pueden analizar a través de él. Utiliza múltiples nodos en el clúster para realizar esta operación.
public void map(LongWritable key, Text value, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
String line = value.toString();
StringTokenizer tokenizer = new StringTokenizer(line);
while (tokenizer.hasMoreTokens()) {
word.set(tokenizer.nextToken());
output.collect(word, one);
}
}
public static class Reduce extends MapReduceBase implements Reducer<Text, IntWritable, Text, IntWritable> {
public void reduce(Text key, Iterator<IntWritable> values, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {
int sum = 0;
while (values.hasNext()) {
sum += values.next().get();
}
output.collect(key, new IntWritable(sum));
}
}