De acuerdo, sé que la pregunta es sobre Java y los algoritmos y, de lo contrario, resolver este problema no es el punto, pero sigo pensando que esta solución debe publicarse para que esté completa.

Solución en sh :

 sort FILE | uniq -c | sort -nr | head -n 100

Explicación: sort | uniq -c enumera solo entradas únicas y cuenta el número de ocurrencias en la entrada; sort -nr ordena la salida numéricamente en orden inverso (las líneas con más ocurrencias en la parte superior); head -n 100 mantiene 100 líneas superiores solamente. Un archivo con 4.000.000.000 números hasta 999999999 (según OP) ocupará unos ~40 GB, por lo que cabe bien en un disco de una sola máquina, por lo que es técnicamente posible utilizar esta solución.

Pro: simple, tiene un uso de memoria constante y limitado. Contras: subóptimo (debido a la sort ), consume mucho espacio temporal en disco para la operación y, en general, no hay duda de que una solución diseñada específicamente para este problema tendrá un rendimiento mucho mejor. La pregunta sigue siendo (con toda seriedad): en un caso general, ¿escribir (y luego depurar y ejecutar) una solución optimizada llevará más o menos tiempo que usar una subóptima (como la anterior) pero disponible de inmediato? Ejecuté la solución en un archivo de muestra con 400 000 000 líneas (10 veces más pequeño) y tardé unos 7 minutos en mi computadora.

PD En una nota al margen, OP menciona que esta pregunta se hizo durante una entrevista de programación. Esto es interesante porque creo que es un tipo de solución que vale la pena mencionar en este contexto antes de comenzar a codificar otro programa desde cero. Cuando la gente dice "los ingenieros experimentados son 10 veces más rápidos...", personalmente no creo que se deba a que los ingenieros experimentados codifican más rápido o producen algoritmos optimizados, sino a que exploran las alternativas que pueden ahorrar tiempo. En el contexto de una entrevista, es una habilidad importante para demostrar, entre otras.

1. Divide tus números en dos cubos
2. Encuentra los 100 mejores en cada grupo
3. Combinar esas 100 listas principales.

Para dividir, haga la mediana de las medianas (que también se puede modificar para hacer medianas de la parte superior/inferior).

Cada cubo tiene un rango distinto de números en él. La división mediana inicial crea 2 cubos, cada uno con la mitad (aproximadamente) de los elementos que contiene la lista completa.

Para encontrar los 100 mejores, primero sepa si el cubo es estrecho (mínimo y máximo similares) O (1) o pequeño (pocos números en él) (O (n) tiempo O (n * recuento de cubos) memoria). Si cualquiera de los dos es cierto, un simple paso de conteo (posiblemente haciendo más de 1 cubo a la vez) lo resuelve (probablemente tendrá que hacerlo más de una vez, ya que tiene límites de memoria).

Si ninguno de los dos es cierto, recurra y divida ese cubo en dos.

Habrá partes complicadas con la forma en que se repite sin perder demasiado tiempo.

Pero la idea es que cada cubo se estreche o se haga más pequeño exponencialmente. Los cubos angostos tienen un mínimo y un máximo cercanos, y los cubos pequeños tienen pocos elementos.

Combina cubos para tener suficiente almacenamiento para contar los elementos en el cubo (ya sea basado en el ancho o en el volumen). Luego haces un pase que cuenta ese balde y encuentra los primeros 100, y repites. Cada vez que combina los 100 principales del escaneo con los 100 principales anteriores.

En el lugar, no es necesario clasificar toda la lista y se convierte en estrategias más simples y óptimas cuando el "cubo" inicial es estrecho o pequeño.

Simplemente colocaría todos los números en una base de datos ( SQLite sería mi primera opción) con una tabla como

 CREATE TABLE tbl ( number INTEGER PRIMARY KEY, counter INTEGER )

Luego, por cada número recibido, simplemente haga un

 INSERT INTO tbl (number,counter) VALUES (:number,1) ON DUPLICATE KEY UPDATE counter=counter+1;

o con sintaxis SQLite

 INSERT INTO tbl (number,counter) VALUES (:number,1) ON CONFLICT(number) DO UPDATE SET counter=counter+1;

Luego, cuando todos los números estén contabilizados,

 SELECT number, counter FROM tbl ORDER BY counter DESC LIMIT 100

