Introduzca cómo procesar datos masivos
Presentar el método de procesamiento de datos masivos
Ámbito de aplicación: se puede utilizar para implementar un diccionario de datos, juzgar el peso de los datos o encontrar la intersección de conjuntos
Principios básicos y puntos clave:
El principio es muy simple: hay k funciones hash independientes en la matriz de bits. Establezca la matriz de bits del valor correspondiente a la función hash en 1. Si se encuentra que todos los bits correspondientes de la función hash son 1 durante la búsqueda, significa que existe. Obviamente, este proceso no garantiza que la búsqueda. El resultado es 100 correcto. Al mismo tiempo, no se admite eliminar una palabra clave insertada, porque el bit correspondiente a la palabra clave afectará a otras palabras clave. Entonces, una mejora simple es el filtro Bloom de conteo, que utiliza una matriz de contadores en lugar de una matriz de bits para admitir la eliminación.
También hay una cuestión más importante: cómo determinar el tamaño de la matriz de bits m y el número de funciones hash en función del número de elementos de entrada n. La tasa de error es menor cuando el número de funciones hash k=(ln2)*(m/n). Cuando la tasa de error no es mayor que E, m debe ser al menos igual a n*lg(1/E) para representar cualquier conjunto de n elementos. Pero m debería ser mayor, porque al menos la mitad de la matriz de bits debe ser 0, entonces m debería ser gt =nlg(1/E)*lge, que es aproximadamente 1,44 veces nlg(1/E) (lg significa 2 es logaritmo de base).
Por ejemplo, supongamos que la tasa de error es 0,01, entonces m debería ser aproximadamente 13 veces n. Entonces k es aproximadamente 8.
Tenga en cuenta que las unidades de myn son diferentes aquí, m es la unidad de bit y n es la unidad del número de elementos (para ser precisos, el número de elementos diferentes). Por lo general, la longitud de un solo elemento es de muchos bits. Por lo tanto, el uso del filtro Bloom suele ahorrar memoria.
Extensión:
El filtro Bloom asigna los elementos del conjunto a la matriz de bits, usando k (k es el número de funciones hash) asignando bits para indicar si los elementos son todos 1. o no en colección. El filtro de conteo de floración (CBF) expande cada bit de la matriz de bits en un contador, lo que admite la operación de eliminación de elementos. Spectral Bloom Filter (SBF) lo asocia con el número de apariciones de un elemento de colección. SBF utiliza el valor mínimo en contador para representar aproximadamente la frecuencia de aparición de elementos.
Ejemplo de problema: le proporcionamos dos archivos A y B, cada uno de los cuales almacena 5 mil millones de URL. Cada URL ocupa 64 bytes y el límite de memoria es 4G. Le permite encontrar los archivos A y B*** La misma URL. . ¿Qué pasa si hay tres o incluso n archivos?
Basándonos en esta pregunta, calculemos que el uso de memoria 4G=2^32 es aproximadamente 4 mil millones*8, que es aproximadamente n=5 mil millones. Si se calcula con una tasa de error de 0,01, se necesitan aproximadamente 65 mil millones de bits. Lo que está disponible ahora es 34 mil millones, lo que no es muy diferente. Esto puede aumentar la tasa de error. Además, si estas URL se corresponden una a una, se pueden convertir en IP, lo cual es mucho más sencillo.
2.Hashing
Ámbito de aplicación: estructura de datos básica para búsqueda y eliminación rápidas, generalmente la cantidad total de datos se puede guardar en la memoria
Principios básicos y puntos clave:
Selección de función hash, para cadenas, enteros, permutaciones y métodos hash correspondientes específicos.
Para el procesamiento de colisiones, uno es el hash abierto, también conocido como método de cremallera; el otro es el hash cerrado, también conocido como método de direccionamiento abierto.
Extensión:
La d en el hash d-izquierda significa múltiple. Primero simplifiquemos este problema y echemos un vistazo al hash 2-izquierda.
El hash de 2 izquierdas se refiere a dividir una tabla hash en dos mitades de igual longitud, llamadas T1 y T2 respectivamente, y equipar a T1 y T2 con una función hash, h1 y h2 respectivamente. Al almacenar una nueva clave, se utilizan dos funciones hash para el cálculo al mismo tiempo y se obtienen dos direcciones h1 [clave] y h2 [clave]. En este momento, debe verificar la posición h1[clave] en T1 y la posición h2[clave] en T2, qué posición tiene más claves almacenadas (en colisión), y luego almacenar la nueva clave en la ubicación con menos carga. Si hay el mismo número en ambos lados, por ejemplo, ambas posiciones están vacías o hay una clave almacenada en ambas, la nueva clave se almacenará en la subtabla T1 de la izquierda, y 2-izquierda proviene de aquí. Al buscar una clave, debe aplicar hash dos veces y buscar dos ubicaciones al mismo tiempo.
Ejemplos de problemas: 1) A partir de datos de registro masivos, extraer la IP con más visitas a Baidu en un día determinado.
La cantidad de IP aún es limitada, hasta 2^32, por lo que puedes considerar usar hash para almacenar las IP directamente en la memoria y luego realizar estadísticas.
3.bit-map
Ámbito de aplicación: puede buscar, determinar y eliminar datos rápidamente. En términos generales, el rango de datos es inferior a 10 veces int
.Principios básicos y puntos clave: use matrices de bits para indicar si existen ciertos elementos, como números de teléfono de 8 dígitos
Extensiones: el filtro Bloom puede verse como una extensión del mapa de bits
Ejemplos de problemas:
1) Se sabe que un archivo contiene algunos números de teléfono, cada número tiene 8 dígitos y se cuenta el número de números diferentes.
El número máximo de 8 bits es 99 999 999, lo que requiere unos 99 m de bits y unos 10 m bytes de memoria.
2) Encuentre el número de enteros no repetidos entre 250 millones de enteros. El espacio de memoria no es suficiente para acomodar estos 250 millones de enteros.
Amplíe el mapa de bits y use 2 bits para representar un número. 0 significa que no aparece, 1 significa que aparece una vez y 2 significa que aparece 2 veces o más. O no usamos 2 bits para representarlo, podemos usar dos mapas de bits para simular este mapa de 2 bits.
4. Montón
Ámbito de aplicación: n es grande antes de datos masivos y n es relativamente pequeño, el montón se puede guardar en la memoria
Principios básicos y puntos clave: montón máximo Encuentre los primeros n montones más pequeños y encuentre los primeros n montones más grandes. Métodos, como encontrar los primeros n más pequeños, comparamos el elemento actual con el elemento más grande en el montón máximo. Si es más pequeño que el elemento más grande, se debe reemplazar el elemento más grande. De esta forma, los n elementos finales obtenidos son los n más pequeños. Es adecuado para grandes cantidades de datos. Si el primer n es pequeño y el tamaño de n es relativamente pequeño, todos los primeros n elementos se pueden obtener escaneando una vez, lo cual es muy eficiente.
Extensión: se puede utilizar un montón dual, un montón máximo combinado con un montón mínimo, para mantener la mediana.
Ejemplos de problemas:
1) Encuentra los 100 números más grandes entre 1 millón de números.
Solo usa un montón mínimo de 100 elementos.
5. División de cubos de doble capa
Ámbito de aplicación: késimo número más grande, mediano, no repetitivo o repetido
Principios básicos y puntos clave: porque El El rango de elementos es muy grande y no se puede usar la tabla de direccionamiento directo, por lo que el rango se determina gradualmente a través de múltiples divisiones y luego, finalmente, dentro de un rango aceptable. Se puede alejar varias veces; la doble capa es solo un ejemplo.
Extensión:
Ejemplo de problema:
1). Encuentre el número de enteros no repetidos entre 250 millones de enteros. El espacio de memoria no es suficiente para acomodar. estos 250 millones de números enteros.
Un poco como el principio del casillero, el número de números enteros es 2^32, es decir, podemos dividir estos 2^32 números en 2^8 áreas (como usar un solo archivo para representar un área ), y luego separe los datos en diferentes áreas, y luego las diferentes áreas se pueden resolver directamente usando un mapa de bits.
En otras palabras, siempre que haya suficiente espacio en disco, se puede solucionar fácilmente.
2) 50 millones de ints para encontrar su mediana.
Este ejemplo es más obvio que el anterior. Primero, dividimos el int en 2 ^ 16 áreas y luego leemos los datos para contar la cantidad de números que caen en cada área. Luego podemos juzgar en qué área cae la mediana en función de los resultados estadísticos y al mismo tiempo saber. El número en esta área. Varios números grandes resultan ser la mediana. Luego, para el segundo escaneo, solo contamos los números que caen en esta área.
De hecho, si no es int sino int64, podemos reducirlo a un nivel aceptable después de 3 de esas divisiones. Es decir, primero puede dividir int64 en 2 ^ 24 áreas y luego determinar el número más grande en el área, luego dividir el área en 2 ^ 20 subáreas y luego determinar el número más grande en la subárea y luego determine el número en la subárea. El número es solo 2 ^ 20, por lo que puede usar directamente la tabla de direcciones directas para estadísticas.
6. Índice de base de datos
Ámbito de aplicación: adición, eliminación, modificación y consulta de grandes cantidades de datos
Principios básicos y puntos clave: Utilice el diseño de datos y métodos de implementación para analizar datos masivos. Se procesan altas, eliminaciones, modificaciones y comprobaciones.
Extensión:
Ejemplo de problema:
7. Índice invertido (Índice invertido)
Ámbito de aplicación: motores de búsqueda, consulta de palabras clave
Principios básicos y puntos clave: ¿Por qué se llama índice invertido? Un método de indexación que se utiliza para almacenar el mapeo de la ubicación de almacenamiento de una palabra en un documento o grupo de documentos bajo búsqueda de texto completo. .
Tomando como ejemplo el inglés, el siguiente es el texto a indexar:
T0 = “es lo que es”
T1 = “lo que es it”
T2 = “es un plátano”
Podemos obtener el siguiente índice de archivo inverso:
“a”: {2}
"plátano": {2}
"es": {0, 1, 2}
"es": {0, 1, 2}
"what": {0, 1}
Las condiciones recuperadas "what", "is" y "it" corresponderán a la intersección de los conjuntos.
Los índices directos se desarrollaron para almacenar una lista de palabras para cada documento. La consulta de índice directo a menudo satisface la consulta ordenada y frecuente de texto completo de cada documento y la verificación de cada palabra en el documento de verificación. En un índice directo, los documentos ocupan una posición central y cada documento apunta a una secuencia de entradas de índice que contiene. Es decir, el documento apunta a las palabras que contiene y el índice inverso significa que la palabra apunta al documento que la contiene. Es fácil ver esta relación inversa.
Extensión:
Ejemplo de problema: sistema de recuperación de documentos, consulta qué documentos contienen una determinada palabra, como búsqueda de palabras clave para artículos académicos comunes.
8. Clasificación externa
Ámbito de aplicación: clasificación de big data, deduplicación
Principios básicos y puntos clave: método de fusión de clasificación, reemplazo y selección externos Principio del árbol de perdedores, árbol de fusión óptimo
Extensión:
Ejemplo de problema:
1). una palabra, el tamaño de la palabra no supera los 16 bytes y el límite de memoria es 1M. Devuelve las 100 palabras más frecuentes.
Estos datos tienen características obvias. El tamaño de la palabra es de 16 bytes, pero la memoria es de solo 1 m, lo que no es suficiente para el hash, por lo que se puede usar para ordenar. La memoria se puede utilizar como búfer de entrada.
9.árbol trie
Ámbito de aplicación: gran cantidad de datos, muchas repeticiones, pero se pueden guardar tipos de datos pequeños en la memoria
Principios básicos y claves puntos: método de implementación, representación de los hijos del nodo
Extensión: implementación de compresión.
Ejemplos de problemas:
1). Hay 10 archivos, cada archivo es 1G. Cada línea de cada archivo almacena la consulta del usuario y la consulta de cada archivo es posible duplicada. Se le pedirá que ordene por frecuencia de consulta.
2) 10 millones de cadenas, algunas de las cuales son iguales (duplicadas), es necesario eliminar todos los duplicados y conservar las cadenas sin duplicaciones. ¿Cómo diseñarlo e implementarlo?
3) Buscar consultas populares: la repetición de cadenas de consulta es relativamente alta, aunque el número total es de 10 millones, si se eliminan las repeticiones, no habrá más. 3 millones, cada uno No más de 255 bytes.
10. Mapreduce de procesamiento distribuido
Ámbito de aplicación: gran cantidad de datos, pero se pueden guardar tipos de datos pequeños
Principios básicos y puntos clave: transferir datos Deje que diferentes máquinas procesen, divida los datos y reduzca los resultados.
Extensión:
Ejemplo de problema:
1). La aplicación de ejemplo canónica de MapReduce es un proceso para contar las apariciones de
cada palabra diferente en un conjunto de documentos:
void map(String name, String document):
// nombre: nombre del documento
// documento: contenido del documento
para cada palabra w en el documento:
EmitIntermediate(w, 1
void reduce(String word, Iterator parcialCounts):
// clave: una palabra
// valores: una lista de recuentos parciales agregados
int resultado = 0;
para cada v en parcialCounts:
resultado = ParseInt(v);
Emit(resultado);
Aquí, cada documento se divide en palabras y cada palabra se cuenta inicialmente. con un valor "1" mediante
la función Mapa, usando la palabra como clave de resultado. El marco reúne todos los pares
con la misma clave y los envía a la misma. llame a Reducir, por lo tanto esta función solo necesita
suma todos sus valores de entrada para encontrar las apariciones totales de esa palabra
2). computadoras, piense en una manera de contar eficientemente el TOP10 de este lote de datos.
3). Hay N máquinas en un *** y hay N números en cada máquina. Cada máquina puede almacenar hasta números O(N) y operar con ellos. ¿Cómo encontrar la mediana (mediana) de N^2 números?
Análisis de problemas clásico
Decenas de decenas de millones o miles de millones de datos (con duplicación), cuente los N superiores que aparecen con mayor frecuencia Los datos se pueden dividir en dos situaciones: se pueden leer en la memoria a la vez y no se pueden leer en la memoria a la vez.
Ideas disponibles: montón de árbol de prueba, índice de base de datos, estadísticas de subconjuntos, hash, computación distribuida, estadísticas aproximadas, clasificación externa
El llamado si se puede leer en la memoria en Una vez, de hecho, debería hacer referencia a la cantidad de datos después de eliminar duplicados. Si los datos se pueden guardar en la memoria después de la deduplicación, podemos crear un diccionario para los datos, como mediante map, hashmap, trie, y luego realizar estadísticas directamente. Por supuesto, al actualizar la cantidad de apariciones de cada dato, podemos usar un montón para mantener los N datos principales con la mayor cantidad de ocurrencias. Por supuesto, esto aumentará la cantidad de tiempos de mantenimiento, lo que no es tan eficiente como encontrar. los N datos principales después de las estadísticas completas.
Si los datos no caben en la memoria. Por un lado, podemos considerar si el método de diccionario anterior se puede mejorar para adaptarse a esta situación. El cambio que se puede hacer es almacenar el diccionario en el disco duro en lugar de en la memoria. la base de datos.
Por supuesto que hay una mejor manera, que es utilizar computación distribuida, que es básicamente el proceso de reducción de mapas. Primero, puede dividir los datos en rangos según el valor de los datos o el valor después del hash. los datos (md5) Para dividirlos en diferentes máquinas, es mejor permitir que los datos se lean en la memoria a la vez después de la división, de modo que diferentes máquinas sean responsables de procesar varios rangos numéricos, que en realidad es un mapa. Después de obtener los resultados, cada máquina solo necesita sacar los N datos principales con más ocurrencias y luego resumirlos para seleccionar los N datos principales con más ocurrencias entre todos los datos. Este es en realidad el proceso de reducción.
De hecho, es posible que desee distribuir directamente los datos a diferentes máquinas para su procesamiento, pero no podrá obtener la solución correcta. Porque un dato puede estar distribuido uniformemente en diferentes máquinas, mientras que otro puede estar completamente agregado en una máquina y puede haber la misma cantidad de datos al mismo tiempo. Por ejemplo, si queremos encontrar los 100 elementos principales con más apariciones, distribuimos 10 millones de datos a 10 máquinas y buscamos los 100 elementos principales con más apariciones en cada máquina. Después de fusionarlos, no podemos garantizar encontrar el número 100 real. uno, porque por ejemplo, el número 100 con más apariciones puede tener 10,000, pero está dividido en 10 máquinas, por lo que solo hay 1,000 en cada máquina. Supongamos que las máquinas clasificadas antes de 1,000 están todas distribuidas en una sola máquina. , hay 1001, por lo que el que tiene 10,000 será eliminado. Incluso si dejamos que cada máquina seleccione los 1000 con más ocurrencias y luego los combine, aún habrá un error, porque puede haber una gran cantidad de 1001 A reunidos. de los individuos se produce. Por lo tanto, los datos no se pueden distribuir aleatoriamente a diferentes máquinas, sino que se deben asignar a diferentes máquinas para su procesamiento de acuerdo con el valor hash, de modo que diferentes máquinas puedan procesar un rango de valores.
El método de clasificación externo consumirá mucha IO y no será muy eficiente. El método distribuido anterior también se puede utilizar en la versión independiente, es decir, los datos totales se dividen en varios subarchivos diferentes según el rango de valores y luego se procesan uno por uno. Una vez completado el procesamiento, se fusionan las palabras y su frecuencia de aparición. De hecho, se puede utilizar un proceso de combinación de clasificación externo.
También podemos considerar la computación aproximada, es decir, podemos combinar atributos del lenguaje natural y utilizar solo aquellas palabras que aparecen más en la práctica como diccionario, de modo que esta escala se pueda guardar en la memoria.