Problema de big data, ¡ayuda urgente!

El problema de big data es, para ser precisos, el problema de la limitación de espacio bajo una gran cantidad de datos. Hay 7 soluciones (fuente de la imagen: Zuo Chengyun Basic Class):

Piense primero en el caso de utilizar un HashMap grande. La clave es un número entero y el valor es el número de veces que aparece el número entero. De esta manera, se puede contar la frecuencia de las palabras y luego se puede obtener la frecuencia de las 10 palabras TOP. Al calcular la memoria utilizada en este momento, el rango de enteros sin signo de 4 bytes es de 0 a más de 4,2 mil millones (si es un entero con signo, el rango es de -2,1 mil millones a más de 2,1 mil millones), y el rango es más de 4 mil millones. En el peor de los casos, si 4 mil millones de números son todos diferentes, el espacio utilizado por HashMap es 4 mil millones de registros. La clave (entero sin signo) en cada registro es de 4 bytes y el valor (frecuencia de palabras) también es de 4 bytes (tipo int). ), un total de ***8 bytes, un total de 32 mil millones de bytes, o 32G (1 mil millones de bytes se pueden estimar como 1G), la tabla hash explotó.

Aquí primero agregamos las características de la función hash:

Característica 1. El dominio de entrada es infinito y el dominio de salida es relativamente limitado.

Característica 2. No hay ningún componente aleatorio y es función de reglas determinadas. Si la entrada es la misma, la salida debe ser la misma; diferentes entradas pueden tener la misma salida (colisión hash).

Característica 3. Incluso si la entrada es muy cercana, el resultado final del cálculo es muy discreto y no tiene nada que ver con el patrón de entrada. Esta es también la característica más crítica.

Característica 4. La salida es módulo del número anterior, y el resultado del módulo también es discreto.

Deduciendo inversamente cuántos registros puede tener un HashMap con 1G de memoria, un conservador 100 millones de registros significa Los tipos de números (no el número) procesados ​​por HashMap no deben exceder los 100 millones. ¿Cómo lidiar con eso? Un archivo grande con 4 mil millones de números enteros. Después de que cada número sea procesado mediante una función hash y luego el módulo 100, solo será de 0 a 99. Según la característica 3 de la función hash, las diferentes entradas se distribuirán uniformemente de 0 a 99. Si hay 4 mil millones de números, si hay K tipos de números diferentes, después del procesamiento, habrá casi 100/k en cada archivo pequeño. números, de modo que hay menos de 100 millones de tipos en cada archivo pequeño. Luego use HashMap para procesar las frecuencias de palabras una por una para obtener el TOP10 de cada uno de los 100 archivos. La función hash tiene la misma entrada y la misma salida, por lo que no habrá una situación en la que un número caiga en archivos diferentes. Fusione los archivos TOP10 para obtener el TOP10 global.

El módulo 40 anterior es en realidad suficiente. El número de 4 mil millones tipo K es menor o igual a 4 mil millones, por lo que K/40 es menor o igual a 100 millones, lo que cumple con los requisitos anteriores para 1G. memoria, pero el valor es 100 En lugar de 40, es más seguro.

Utiliza un mapa de bits para utilizar un determinado bit para indicar si un determinado número ha aparecido o no. Si es una tabla hash, se requiere un par clave-valor para indicar si aparece un número. Tanto la clave como el valor ocupan 4 bytes, por lo que el espacio que ocupa un registro es de 64 bits (8 bytes). En términos de mapas de bits, 1 bit representa un número y se utilizan tantos bits como rango de números; 4,2 mil millones de bits/8 = más de 500 millones de bytes = más de 500 M (1 mil millones de bytes = 1G capturados en 1G); espacio.

Utiliza dos bits para representar la frecuencia de un determinado número. 00 significa que aparece 0 veces; 01 significa que aparece una vez; 10 significa que aparece 2 veces; 11 significa que aparece 3 veces. Si aparece más de 3 veces, 11 permanece sin cambios. De esta forma, tras las estadísticas finales, podemos conocer todos los números que aparecen dos veces en comparación con el original, el espacio se duplica y se ocupa 1G.

No se puede utilizar el mapa de bits. El espacio de 3 KB es demasiado pequeño. Primero calcule cuánto tiempo se puede hacer una matriz sin signo con 3 KB. El tamaño de un número sin signo es 4B, 3 KB / 4B = 750, y luego cuál es el más cercano a una determinada potencia de 2 entre 750 y 2 es 512. Luego, solicite. un entero sin signo con una longitud de 512. Escriba array arr (el espacio ocupado por arr obviamente no supera los 3 KB).

El rango de números en la pregunta es de 0 a 2 elevado a la potencia de 32 menos uno (un *** tiene tantos números como 2 elevado a la potencia de 32 porque, al igual que 512, ambos están elevados a una determinada potencia). de 2, por lo que 2 elevado a la potencia de 32 debe ser Se puede dividir igualmente en 512 partes (el tamaño de cada parte es 8388608); arr[0] representa la parte 0 entre las 512 partes (rango 0~8388607); indicando las estadísticas de frecuencia de palabras en esta parte y debido a que un *** solo tiene 40 100 millones de números, entonces los números contados por arr[0] definitivamente no se desbordarán (4 mil millones 2 elevado a 32 menos uno = más de 4,2); mil millones, un número sin signo tiene 32 bits si la frecuencia de todos los números se cuenta en el rango correspondiente. Por el bien de Los números no aparecieron.