... entonces terminaría con los 100 números más comunes y con qué frecuencia ocurrían. Este esquema solo fallará cuando se quede sin espacio en disco... (o cuando alcance ~ 20000000000000 (20 billones) de dígitos únicos en unos ~281 terabytes de espacio en disco... )

herramientas de linux

Eso simplemente se hace en un script de shell en Linux/Mac:

 sort inputfile | uniq -c | sort -nr | head -n 100

Si los datos ya están ordenados, simplemente use

 uniq -c inputfile | sort -nr | head -n 100

sistema de archivos

Otra idea es usar el número como nombre de archivo y aumentar el tamaño del archivo para cada visita.

 while read number; do echo -n "." >> number done <<< inputfile

Las restricciones del sistema de archivos podrían causar problemas con tantos archivos, por lo que puede crear un árbol de directorios con los primeros dígitos y almacenar los archivos allí.

Cuando termine, recorre el árbol y recuerda los 100 valores más altos vistos para el tamaño del archivo.

Base de datos

Puede usar el mismo enfoque con una base de datos, por lo que no necesita almacenar el GB de datos allí (también funciona), solo los contadores (necesita menos espacio).

Entrevista

Una pregunta interesante sería cómo maneja los casos extremos, entonces, ¿qué debería suceder si el número 100, 101, ... tiene la misma frecuencia? ¿Son los números enteros sólo positivos?

¿Qué tipo de salida necesitan, solo los números o también las frecuencias? Simplemente piénselo como una tarea real en el trabajo y pregunte todo lo que necesita saber para resolverlo. Se trata más de cómo piensas y analizas un problema.

Supongo que el objetivo del desafío es procesar esta gran cantidad de datos sin consumir demasiada memoria y evitar analizar la entrada demasiadas veces.

Aquí hay un algoritmo que requeriría dos matrices no demasiado grandes. No sé acerca de Java, pero estoy seguro de que se puede hacer que esto se ejecute muy rápido en C:

Cree una matriz Count de tamaño 2^n para contar la cantidad de números de entrada en función de sus n bits más significativos. Eso requerirá un primer escaneo sobre los datos de entrada, pero es realmente sencillo de hacer. Primero intentaría con n = 20 (alrededor de un millón de cubos).

Obviamente, no procesaremos los datos un cubo a la vez, ya que eso requeriría leer la entrada un millón de veces, en su lugar, elegimos nuestro tamaño de lote B óptimo y asignamos una matriz de lotes de tamaño B. B podría ser como 40M, por lo que que nuestro objetivo es leer la entrada unas 100 veces. (Todo depende de la memoria disponible).

Luego iteramos sobre la matriz de conteo para agrupar el primer rango de cubos para que la suma esté cerca, pero no exceda B.

Para cada uno de esos rangos, analizamos los datos de entrada, buscamos números en el rango y copiamos esos números en la matriz por lotes. Como ya sabemos el tamaño de cada cubo, podemos copiarlos inmediatamente agrupados por cubo, de modo que solo tengamos que ordenarlos cubo por cubo (puede reutilizar la matriz de conteo para almacenar los índices sobre dónde escribir la siguiente entrada). A continuación, contamos los elementos idénticos en la matriz de lotes ordenados y realizamos un seguimiento de los 100 principales hasta el momento.

Continúe con el siguiente rango de cubos para los que la suma de los recuentos sea inferior al tamaño B, etc.

Optimizaciones:

• Una vez que comencemos a tener un top 100 decente, puede omitir cubos enteros cuyo tamaño esté por debajo de nuestra entrada número 100. Para esto podemos usar un valor especial (como -1) en la matriz de conteo, para indicar que no hay índice. Dependiendo de los datos, esto puede reducir drásticamente el número de pasadas requeridas.
• Al contar elementos idénticos en el lote ordenado, podemos hacer saltos del tamaño de su entrada número 100 (y luego retroceder unos pasos. Puedo compartir pseudocódigo si es necesario)

Posibles problemas con este enfoque: los números de entrada podrían concentrarse en un rango pequeño, luego podría obtener uno o más cubos individuales que son más grandes que B. Posibles soluciones:

1. En su lugar, podría probar con otra selección de n bits (p. ej., los n bits menos significativos). Tenga en cuenta que eso aún no ayudará si los mismos números aparecen mil millones de veces.
2. Si la entrada son enteros de 32 bits, entonces el rango de valores posibles es limitado y solo puede haber unos pocos miles de números diferentes en cada depósito. Entonces, si un cubo es realmente grande, entonces podemos procesar ese cubo de manera diferente: simplemente mantenga un contador para cada valor único en ese rango. Podemos reutilizar la matriz Batch para eso.

En pseudocódigo:

1. Realizar una ordenación externa
2. Haz un pase para recopilar las 100 frecuencias principales (no qué valores las tienen)
3. Haz otra pasada para recolectar los valores que tienen esas frecuencias

Suposición: hay ganadores claros, sin empates (fuera de los 100 primeros).

Complejidad de tiempo: O (n log n) (aprox.) debido a la ordenación. Complejidad del espacio: memoria disponible, nuevamente debido a la ordenación.

Los pasos 2 y 3 son O(n) tiempo y O(1) espacio.

Si no hay empates (fuera de los 100 principales), los pasos 2 y 3 se pueden combinar en una sola pasada, lo que no mejoraría la complejidad del tiempo, pero mejoraría ligeramente el tiempo de ejecución.

Si hay empates que harían que la cantidad de ganadores fuera grande, no podrías descubrirlo y tomar una acción especial (por ejemplo, arrojar un error o descartar todos los empates) sin dos pases. Sin embargo, podría encontrar los 100 valores más pequeños de los lazos con una sola pasada.

Los números enteros tienen un signo de 32 bits, por lo que si solo ocurren números enteros positivos, observamos un máximo de 2^31 entradas diferentes. Una matriz de 2^31 bytes debe permanecer por debajo del tamaño máximo de la matriz.

¿Pero eso no puede contener frecuencias superiores a 255, diría usted? Sí tienes razón.

Entonces agregamos un hashmap para todas las entradas que excedan el valor máximo posible en su matriz (255, si está firmado, simplemente comience a contar en -128). Hay como máximo 16 millones de entradas en este mapa hash (4 mil millones divididos por 255), lo que debería ser posible.

Tenemos dos estructuras de datos:

• una matriz grande, indexada por el número leído (0..2^31) de bytes.
• un hashmap de (número leído, frecuencia)

Algoritmo:

 mientras lee el siguiente número 'x'
 {
   si (hashmap. contiene (x))
   {
     hashmap[x]++;
   }
   demás
   {
     matriz grande[x]++;
     si (bigarray[x] > 250)
     {
       hashmap[x] = bigarray[x];
     }
   }
 }

 // cuando termine:
 // Buscar top-100 en hashmap
 // si aún no son 100, agregue más de bigarray, omitiendo los que ya se tomaron del hashmap

No soy fluido en Java, así que no puedo dar un mejor ejemplo de código.

Tenga en cuenta que este algoritmo es de un solo paso, funciona con entradas no ordenadas y no utiliza pasos de preprocesamiento externos.

Todo lo que hace es asumir un máximo para el número leído. Debería funcionar si la entrada son enteros no negativos, que tienen un máximo de 2^31. La entrada de muestra satisface esa restricción.

El algoritmo anterior debería satisfacer a la mayoría de los entrevistadores que hacen esta pregunta. Si puede codificar en Java debe establecerse mediante una pregunta diferente. Esta pregunta trata sobre el diseño de estructuras de datos y algoritmos eficientes.

He notado que hay un error en esta línea.

 unsorted.put(number, unsorted.getOrDefault(number, 1) + 1);

Debe hacer que el valor predeterminado sea 0, ya que luego le agrega 1. Si no, cuando solo tiene 1 ocurrencia de un valor, se registra como la frecuencia de 2.

 unsorted.put(number, unsorted.getOrDefault(number, 0) + 1);

Una desventaja que veo es que no es necesario mantener los 4 mil millones de frecuencias cuando se está clasificando.

