Escriba un programa para encontrar los 100 números más grandes de una matriz de mil millones de números.
Recientemente asistí a una entrevista en la que me pidieron "escribir un programa para encontrar los 100 números más grandes de una matriz de mil millones de números".
Solo pude dar una solución de fuerza bruta que consistía en ordenar la matriz en complejidad de tiempo O (nlogn) y tomar los últimos 100 números.
Arrays.sort(array);
El entrevistador buscaba una mejor complejidad temporal. Probé un par de soluciones más pero no pude responderle. ¿Existe una mejor solución para la complejidad del tiempo?
Puede mantener una cola de prioridad de los 100 números más grandes, iterar a través de los mil millones de números. Siempre que encuentre un número mayor que el número más pequeño en la cola (el encabezado de la cola), elimine el encabezado de la cola y agregue el nuevo número a la cola.
Una cola de prioridad implementada con un montón tiene una complejidad de inserción y eliminación de O(log K). (Donde K = 100, el número de elementos a encontrar. N = mil millones, el número total de elementos en la matriz).
En el peor de los casos, obtendrá cuál es mejor que para una clasificación 1 basada en comparación O (N log N) .billion*log2(100)billion*log2(billion)
En general, si necesita los K números más grandes de un conjunto de N números, la complejidad es O(N log K)más que O(N log N), esto puede ser muy significativo cuando K es muy pequeño en comparación con N.
El tiempo esperado de este algoritmo de cola de prioridad es bastante interesante, ya que en cada iteración puede ocurrir o no una inserción.
La probabilidad de que el i-ésimo número se inserte en la cola es la probabilidad de que una variable aleatoria sea mayor que al menos i-Klas variables aleatorias de la misma distribución (los primeros k números se agregan automáticamente a la cola). Podemos utilizar estadísticas de pedidos (ver enlace ) para calcular esta probabilidad.
Por ejemplo, supongamos que los números se seleccionaron aleatoriamente de manera uniforme{0, 1} , el valor esperado del (iK)ésimo número (de i números) es (i-k)/iy la probabilidad de que una variable aleatoria sea mayor que este valor es 1-[(i-k)/i] = k/i.
Por tanto, el número esperado de inserciones es:
Y el tiempo de ejecución esperado se puede expresar como:
( ktiempo para generar la cola con los primeros kelementos, luego n-klas comparaciones y el número esperado de inserciones como se describe anteriormente, cada uno toma un log(k)/2tiempo promedio)
Tenga en cuenta que cuando Nes muy grande en comparación con K, esta expresión está mucho más cerca nde N log K. Esto es algo intuitivo, ya que en el caso de la pregunta, incluso después de 10.000 iteraciones (lo cual es muy pequeño en comparación con mil millones), la posibilidad de que se inserte un número en la cola es muy pequeña.
Pero no sabemos si los valores de la matriz están distribuidos uniformemente. Es posible que tiendan a aumentar, en cuyo caso la mayoría o todos los números serán nuevos candidatos para el conjunto de los 100 números más grandes vistos. El peor caso para este algoritmo es O(N log K).
O si tienden a disminuir, la mayoría de los 100 números más grandes serán muy tempranos, y nuestro tiempo de ejecución en el mejor de los casos es esencialmente O(N + K log K), que es solo O(N)para Kmucho menor que N.
Nota al pie 1: ordenación de enteros O(N)/histograma
Counting Sort o Radix Sort son ambos O(N), pero a menudo tienen factores constantes más grandes que los hacen peores que los tipos de comparación en la práctica. En algunos casos especiales son bastante rápidos, principalmente para tipos de enteros estrechos.
Por ejemplo, Counting Sort funciona bien si los números son pequeños. Los números de 16 bits solo necesitarían una matriz de 2^16 contadores. Y en lugar de volver a expandirse en una matriz ordenada, puede simplemente escanear el histograma que construye como parte de Counting Sort.
Después de histogramar una matriz, puede responder rápidamente consultas para cualquier estadística de orden, por ejemplo, los 99 números más grandes, los números 200 a 100 más grandes). Los números de 32 bits dispersarían los recuentos en una matriz o tabla hash de contadores mucho más grande, lo que podría necesitar 16 GiB de memoria (4 bytes para cada uno de los 2^32 contadores). Y en las CPU reales, probablemente se produzcan muchos errores de TLB y caché, a diferencia de una matriz de 2 ^ 16 elementos donde normalmente se produciría un caché L2.
De manera similar, Radix Sort solo podía examinar los depósitos superiores después de una primera pasada. Pero los factores constantes aún pueden ser mayores que log K, dependiendo de K.
Tenga en cuenta que el tamaño de cada contador es lo suficientemente grande como para no desbordarse incluso si todos los N enteros están duplicados. Mil millones está algo por debajo de 2^30, por lo que un contador sin firmar de 30 bits sería suficiente. Y un entero de 32 bits con o sin signo está bien.
Si tuviera muchos más, es posible que necesite contadores de 64 bits, que ocupan el doble de memoria para inicializarse a cero y acceder aleatoriamente. O un valor centinela para los pocos contadores que desbordan un entero de 16 o 32 bits, para indicar que el resto del recuento está en otra parte (en un pequeño diccionario como una tabla hash asignada a contadores de 64 bits).
Si se pregunta esto en una entrevista, el entrevistador probablemente quiera ver su proceso de resolución de problemas, no solo su conocimiento de los algoritmos.
La descripción es bastante general, así que tal vez puedas preguntarle el rango o el significado de estos números para aclarar el problema. Hacer esto puede impresionar al entrevistador. Si, por ejemplo, estos números representan la edad de las personas, entonces el problema es mucho más sencillo. Con una suposición razonable de que nadie vivo tiene más de 200 años, puede usar una matriz de números enteros de tamaño 200 (tal vez 201) para contar la cantidad de personas con la misma edad en una sola iteración. Aquí el índice significa la edad. Después de esto, es muy fácil encontrar los 100 números más grandes. Por cierto, este algoritmo se llama clasificación por conteo .
De todos modos, hacer la pregunta más específica y clara es bueno para ti en una entrevista.
Puedes iterar sobre los números que toman O(n)
Siempre que encuentre un valor mayor que el mínimo actual, agregue el nuevo valor a una cola circular con tamaño 100.
El mínimo de esa cola circular es su nuevo valor de comparación. Sigue agregando a esa cola. Si está lleno, extraiga el mínimo de la cola.