Complejidad temporal general: logaritmo de 2 elevado a 32 con base 512. Este es un número muy pequeño. Y leer archivos línea por línea ocupa muy poca memoria. Leer archivos no significa cargar todos los archivos en la memoria a la vez, sino que utiliza un desplazamiento para encontrar una determinada línea de datos en el archivo del disco duro. , la línea anterior El espacio se puede liberar, por lo que manteniendo un identificador y un desplazamiento se puede leer el archivo línea por línea.

Todo el rango es de 0 a 2 elevado a la potencia 32 menos uno. Calcule el punto medio Mid y cuente el número de ocurrencias en el rango de 0 a Mid y regístrelo como a, cuente el número de ocurrencias en el rango de Mid 1 hasta el final y regístrelo como b uno de a y b deben ser; insatisfecho, y el insatisfecho se divide en dos partes, y finalmente debe ser Para localizar un determinado número que no aparece, el número de recorridos es logarítmico a la 32ª potencia de 2 como base 2, es decir, 32 veces

Cuando se enfrente a preguntas con espacio limitado, comience con el estado de los datos del rango y realice reflexiones sobre estadísticas entre particiones.

Utilice una función hash para distribuir URL a muchas máquinas. Los archivos de cada máquina se dividen en archivos pequeños utilizando una función hash. Después de contar las particiones de cada archivo pequeño, se encuentran URL duplicadas.

Utilice clasificación externa y de montón para fusionar los resultados de múltiples unidades de procesamiento

Desvíe archivos a través de 1G de memoria, y este 1G se usa para almacenar tablas hash. La característica de la función hash es que se ingresará la misma URL en un archivo y el tamaño del archivo se dividirá hasta que se pueda contar 1G, dividiendo así un archivo grande de 10 mil millones de URL en archivos pequeños. La clave de la tabla hash es de 64 bytes (tamaño de URL) y el valor es de tipo largo (porque hay 10 mil millones, los enteros sin signo no son suficientes) 8 bytes. Luego, calcule la cantidad máxima de dichos registros que se pueden almacenar en 1G de memoria y podrá conocer la cantidad máxima de URL diferentes que puede tolerar un archivo pequeño. Por lo tanto, suponiendo que 10 mil millones de URL son todas diferentes, cuántos archivos pequeños hay; necesario para garantizar que 1G no supere.

Cálculo: 64 8 = 72 bytes. Puede haber espacio de índice ocupado en la tabla hash. Se puede calcular como un poco más rico. Cuenta como 100 bytes para un registro. entonces Se pueden colocar un máximo de 10 millones de registros en la tabla hash, es decir, se registran 10 millones de URL diferentes, en el peor de los casos, 10 mil millones de URL son diferentes y 10 mil millones/10 millones requieren 1000 archivos pequeños, luego el original; URL El archivo grande se calcula utilizando una función hash y luego el módulo 1000, y se divide en los archivos pequeños correspondientes (según la naturaleza de la función hash, los tipos en cada archivo pequeño se dividen casi uniformemente y el número de registros en cada archivo es casi 1 Alrededor de 10 millones, no mucho más). Luego, cuente las frecuencias de palabras TOP100 en cada archivo pequeño en este espacio 1G. Hay 1000 palabras TOP100 para 1000 archivos y luego cree un montón raíz grande ordenado por frecuencia de palabras en cada archivo.

Forme la parte superior de cada montón en un montón raíz grande para formar un montón encima de un montón, un montón bidimensional (es decir, la estructura de árbol binario en la imagen de arriba, por ejemplo); la imagen de arriba contiene A, B y C; a, b, c; tres montones de α, β y θ. Ahora los elementos superiores A, a y α forman un montón de raíces grande.

En la figura anterior, si se encuentra que α es el más grande después del ajuste, entonces α y Cuando se intercambia a, la cadena α se intercambia con la cadena a, y α se genera como TOP1 en toda la frecuencia de palabras.

Como se muestra en la figura anterior, β aparece después de que se genera α, pero β no es necesariamente el máximo global, por lo que el montón raíz grande compuesto por los elementos superiores del montón comienza a acumularse si A; es el máximo global en este momento, entonces la cadena A se intercambia con la cadena de β... y así sucesivamente. Cada vez que el montón en el montón genera un valor máximo, los siguientes elementos se empujan hacia arriba y luego el montón. se ajusta nuevamente y la cadena completa se intercambia cada vez en el montón bidimensional. Salida uno, salida 100 veces, será TOP100.

Si es transversal, el costo de tiempo es O (100); el uso de una estructura de montón puede acelerar hasta O (log100). Se puede ver desde aquí que cada vez que la fila exterior determina algo, atraviesa la parte superior de cada montón y compara el tamaño.

Supongamos que el espacio dado está limitado a 3 KB, dividido en 512 partes como antes, y cada parte puede contar la frecuencia de las palabras. En la primera parte, se supone que estos números aparecen a, y en la. En la segunda parte, se supone que estos números aparecen b, la tercera parte supone que estos números aparecen c veces y que las frecuencias de palabras de todos los segmentos están presentes, y luego se suman a, b, c..., y se ve en. cuyo rango supera ligeramente los 2 mil millones o es exactamente 2 mil millones, y luego ubica el número 2 mil millones en este rango.

Por ejemplo, si la i-ésima parte es 1,9 mil millones y la i-1 es 2,1 mil millones, entonces 2 mil millones están en el i-1 y es la primera en el i-1 100 millones, y luego divídalo en 512 partes para las estadísticas de frecuencia de palabras en la parte i-1 y vea qué parte acaba de superar los 100 millones o acaba de alcanzar los 100 millones. Si esto continúa, siempre habrá un momento en que se publicarán las estadísticas.