El tiempo de ejecución mínimo requeriría al menos 2 mil millones de escaneos de filas: debe leer el archivo de registro
Suponiendo que cada nombre de usuario tiene un máximo de 20 caracteres de ancho,
- En el peor de los casos , habría 2 mil millones de nombres únicos que requieren 1 × 20 mil millones de bytes ~ 20 GB de almacenamiento como mínimo (vamos a almacenar solo un conjunto de nombres de usuario de registro, ya que todo lo que necesitamos son nombres de usuario comunes, por lo tanto, min es 0 , max es de mil millones)
- En el mejor de los casos , se repiten los 2 mil millones de nombres que requieren un mínimo de 20 bytes
Lea un archivo de registro y almacene todos los mil millones de nombre de usuario como par clave = valor.
Escanee el segundo archivo de registro y compruebe if (keymap[user] != null) {output(user)} else {next}
- ¿Por qué falla este método para encontrar la enésima posición de un nodo en una lista vinculada?
- ¿Podemos crear una matriz sin especificar un tamaño?
- ¿Dónde puedo encontrar datos de imágenes y sensores de las misiones MER-A y MER-B?
- ¿Cuál es el algoritmo utilizado por Google para la búsqueda por voz e imagen?
- ¿Cuál es exactamente la diferencia entre f (n) yg (n)?
Para buscar todos los nombres únicos, de la manera más eficiente, debe implementar un algoritmo Hash / Dictionary. es decir (solo pseudocódigo de alto nivel aquí)
if (hash (current_user_name) == null) {
set (hash (current_user_name)) && store (current_user_name)
}
Ahora, esto esencialmente encontraría y almacenaría todos los nombres de usuario únicos en los archivos de registro.
La mayoría de los lenguajes de programación modernos como Python / Perl / Java admiten una implementación de hash / diccionario altamente optimizada que establece / obtiene claves hash en un tiempo casi constante.
Por lo tanto, si tiene un servidor realmente bueno con una gran cantidad de RAM (> 20 GB, es decir, mejor que su requisito de Mem en el peor de los casos, que es costoso), puede usar Python / Perl hash en memoria.
Si la RAM no es una opción, debe usar otro tipo de bases de datos de valores clave. Sin embargo, estos serían más lentos (porque necesitan mirar más allá de la RAM y buscar almacenamiento HDD / Flash).
Puedo sugerir Couchbase, que usa disco duro (si tiene SSD, será bastante rápido)
¿Valor-clave o base de datos de documentos? Couchbase 2.0 cierra la brecha.
Alternativamente, encontré este DB que usa almacenamiento Flash (USB) para acelerar las cosas.
Página en Ucsd
Si realmente tiene que implementar todo usted mismo (sin usar una base de datos)
Entonces debe recurrir a la implementación de estas cosas altamente optimizadas en Python / Perl / Couchbase, etc. por su cuenta.
Por lo menos
- Escriba una función hash: para agrupar los nombres de usuario en un conjunto fijo de cubos (digamos 1000, cada uno puede representar un archivo en el disco duro)
- Almacene el nombre de usuario como par clave = valor en el depósito correspondiente (aproximadamente 1 millón de claves, par de valores, unos pocos MB y puede cargarse fácilmente en la RAM de uno en uno).
- Mientras escanea el segundo archivo y busca si el nombre de usuario ya existe, haga lo contrario.
- Calcule la identificación del depósito (utilizando la función hash anteriormente), cargue el depósito en la memoria y busque la clave (nombre de usuario) en ese depósito.
- Para acelerar un poco más las cosas, use hilos para lectura / escritura paralela en cubos.
