Introducción de métodos para procesar datos masivos.
Ámbito de aplicación: se puede utilizar para implementar un diccionario de datos, determinar la duplicación de datos o establecer intersecciones.
Principios básicos y puntos clave:
El principio es muy simple: matriz de bits + k funciones hash independientes. Si la matriz de bits del valor correspondiente a la función hash se establece en 1, y si se encuentra que todos los bits correspondientes a la función hash son 1, es obvio que este proceso no puede garantizar que el resultado de la búsqueda sea 100% correcto. Al mismo tiempo, no se admite la eliminación de palabras clave insertadas porque los bits correspondientes de esta palabra clave afectarán a otras palabras clave. Entonces, una mejora simple es un filtro de conteo de floración que admita la eliminación reemplazando la matriz de bits con una matriz de contadores.
También hay una cuestión importante, como 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 n de elementos de entrada. Cuando el número de funciones hash k = (LN2) * (m/n), la tasa de error es la más pequeña. Si la tasa de error no es mayor que E, entonces 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 es necesario garantizar que al menos la mitad de la matriz de bits sea 0, por lo que m debería > 0 = Nlg (1/E) * lge es aproximadamente 1,44 veces NLG (1/E) (LG; representa logaritmo en base 2).
Por ejemplo, si asumimos una tasa de error de 0,01, entonces m debería ser aproximadamente 13 veces n. Entonces k es aproximadamente 8.
Tenga en cuenta aquí que las unidades de myn son diferentes, m es la unidad de bits y n es la unidad de número de elementos (para ser precisos, el número de elementos diferentes). Normalmente, un solo elemento tiene muchos bits de longitud. Por lo tanto suele resultar económico utilizar filtros de floración en memoria.
Extensión:
El filtro Bloom asigna los elementos del conjunto a una matriz de bits. Si todos los bits de mapeo son 1 (k es el número de funciones hash) indica si el elemento en este. recopilación. Los filtros Bloom de conteo (CBF) admiten la eliminación de elementos extendiendo cada bit de la matriz de bits a un contador. El filtro de floración espectral (SBF) lo relaciona con el número de apariciones de los elementos recopilados. SBF utiliza el valor mínimo en el contador para estimar la frecuencia de aparición del elemento.
Problema de ejemplo: te doy dos archivos A y B, cada archivo tiene 5 mil millones de URL, cada URL ocupa 64 bytes y el límite de memoria es 4G, para que puedas encontrar la misma URL para Archivos A y B. ¿Qué pasa si es tercera marcha o incluso n marcha?
Con base en esta pregunta, calculemos el uso de memoria. 4g = 2 32 es aproximadamente 4 mil millones * 8 es aproximadamente 34 mil millones, n = 5 mil millones. Si la tasa de error es 0,01, se necesitan aproximadamente 65 mil millones de bits. Ahora hay 34 mil millones disponibles, que es aproximadamente lo mismo, lo que puede aumentar la tasa de error. Además, si estas URL e IP se corresponden uno a uno, se pueden convertir en IP, lo cual se simplifica enormemente.
2. Método de hash
Ámbito de aplicación: una estructura de datos básica que se puede buscar y eliminar rápidamente, y que generalmente requiere la cantidad total de datos que se pueden colocar en la memoria.
Principios básicos y puntos clave:
La selección de la función hash, para cadenas, enteros y permutaciones, corresponde específicamente al método hash.
Procesamiento de colisiones, uno es el método de hash abierto, también llamado método de cremallera; el otro es el método de hash cerrado, también llamado direccionamiento abierto.
Extensión:
d-La d en el hash izquierdo significa múltiple. Primero simplifiquemos el problema y observemos el hash de 2 izquierdas. 2 El hash izquierdo se refiere a dividir la tabla hash en dos mitades de igual longitud, llamadas T1 y T2 respectivamente, y proporcionar funciones hash h1 y h2 para T1 y T2. Al almacenar una nueva clave, se utilizan dos funciones hash para el cálculo al mismo tiempo y se obtienen dos direcciones: h 1 [clave] y H2 [clave]. En este momento, debe verificar la ubicación de h 1 [clave] en T1 y la ubicación de H2 [clave] en T2, qué ubicación almacena más claves (en conflicto) y luego almacenar la nueva clave en la ubicación con menos carga. . Si hay varios bordes, por ejemplo, ambas ubicaciones están vacías o se almacena una clave, la nueva clave se almacena en la subtabla T1 de la izquierda, por lo tanto, 2-izquierda. Al buscar una clave, se debe aplicar hash dos veces y buscar en ambas ubicaciones.
Ejemplos de preguntas: 1). Se utilizan datos de registro masivos para extraer las IP que más visitan 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 directamente las IP en la memoria y luego realizar estadísticas.
3. Mapa de bits
Ámbito de aplicación: puede buscar, copiar y eliminar datos rápidamente. En términos generales, el rango de datos es menos de 10 veces el tamaño de int.
Principios básicos y puntos clave: utilice una matriz de bits para indicar si existen ciertos elementos, como un número de teléfono de 8 dígitos.
Extensión: el filtro Bloom puede considerarse 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.
8 bits hasta 99 999 999, lo que requiere unos 99 millones de bits, o unos 10 MB de memoria.
2) Encuentre el número de enteros no repetidos entre los 250 millones de enteros. El espacio de memoria no es suficiente para acomodar estos 250 millones de enteros.
Amplíe el mapa de bits de 2 bits y use solo 2 bits para representar un número, 0 significa que no aparece, 1 significa que aparece una vez y 2 significa que aparece dos o más veces. O en lugar de usar 2 bits para representarlo, podemos usar dos mapas de bits para simular e implementar este mapa de 2 bits.
Apilamiento
Ámbito de aplicación: la parte superior n de datos masivos es grande, n es relativamente pequeña y la memoria se puede acumular.
Principios básicos y puntos clave: el montón máximo es más pequeño que el primer n y el montón mínimo es más grande que el primer n Métodos, como encontrar el primer n que es más pequeño, comparamos el actual. elemento con el elemento más grande en el montón máximo Se hace una comparación y si es más pequeño que el elemento más grande, debemos reemplazar ese elemento más grande. De esta forma, los últimos n elementos son los n elementos más pequeños. Es adecuado para grandes cantidades de datos, y el n superior es pequeño y el tamaño de n es relativamente pequeño, por lo que todos los n elementos superiores se pueden obtener mediante un escaneo, lo cual es muy eficiente.
Extensión: se puede utilizar un montón dual, una combinación de un montón máximo y un montón mínimo, para mantener los valores medios.
Preguntas de ejemplo:
1) Encuentra los 100 números más grandes entre 1 millón de números.
Utiliza un montón de al menos 100 elementos.
5. División de barril binario
Alcance aplicable: el k-ésimo número más grande, medio, no repetido o repetido
Principios básicos y puntos clave: debido a la El rango es demasiado grande para usar una tabla de direccionamiento directo, por lo que el rango se determina gradualmente dividiéndolo varias veces y finalmente dentro de un rango aceptable. Se puede reducir muchas veces; la doble capa es sólo un ejemplo.
Extensiones:
Ejemplos de preguntas:
1). Para calcular 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.
Esto es un poco como el principio del nido de palomas, el número entero es 2^32, es decir, podemos dividir el número de 2^32 en 2^8 áreas (por ejemplo, un solo archivo representa un área), y luego divida los datos. Divídalos en diferentes áreas, y luego las diferentes áreas se pueden resolver directamente usando mapas de bits. Dicho esto, se puede solucionar fácilmente siempre que tengas suficiente espacio en disco.
2). 500 millones de números enteros encuentran su mediana.
Este ejemplo es más obvio que el anterior. Primero, dividimos el int en 2 16 regiones y luego leemos los datos para contar el número de números que caen en cada región. Luego podemos juzgar en qué área cae la mediana según los resultados estadísticos, sabiendo que el número más grande en esta área resulta ser la mediana. Luego, en el segundo escaneo, solo necesitamos contar aquellos números que caen en esa área.
De hecho, si no es un int sino un int64, podemos reducirlo a un nivel aceptable después de tres de esas divisiones. es decir, int64 se puede dividir en 2 ^ 24 regiones, luego se puede determinar el número máximo de regiones, luego la región se puede dividir en 2 ^ 20 subregiones, luego se puede determinar el número máximo de subregiones y luego el número de números en las subregiones es solo 2 ^ 20, por lo que la tabla de direcciones directas se puede usar directamente para estadísticas.
6. Índice de base de datos
Ámbito de aplicación: agregar, eliminar, modificar y consultar big data.
Principios básicos y puntos clave: utilice métodos de implementación y diseño de datos para agregar, eliminar, modificar y verificar datos masivos.
Extensiones:
Ejemplos de preguntas:
7. Índice invertido
Ámbito aplicable: motores de búsqueda, consultas de palabras clave
Principios básicos y puntos clave: ¿Por qué se llama índice invertido? El método de índice se utiliza para almacenar un mapa de dónde se almacena una palabra en una búsqueda de texto completo o en un conjunto de documentos.
Tomemos el inglés como ejemplo, el siguiente es el texto a indexar:
T0 = "Eso es"
T1 = "Qué es esto"
T2="Esto es un plátano"
Podemos obtener el siguiente índice de archivo inverso:
"a":{ 2}
" Plátano":{2}
" es ":{0, 1, 2}
" it ":{0, 1, 2}
" what":{ 0, 1}
Las condiciones de recuperación "what", "is" y "it" corresponderán a la intersección de los conjuntos.
La lista de palabras utilizadas para almacenar cada documento en el índice. Las consultas contra índices directos a menudo encuentran consultas que realizan consultas ordenadas y frecuentes de texto completo en cada documento y una validación que verifica cada palabra del documento. En un índice directo, los documentos ocupan una posición central y cada documento apunta a la serie de entradas del índice que contiene. Es decir, el documento apunta a la palabra que contiene y el índice invertido apunta a la palabra del documento que lo contiene, por lo que 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 por palabra clave de artículos académicos comunes.
8. Clasificación externa
Ámbito de aplicación: clasificación y deduplicación de big data.
Principios básicos y puntos clave: el método de combinación de clasificación externa, el principio de reemplazar el árbol perdedor y el árbol de combinación óptimo.
Extensión:
Ejemplo de problema:
1). Hay un archivo con un tamaño de 1G, en el que cada línea tiene una palabra y la longitud de la palabra. No supera las 16 palabras, el tamaño del límite de memoria es 1M. Devuelve las 100 palabras más frecuentes.
Estos datos tienen características obvias. La longitud de la palabra es de 16 bytes, pero la memoria es de solo 1 m, lo que no es suficiente para hash y puede usarse para ordenar. La memoria se puede utilizar como búfer de entrada.
9. Árbol Trie
Ámbito de aplicación: gran cantidad de datos y muchas repeticiones, pero se pueden colocar pequeños tipos de datos en la memoria.
Principios básicos y puntos clave: método de implementación, método de representación de subnodos de nodos.
Extensión: implementación de compresión.
Ejemplo de problema:
1). Hay 10 archivos en total, cada archivo es 1G, cada fila de cada archivo almacena la consulta del usuario y la consulta de cada archivo puede ser mayor. repetirse. Quiero que ordenes según la frecuencia de las consultas.
2). 100.000 cadenas, algunas de ellas son idénticas (duplicadas), por lo que es necesario eliminar todas las cadenas duplicadas y conservar las no duplicadas. ¿Cómo diseñar e implementar?
3) Consultas de búsqueda populares: la tasa de repetición de las cadenas de consulta es relativamente alta. Aunque el total es 1 millón, si se eliminan los duplicados, no excederá los 3 millones y cada cadena de consulta no excederá los 255 bytes.
10. Mapreduce de procesamiento distribuido
Ámbito de aplicación: gran cantidad de datos, pero se pueden colocar pequeños tipos de datos en la memoria.
Principios básicos y puntos clave: Entregar datos a diferentes máquinas para su procesamiento, dividir los datos y reducir los resultados.
Extensión:
Ejemplo de problema:
1). Una aplicación de ejemplo típica de MapReduce es un par de
cada palabra diferente:
Mapa vacío (nombre de cadena, documento de cadena):
//Nombre: Nombre del documento
//Documento: Contenido del documento
Para cada palabra w en el documento:
emitir intermedio(w, 1);
void reduce(palabra de cadena, recuento de partes del iterador):
// Palabra clave: una palabra
//Valor: una lista de recuentos parciales agregados
int resultado = 0;
Para cada v en el recuento parcial:
resultado+= parse int(v);
Emitir(resultado);
Aquí, cada documento se divide en palabras, cada una con un recuento inicial de "1"
Función de mapa, usando palabras como claves de resultados. El marco reúne todos los pares de
la misma clave y los envía a la misma llamada para reducir, por lo que la función solo necesita
sumar todos los valores de entrada y encontrar Obtener el Número total de apariciones de la palabra.
2). Los datos masivos se distribuyen entre 100 ordenadores. Encuentre una manera de contar de manera eficiente el TOP10 de este lote de datos.
3). A * * * tiene n máquinas y cada máquina tiene n números. Cada máquina puede almacenar hasta números O(N) y operar con ellos. ¿Cómo encontrar la mediana de n 2 números?
Análisis de problemas clásico
Diez millones o miles de millones de datos (con duplicación), cuente los n datos principales con mayor frecuencia, divididos en dos situaciones: se puede hacer todo a la vez Leer en la memoria, pero no todo a la vez.
Ideas disponibles: árbol trie + montón, índice de base de datos, estadísticas de subconjuntos de particiones, hash, computación distribuida, estadísticas aproximadas, clasificación externa.
Si se puede leer en la memoria al mismo tiempo, en realidad debería referirse a la cantidad de datos después de eliminar duplicados. Si los datos deduplicados se pueden guardar en la memoria, podemos crear un diccionario para los datos, como map, hashmap y trie, y luego realizar estadísticas directamente. Por supuesto, al actualizar el número de apariciones de cada dato, podemos usar el montón para mantener los n primeros datos con la mayor cantidad de ocurrencias. Sin embargo, esto conducirá a un aumento en el tiempo de mantenimiento y no es tan eficiente como encontrar los primeros n datos después de estadísticas completas.
Si los datos no se pueden almacenar en la memoria. Por un lado, podemos considerar si el método de diccionario anterior se puede mejorar para adaptarlo a esta situación. El cambio que podemos hacer es almacenar el diccionario en el disco duro en lugar de en la memoria. Esto puede referirse al método de almacenamiento de la base de datos.
Por supuesto, hay una manera mejor, que es utilizar computación distribuida, que es básicamente un proceso de reducción de mapas. Primero, los datos se pueden dividir en diferentes computadoras de acuerdo con el valor de los datos o el valor después del hash (md5), y es mejor leer los datos en la memoria inmediatamente después de la división, de modo que diferentes computadoras sean responsables de procesar varios valores. Alcance, esto es en realidad un mapeo. Después de obtener los resultados, cada computadora solo necesita sacar los n datos principales con la frecuencia más alta y luego resumir y seleccionar los n datos principales con la frecuencia más alta entre todos los datos. Este es en realidad el proceso de reducción.
De hecho, es posible que desees distribuir los datos directamente a diferentes ordenadores para su procesamiento, por lo que no obtendrás la solución adecuada. Porque algunos datos pueden estar distribuidos uniformemente entre diferentes computadoras, mientras que otros datos pueden estar completamente agregados en una computadora y aún tener la misma cantidad de datos. Por ejemplo, si queremos encontrar los 100 datos más frecuentes, distribuiremos 1 millón de datos en 100 máquinas y encontraremos los 100 más frecuentes. No hay garantía de que se encuentren los 100 reales después de la fusión, porque, por ejemplo, se pueden encontrar los 100 con el mayor número de veces. Pero dividido en 10 máquinas, por lo que solo hay 1000 máquinas en cada máquina.
Suponiendo que todas las máquinas clasificadas antes de 1000 están distribuidas en una sola máquina, por ejemplo, hay 1001 máquinas, entonces esta máquina con 1000 será eliminada, incluso si, por lo tanto, no podemos dividir los datos aleatoriamente en diferentes computadoras, sino que es asignado a diferentes computadoras para su procesamiento en función del valor hash, de modo que diferentes computadoras 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. Después del procesamiento, se combinan las palabras y su frecuencia de aparición. De hecho, puede utilizar un proceso de clasificación y combinación externo.
Además, también podemos considerar la computación aproximada, es decir, podemos combinar propiedades del lenguaje natural y usar solo aquellas palabras que aparecen más en la práctica real como diccionario, de modo que esta escala se pueda guardar en la memoria. .