Puede usar PriorityQueue para contener solo 100 valores.

 Map<String, Integer> unsorted = new HashMap<>(); PriorityQueue<Map.Entry<String, Integer>> highestFrequentValues = new PriorityQueue<>(100, (o1, o2) -> o2.getValue().compareTo(o1.getValue())); // O(n) try (Scanner scanner = new Scanner(new File("numbers.txt"))) { while (scanner.hasNextLine()) { String number = scanner.nextLine(); unsorted.put(number, unsorted.getOrDefault(number, 0) + 1); } } // O(n) for (Map.Entry<String, Integer> stringIntegerEntry : unsorted.entrySet()) { if (highestFrequentValues.size() < 100) { highestFrequentValues.add(stringIntegerEntry); } else { Map.Entry<String, Integer> minFrequencyWithinHundredEntries = highestFrequentValues.poll(); if (minFrequencyWithinHundredEntries.getValue() < stringIntegerEntry.getValue()) { highestFrequentValues.add(stringIntegerEntry); } } } // O(n) for (Map.Entry<String, Integer> frequentValue : highestFrequentValues) { System.out.println(frequentValue.getKey()); }

Pero probablemente arrojaría una excepción OutOfMemory para el conjunto de datos de 4000000000 números. Además, dado que 4000000000 excede la longitud máxima de la matriz de Java, digamos que los números están en un archivo de texto y no están ordenados.

Eso depende de la distribución del valor. Si tiene números 4E9, pero los números son números enteros del 1 al 1000, terminará con un mapa de 1000 entradas. Si los números son dobles o el espacio de valores no está restringido, es posible que tenga un problema.

Como en la respuesta anterior , hay un error

 unsorted.put(number, unsorted.getOrDefault(number, 0) + 1);

Personalmente, usaría "AtomicLong" por valor, permite aumentar el valor sin actualizar las entradas de HashMap.

¿Supongo que subprocesos múltiples o Map Reduce serían más apropiados para grandes conjuntos de datos? ¿Cuál sería la solución más eficiente para este problema?

Este es un ejemplo típico de ejercicio de reducción de mapas, por lo que, en teoría, podría usar un enfoque de subprocesos múltiples o MR. Tal vez sea el objetivo de su ejercicio y suponga que debe implementar las tareas de reducción de mapas multiproceso, independientemente de si es la forma más eficiente o no.

En realidad debes calcular si vale la pena el esfuerzo. Si está leyendo la entrada en serie (como está en su código usando el Scanner ), definitivamente no. Si puede dividir los archivos de entrada y leer varias partes en paralelo, teniendo en cuenta el rendimiento de E/S, puede ser el caso.

O tal vez, si el espacio de valores es demasiado grande para caber en la memoria y necesitará reducir el conjunto de datos, puede considerar un enfoque diferente.

Si los datos están ordenados , puede recopilar los 100 primeros en O(n) donde n es el tamaño de los datos. Debido a que los datos están ordenados, los distintos valores son contiguos. Contarlos mientras se recorren los datos una vez le da la frecuencia global , que no está disponible cuando los datos no están ordenados.

Vea el código de ejemplo a continuación sobre cómo se puede hacer esto. También hay una implementación (en Kotlin) de todo el enfoque en GitHub

Nota: No es necesario ordenar. Lo que se requiere es que los valores distintos sean contiguos y, por lo tanto, no es necesario definir el orden; obtenemos esto de la clasificación, pero tal vez haya una manera de hacerlo de manera más eficiente.

Puede ordenar el archivo de datos utilizando la ordenación de combinación (externa) en aproximadamente O(n log n) dividiendo el archivo de datos de entrada en archivos más pequeños que quepan en su memoria, clasificándolos y escribiéndolos en archivos ordenados y luego combinándolos.

Acerca de este ejemplo de código:

• Los datos ordenados se representan mediante un long[] . Debido a que la lógica lee los valores uno por uno, es una buena aproximación de leer los datos de un archivo ordenado.

