P. “Si tengo una base de datos con 100 mil millones de nombres de usuario, ¿cómo construyo eficientemente una matriz ordenada a partir de eso para realizar fácilmente una búsqueda binaria?”
A menos que tenga un terabyte de RAM, tendría que acceder a su disco duro, mucho.
A menos que tenga un gran presupuesto para comprar un SSD por valor de terabyte, tendría que usar un disco duro giratorio.
- Si hipotéticamente encontré un algoritmo que genera rendimientos comerciales al 100% anualmente, ¿qué debo hacer con él?
- ¿Cuáles son algunos lenguajes de programación que me permiten visualizar algoritmos?
- ¿Por qué usamos algoritmos genéticos?
- ¿Es necesario que el vector se ordene para usar lower_bound?
- ¿Cuáles son algunos algoritmos de gráficos más utilizados en aplicaciones del mundo real?
Suponiendo que tiene un disco duro giratorio, el acceso aleatorio será muy costoso, de 10 a 100 ms. Por lo tanto, le gustaría minimizarlos tanto como pueda. Eso plantea la pregunta de si realmente desea realizar una búsqueda binaria en su estructura de datos final. Una búsqueda binaria en una matriz ordenada de 10 ^ 11 entradas, necesitaría [math] \ lceil log_2 (10 ^ {11}) \ rceil = 37 [/ math] operaciones de disco de acceso aleatorio. Suponiendo que los primeros 17 se ajusten a su caché de disco, necesitaría entre 0.2 y 2 segundos para encontrar un solo elemento con búsqueda binaria. Esto es horrible
Para eso, es mucho mejor usar una estructura de datos como B-tree o B + tree. Estos son n -arboles, donde cada nodo interno tiene n hijos. Dado que cuesta lo mismo traer 1 byte o 512 bytes del disco, o incluso más, dependiendo del tamaño del bloque. La lectura de varios bloques de discos adyacentes también es muy barata, por lo que un gran nodo de árbol B no es muy costoso. Si el nodo b-tree tiene 32 entradas, entonces necesita [math] \ lceil log_ {32} (10 ^ {11}) \ rceil = 8 [/ math] accesos de disco, y con caché de disco esto puede ser tan bajo como 4 accesos a disco. Esto costará solo 0.04–0.4 segundos, lo cual es mucho mejor.
También puede usar un Trie, que tendrá alrededor de 26 hijos en el nodo raíz, pero empeorará con cada paso que profundice. Para un nombre con 20 caracteres, deberá realizar 20 operaciones de acceso aleatorio en el disco, lo cual es bastante malo. En nombres cortos como Bill Gates, necesitará 10 operaciones de acceso aleatorio, lo cual es peor que el peor de los casos del árbol B.
Para mejorar las cosas, puede hacer un Trie que se ramifica en base a pares de letras. Entonces Bill Gates será representado como los pares [Bi] [ll] [G] [at] [es]. Esto acortará un poco el número de accesos aleatorios, pero aún así para nombres más largos como Kiefer William Frederick Dempsey George Rufus Sutherland todavía tendría que ejecutar 28 accesos aleatorios de disco. Esto será bastante lento. Si solo hay una persona cuyo nombre comienza con Kiefer William Frederick , podrá usar el Trie para almacenar este prefijo único y almacenar el nombre completo solo en la hoja. Sin embargo, esto todavía le da 12 solicitudes de disco, que todavía es bastante más lento que el árbol B.
Recientemente he implementado el árbol B + para optimizar el uso de la memoria caché de la CPU, lo que significa que el árbol b + es mucho más pequeño que el tuyo, pero todavía tengo algo de experiencia. En mi caso, los datos son dos veces más grandes que la clave, por lo que vale la pena usar el árbol B + en lugar de un árbol B. Además, las claves son lo suficientemente pequeñas como para caber 8 claves por línea de caché, lo que hace que valga la pena con respecto a la eficiencia del caché de la CPU.
Entonces, ¿cómo se crea un árbol b a partir de una lista aleatoria de nombres? Hay dos enfoques:
- Primero ordene la lista y cree un árbol B + de abajo hacia arriba de la lista. Encontré que este es el más eficiente para árboles B + basados en memoria, con nodos internos de tamaño 8. Sin embargo, la clasificación en disco tiene un conjunto de costos diferente que la clasificación en RAM, por lo que esta observación puede ser completamente irrelevante para su caso. Sin embargo, la clasificación se puede realizar de manera relativamente eficiente en el disco (ver más abajo), y la construcción de abajo hacia arriba se puede hacer casi secuencialmente, minimizando el número de escrituras aleatorias de disco.
- Inserte un elemento a la vez en el árbol B. Esto incurrirá en escrituras en disco O (N), lo que me parece horrible. No creo que sea práctico construir ni B-tree ni B + tree para 10 ^ 11 entradas de esta manera.
Entonces, ¿cómo se ordena una gran lista en el disco? Lo haces por partes, para minimizar las escrituras aleatorias en el disco.
disk_sort (disk_array, from, to) {
if (a – desde <= MAX_IN_RAM) {
in_mem: = read (disk_array, offset = from,
tamaño = de – a + 1);
in_mem.sort ();
escribir (disk_array, offset = from);
} más {
medio = (a + desde) / 2;
disk_sort (disk_array, from, middle -1);
disk_sort (disk_array, middle, to);
fusionar (disk_array, from, middle, to);
}
Si permite un búfer de 8 GB de RAM, que podría permitir 250 * 10 ^ 6 entradas, entonces podría fusionar solo 400 fragmentos ordenados. Si puede permitirse varios discos y varios hosts, estos bloques se pueden ordenar en paralelo. La fusión de 400 fragmentos requerirá 9 profundidades de fusión, donde cada profundidad procesará 10 ^ 11 entradas. Esto va a ser lento, pero al menos la mayor parte del trabajo es secuencial, por lo que estará limitado solo por el rendimiento del disco y no por el tiempo de acceso.
Si puede dividir el trabajo entre 100 hosts, esto será mucho más rápido. Incluso la fusión en el último paso se puede paralelizar, cuando tiene dos grandes conjuntos, se puede paralelizar bastante bien incluso si están muy desequilibrados.
EDITAR:
Mirando la respuesta de Eugene Yarovoi, perdí una gran oportunidad de optimización y paralelización. Si hay varios hosts disponibles, es posible, durante una fase inicial, dividir el trabajo entre estos hosts según la primera letra, o dos, del nombre. Entonces, si la lista original se encuentra en un disco de 2TB, la tarea principal repasará todos los nombres y enviará todos los nombres que comienzan con “aa” a un host, con “ab” a otro, y así sucesivamente. Cada host ordenará los resultados por sí mismo, y más tarde será posible fusionar los resultados en el archivo final en el disco de 2TB o guardarlos en hosts separados. Cada host contendrá un árbol B para el sufijo de los nombres.
Entonces “Bill Gates” irá al host “Bi”, que tendrá la entrada “ll Gates” en su árbol B. Esto hace que las cosas sean mucho más rápidas tanto para clasificar como para servir, y permitirá un mayor rendimiento de servicio. Probablemente debería replicar los datos varias veces, para un mayor rendimiento de acceso y una mayor confiabilidad.
Debería haber un servicio de búsqueda, que puede centralizarse, que elegirá el mejor host para cada consulta. Este servicio tendrá que tener en cuenta la carga, y si un prefijo de nombre dado tiene demasiadas solicitudes, tendrá que replicar ese host durante el tiempo de inactividad. También tendrá que replicar un host en caso de falla del disco.
EDIT2:
De nuevo, la respuesta de Eugene Yarovoi. Sugiere poner los nombres en una tabla hash distribuida. Podría ser una solución mucho mejor que la mía, pero depende de los detalles que nos faltan en la pregunta. Si todo lo que necesita es encontrar un nombre en su estructura de datos, una tabla hash distribuida podría ser una solución mucho mejor, suponiendo que no obtenga demasiados nombres en un cubo. En teoría, es posible que haya más de 1,000 entradas en un solo depósito, incluso si la función hash es razonablemente efectiva.
Soy demasiado vago para hacer los cálculos, pero suponiendo algo como la paradoja del cumpleaños, es muy posible que algunos cubos de hash obtengan más de 1,000 entradas. Es posible colocar todas las entradas en un área consecutiva del disco, por lo que acceder a todas las entradas en el depósito no será demasiado costoso. Incluso si la entrada de las entradas en el depósito puede ser rápida, existe el riesgo de fragmentación debido a futuras actualizaciones y reasignaciones del depósito. Para superar este problema, es posible usar árboles B para almacenar las entradas en cada depósito. Así que volvemos a los árboles B.
Otra cosa a tener en cuenta es que no sabemos por la pregunta si se requiere o no tener una lista ordenada, ya que no conocemos todos los casos de uso. Si una búsqueda es todo lo que necesitamos, entonces un hash distribuido es perfecto. Si queremos hacer otras cosas, como encontrar el siguiente nombre en una lista. ¿Qué pasa si queremos contar la cantidad de nombres que comienzan con George , como George Washington y George Lucas , entonces no podemos usar la tabla hash?
Otra cosa que no sabemos es cuántos nombres únicos hay. Si solo hay 1,000,000 de nombres únicos que se repiten una y otra vez, entonces las cosas son bastante triviales y podemos hacerlo todo en RAM.
EDITAR3:
Estoy de acuerdo con la respuesta de Can Baysal: usar un buen servidor SQL es más seguro y menos propenso a errores que implementarlo usted mismo. Un servidor SQL hace que toda mi respuesta sea bastante redundante.
Sin embargo, si tiene curiosidad por saber cómo se puede hacer esto desde cero, o si desea construir algo grande (como un servidor SQL o Google), entonces debe aprender cómo hacerlo desde cero, sin usar una base de datos SQL. Esto es como preguntar ” ¿cómo implemento una tabla hash ?”, Que se enseña en los cursos de CS a pesar de que está disponible, de fábrica, en la mayoría de los lenguajes de programación. Y sí, tuve que implementar una tabla hash recientemente, debido a los requisitos especiales de rendimiento.
EDITAR4:
Lea la excelente respuesta de Cameron Purdy con respecto a Trie. Tiene una experiencia práctica mucho mejor que mis predicciones para Trie. Mi respuesta fue demasiado conservadora para asumir que tener 2TiB RAM no es práctico. Sin embargo, Cameron menciona esta cifra como práctica, y estoy de acuerdo. Suponiendo que distribuya el Trie entre 32 hosts, donde cada host tiene 64 GiB, entonces esta configuración es completamente plausible. Una vez que guarda todo en la memoria, ordenar y acceder a los datos se vuelve muy rápido: micro segundos, como nos dice Cameron.
