algorithm - ver - Seguimiento en tiempo real de las 100 mejores palabras de twitter por minuto/hora/día

estadisticas twitter gratis

Question

Recientemente me encontré con esta pregunta de entrevista:

Given a continuous twitter feed, design an algorithm to return the 100 most
frequent words used at this minute, this hour and this day.

Estaba pensando en un sistema con un hash de mapa de word -> count vinculado a 3 min-montones para el minuto, la hora y el día actuales.

Todos los mensajes entrantes se tokenizan, desinfectan y los recuentos de palabras se actualizan en el mapa hash (y aumenta la clave en los montones si la palabra ya existe en él)

Si alguna de las palabras no existe en el montón (y el tamaño del montón == 100) comprueba si su frequency > min value en el montón y, si es así, extrae-mín e inserta en el montón.

¿Hay mejores formas de hacer esto?

Answer 1

Su algoritmo es un buen comienzo, pero no va a producir resultados correctos. El problema es que las tablas hash de la forma en que las describes son una calle de sentido único: una vez que se agrega una palabra, se cuenta para siempre.

Necesita una matriz de 1440 (24 * 60) word+count mapas hash organizados de la manera que usted describe; estos son tus conteos minuto a minuto. Necesita dos mapas hash adicionales para el total de la hora y el día.

Defina dos operaciones en mapas hash: add y subtract , con la semántica de la fusión de conteos de palabras idénticas, y elimine las palabras cuando su conteo se reduzca a cero.

Cada minuto, inicia un nuevo mapa hash y actualiza los recuentos del feed. Al final del minuto, coloque ese mapa hash en la matriz para el minuto actual, agréguelo al total acumulado de la hora y del día, y luego reste el mapa hash de hace una hora del total acumulado por hora, y reste el mapa hash de hace 24 horas del total acumulado diario.

Finalmente, necesita una forma de producir las 100 palabras principales con un mapa hash. Esta debería ser una tarea trivial: agregue elementos a una matriz de entradas de word+count , clasifique el recuento y mantenga los 100 principales.

Answer 2

dasblinkenlight hizo un buen punto por un error al no excluir elementos de tu mapa hash.

Sin embargo, hay una cosa más que añadir, para calcular realmente las palabras K principales dadas una min / hora / día, es más rápido usar partición (O (n)) en lugar de ordenar (O (nlgn)):

1. volcar un hashmap de recuentos de palabras min / hour / day en una matriz: O (n)
2. use la selección de la mediana de la mediana para obtener el elemento K-ésimo: O (n)
3. partición alrededor del elem K-ésimo: O (n)

HTH.