• El OP no especificó cómo se deben tratar los valores múltiples con la misma frecuencia; en consecuencia, el código no hace nada más que garantizar que el resultado sean los N valores principales sin ningún orden en particular y no implica que no haya otros valores con la misma frecuencia.

 import java.util.*; import java.util.Map.Entry; class TopN { private final int maxSize; private Map<Long, Long> countMap; public TopN(int maxSize) { this.maxSize = maxSize; this.countMap = new HashMap(maxSize); } private void addOrReplace(long value, long count) { if (countMap.size() < maxSize) { countMap.put(value, count); } else { Optional<Entry<Long, Long>> opt = countMap.entrySet().stream().min(Entry.comparingByValue()); Entry<Long, Long> minEntry = opt.get(); if (minEntry.getValue() < count) { countMap.remove(minEntry.getKey()); countMap.put(value, count); } } } public Set<Long> get() { return countMap.keySet(); } public void process(long[] data) { long value = data[0]; long count = 0; for (long current : data) { if (current == value) { ++count; } else { addOrReplace(value, count); value = current; count = 1; } } addOrReplace(value, count); } public static void main(String[] args) { long[] data = {0, 2, 3, 3, 4, 5, 5, 5, 5, 6, 6, 6, 7}; TopN topMap = new TopN(2); topMap.process(data); System.out.println(topMap.get()); // [5, 6] } }

Dado que el conjunto de datos es presumiblemente demasiado grande para la memoria, haría una ordenación de base hexadecimal. Entonces, el conjunto de datos se dividiría entre 16 archivos en cada paso con tantos pases como sea necesario para llegar al número entero más grande.

La segunda parte sería combinar los archivos en un gran conjunto de datos.

La tercera parte sería leer el archivo número por número y contar la ocurrencia de cada número. Guarde el número y el número de ocurrencias en una matriz bidimensional (la lista) que se ordena por tamaño. Si el siguiente número del archivo tiene más ocurrencias que el número en la lista con las ocurrencias más bajas, reemplace ese número.

Una opción es un tipo de búsqueda binaria. Considere un árbol binario donde cada división corresponde a un bit en un entero de 32 bits. Entonces, conceptualmente, tenemos un árbol binario de profundidad 32. En cada nodo, podemos calcular el conteo de números en el conjunto que comienza con la secuencia de bits para ese nodo. Este conteo es una operación O(n), por lo que el costo total de encontrar nuestra secuencia más común será O(n * f(n)) donde la función depende de cuántos nodos necesitamos enumerar.

Empecemos por considerar una búsqueda en profundidad. Esto proporciona un límite superior razonable para el tamaño de la pila durante la enumeración. Una búsqueda de fuerza bruta de todos los nodos es obviamente terrible (en ese caso, puede ignorar el concepto de árbol por completo y simplemente enumerar todos los números enteros), pero tenemos dos cosas que pueden evitar que necesitemos buscar en todos los nodos:

1. Si alguna vez llegamos a una rama donde hay 0 números en el conjunto que comienza con esa secuencia de bits, podemos podar esa rama y dejar de enumerar.

2. Una vez que llegamos a un nodo terminal, sabemos cuántas ocurrencias hay de ese número específico. Agregamos esto a nuestra lista de 'top 100', eliminando el más bajo si es necesario. Una vez que esta lista se llene, podemos comenzar a podar cualquier rama cuyo recuento total sea menor que el más bajo de los 'top 100'.

No estoy seguro de cuál sería el rendimiento promedio y el peor de los casos para esto. Tendería a funcionar mejor para conjuntos con menos números distintos y probablemente funciona peor para conjuntos que se aproximan a una distribución uniforme, ya que eso implica que será necesario buscar más nodos.

Algunas observaciones:

1. Hay como máximo N nodos terminales con recuentos distintos de cero, pero como N > 2^32 en este caso específico, eso no importa.

2. El número total de nodos para M nodos hoja (M = 2^32) es 2M-1. Esto sigue siendo lineal en M, por lo que el tiempo de ejecución en el peor de los casos está limitado por arriba en O(N*M).

3. Esto funcionará peor que simplemente buscar todos los números enteros para algunos casos, pero solo por un factor escalar lineal. Si esto funciona mejor en promedio depende de los datos esperados. Para conjuntos de datos uniformemente aleatorios, mi suposición intuitiva es que podría podar suficientes ramas una vez que se llene la lista de los 100 principales que tendería a requerir menos de M recuentos, pero eso tendría que evaluarse empíricamente o probarse.

4. Como cuestión práctica, el hecho de que este algoritmo solo requiera acceso de solo lectura al conjunto de datos (solo realiza un conteo de números que comienzan con un cierto patrón de bits) significa que es susceptible de paralelización al almacenar los datos en múltiples matrices, contando los subconjuntos en paralelo, luego sumando los conteos. Esto podría ser una aceleración bastante sustancial en una implementación práctica que es más difícil de hacer con un enfoque que requiere clasificación.

Un ejemplo concreto de cómo podría ejecutarse esto, para un conjunto más simple de números de 3 bits y solo para encontrar el más frecuente. Digamos que el conjunto es '000, 001, 100, 001, 100, 010'.

1. Cuente todos los números que comienzan con '0'. Esta cuenta es 4.

2. Vaya más profundo, cuente todos los números que comienzan con '00'. Esta cuenta es 3.

3. Cuenta todos los números que son '000'. Este conteo es 1. Este es nuestro nuevo más frecuente.

4. Cuenta todos los números que son '001'. Esta cuenta es 2. Este es nuestro nuevo más frecuente.

5. Tome la siguiente rama profunda y cuente todos los números que comienzan con '01'. Este recuento es 1, que es menor que nuestro más frecuente, por lo que podemos dejar de enumerar esta rama.

6. Cuente todos los números que comienzan con '1'. Este recuento es 1, que es menor que nuestro más frecuente, por lo que podemos dejar de enumerar esta rama.

7. No tenemos sucursales, así que hemos terminado y '001' es el más frecuente.

Supongo que se eligieron 4 billones para asegurarse de que el problema es demasiado grande para caber en la memoria de las máquinas de escritorio actuales. Entonces, ¿alquilar una máquina virtual grande de Amazon o Microsoft para ese propósito? Esa es una respuesta en la que la mayoría de la gente aún no piensa, pero es válida para soluciones del mundo real.

La forma en que lo abordaría es comenzar por agrupar . El rango de números es presumiblemente todos los enteros sin signo de 32 bits (o lo que sea que digan). ¿Qué tan grande de una matriz cabe en la RAM? divida el rango en tantos contenedores iguales y pase los datos una vez. Mire la distribución: ¿es bastante uniforme, puntiaguda o una curva de algún tipo? Si el primer/último rango de intervalos son ceros, entonces le brinda el rango real de valores de entrada, y puede ajustar el programa para que solo supere ese rango y repita, para obtener una mayor precisión.

Luego, dependiendo de la distribución, decida cómo proceder. En general, solo los 100 contenedores principales pueden contener los 100 valores principales, por lo que puede reconfigurar con esos rangos y los contenedores más grandes que puede manejar dentro de ese rango extraído. Si la distribución es demasiado uniforme, es posible que obtenga muchos contenedores con el mismo número, así que descarte los contenedores más pequeños aunque le queden muchos más de 100 contenedores; aún así, reduzca algunos .

¡En el peor de los casos, todos los contenedores salen iguales y no puedes cortarlos de esta manera! Alguien preparó algunos datos patológicos asumiendo este tipo de enfoque. Así que reorganiza la forma en que haces el binning. En lugar de simplemente dividirlos en rangos contiguos de igual tamaño, usamos un mapeo 1:1 para barajarlos. Sin embargo, para contenedores grandes, esto podría preservar la propiedad de ser bastante uniforme, por lo que no desea una función hash convencional "buena".

Otro enfoque

Si el agrupamiento funciona y reduce rápidamente el problema, es fácil. Pero los datos podrían ser tales que en realidad es muy difícil. Entonces, ¿cuál es una forma que siempre funciona, independientemente de los datos? Bueno, puedo suponer que el resultado existe: unos 100 valores tendrán más ocurrencias.

En lugar de contenedores, elija n valores específicos (sin importar cuántos pueda caber en la memoria). Elija números aleatorios o use los primeros N valores distintos de su entrada. Cuéntelos y copie los demás en otro archivo. Es decir, los valores que no tiene espacio para contar se copian en un archivo (más pequeño que el original).

Ahora al menos tendrá un valor pivote útil: la cardinalidad exacta de los 100 valores superiores distintos que contó exactamente. Bueno, ¡los que escogiste podrían terminar siendo todos del mismo conteo! Entonces solo tienes 1 cardinalidad distinta en el peor de los casos. Usted sabe que este no es un valor "superior" ya que hay muchos más de 100 de ellos.

Vuelva a ejecutar en su archivo nuevo (más pequeño) y descarte los recuentos que son más pequeños que los 100 principales que ya conoce. Repetir.

Esto me recuerda algo que podría haber leído en el TAOCP de Knuth, pero ampliado para los tamaños de las máquinas modernas.