algorithm - numeros - millones billones trillones cuatrillones quintillones sextillones

Escriba un programa para encontrar los 100 números más grandes de una matriz de 1 billón de números (30)

Usa el elemento n para obtener el elemento 100 ''O (n)
Iterate la segunda vez, pero solo una vez, y genera cada elemento que sea mayor que este elemento específico.

Tenga en cuenta esp. ¡El segundo paso puede ser fácil de calcular en paralelo! Y también será eficiente cuando necesite un millón de elementos más grandes.

Hace poco asistí a una entrevista en la que me preguntaron "escriba un programa para encontrar los 100 números más grandes de un conjunto de mil millones de números".

Solo pude dar una solución de fuerza bruta que era ordenar la matriz en complejidad de tiempo O (nlogn) y tomar los últimos 100 números.

Arrays.sort(array);

El entrevistador estaba buscando un mejor momento de complejidad, probé un par de otras soluciones pero no le contesté. ¿Hay una solución de complejidad de tiempo mejor?

Dos opciones:

(1) Montón (prioridadQueue)

Mantener un montón mínimo con un tamaño de 100. Recorre la matriz. Una vez que el elemento es más pequeño que el primer elemento en el montón, reemplazarlo.

InSERT ELEMENT INTO HEAP: O（log100） compare the first element: O(1) There are n elements in the array, so the total would be O(nlog100), which is O(n)

(2) Mapa de reducir el modelo.

Esto es muy similar al ejemplo de conteo de palabras en hadoop. Trabajo de mapa: cuenta la frecuencia de cada elemento o los tiempos aparecidos. Reducir: Obtener el elemento K superior.

Por lo general, le daría dos respuestas al reclutador. Dales lo que quieran. Por supuesto, la codificación de reducción de mapas sería laboriosa, ya que debe conocer cada parámetro exacto. No hay daño para practicarlo. Buena suerte.

Inspirado en la respuesta de @ron teller, aquí hay un programa de C de barebones para hacer lo que quieras.

#include <stdlib.h> #include <stdio.h> #define TOTAL_NUMBERS 1000000000 #define N_TOP_NUMBERS 100 int compare_function(const void *first, const void *second) { int a = *((int *) first); int b = *((int *) second); if (a > b){ return 1; } if (a < b){ return -1; } return 0; } int main(int argc, char ** argv) { if(argc != 2){ printf("please supply a path to a binary file containing 1000000000" "integers of this machine''s wordlength and endianness/n"); exit(1); } FILE * f = fopen(argv[1], "r"); if(!f){ exit(1); } int top100[N_TOP_NUMBERS] = {0}; int sorts = 0; for (int i = 0; i < TOTAL_NUMBERS; i++){ int number; int ok; ok = fread(&number, sizeof(int), 1, f); if(!ok){ printf("not enough numbers!/n"); break; } if(number > top100[0]){ sorts++; top100[0] = number; qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function); } } printf("%d sorts made/n" "the top 100 integers in %s are:/n", sorts, argv[1] ); for (int i = 0; i < N_TOP_NUMBERS; i++){ printf("%d/n", top100[i]); } fclose(f); exit(0); }

En mi máquina (Core i3 con un SSD rápido) toma 25 segundos y 1724 clasificaciones. Generé un archivo binario con dd if=/dev/urandom/ count=1000000000 bs=1 para esta ejecución.

Obviamente, hay problemas de rendimiento con la lectura de solo 4 bytes a la vez, desde el disco, pero esto es por ejemplo. En el lado positivo, se necesita muy poca memoria.

La solución más simple es escanear la matriz grande de mil millones de números y mantener los 100 valores más grandes encontrados hasta ahora en un búfer de matriz pequeña sin ninguna clasificación y recordar el valor más pequeño de este búfer. Primero pensé que este método fue propuesto por fordprefect, pero en un comentario dijo que asumió que la estructura de datos de 100 números se estaba implementando como un montón. Cada vez que se encuentra un nuevo número que es más grande, el nuevo valor encontrado sobrescribe el mínimo en el búfer y se busca nuevamente el búfer en el búfer. Si los números en la matriz de miles de millones se distribuyen aleatoriamente la mayor parte del tiempo, el valor de la matriz grande se compara con el mínimo de la matriz pequeña y se descarta. Solo para una fracción muy pequeña de número, el valor debe insertarse en la matriz pequeña. Por lo tanto, la diferencia de manipular la estructura de datos que contiene los números pequeños puede ignorarse. Para una pequeña cantidad de elementos es difícil determinar si el uso de una cola de prioridad es realmente más rápido que usar mi enfoque ingenuo.

Quiero estimar el número de inserciones en el pequeño búfer de matriz de 100 elementos cuando se escanea la matriz de 10 ^ 9 elementos. El programa escanea los primeros 1000 elementos de esta gran matriz y debe insertar como máximo 1000 elementos en el búfer. El búfer contiene 100 elementos de los 1000 elementos escaneados, es decir, 0.1 del elemento escaneado. Por lo tanto, suponemos que la probabilidad de que un valor de la matriz grande sea mayor que el mínimo actual del búfer es de aproximadamente 0,1 Este elemento debe insertarse en el búfer. Ahora el programa escanea los siguientes 10 ^ 4 elementos de la matriz grande. Porque el mínimo del búfer aumentará cada vez que se inserte un nuevo elemento. Estimamos que la proporción de elementos más grande que nuestro mínimo actual es de aproximadamente 0.1 y, por lo tanto, hay 0.1 * 10 ^ 4 = 1000 elementos para insertar. En realidad, el número esperado de elementos que se insertan en el búfer será menor. Después del escaneo de esta fracción de 10 ^ 4 elementos, los números en el búfer serán aproximadamente 0.01 de los elementos escaneados hasta el momento. Entonces, al escanear los próximos 10 ^ 5 números, asumimos que no se insertarán más de 0.01 * 10 ^ 5 = 1000 en el búfer. Continuando con esta argumentación, hemos insertado alrededor de 7000 valores después de escanear 1000 + 10 ^ 4 + 10 ^ 5 + ... + 10 ^ 9 ~ 10 ^ 9 elementos de la matriz grande. Por lo tanto, al escanear una matriz con 10 ^ 9 elementos de tamaño aleatorio, esperamos no más de 10 ^ 4 (= 7000 redondeadas) inserciones en el búfer. Después de cada inserción en el búfer se debe encontrar el nuevo mínimo. Si el búfer es una matriz simple, necesitamos 100 comparaciones para encontrar el nuevo mínimo. Si el búfer es otra estructura de datos (como un montón) necesitamos al menos 1 comparación para encontrar el mínimo. Para comparar los elementos de la gran variedad necesitamos 10 ^ 9 comparaciones. Entonces, en general, necesitamos alrededor de 10 ^ 9 + 100 * 10 ^ 4 = 1.001 * 10 ^ 9 comparaciones cuando usamos una matriz como buffer y al menos 1,000 * 10 ^ 9 comparaciones cuando usamos otro tipo de estructura de datos (como un montón) . Por lo tanto, el uso de un montón solo genera una ganancia del 0,1% si el rendimiento se determina por el número de comparación. Pero ¿cuál es la diferencia en el tiempo de ejecución entre insertar un elemento en un montón de 100 elementos y reemplazar un elemento en una matriz de 100 elementos y encontrar su nuevo mínimo?

En el nivel teórico: cuántas comparaciones se necesitan para insertar en un montón. Sé que es O (log (n)) pero ¿qué tan grande es el factor constante? yo
A nivel de máquina: ¿Cuál es el impacto del almacenamiento en caché y la predicción de ramificación en el tiempo de ejecución de una inserción de montón y una búsqueda lineal en una matriz.
En el nivel de implementación: ¿Qué costos adicionales se ocultan en una estructura de datos de montón proporcionada por una biblioteca o un compilador?

Creo que estas son algunas de las preguntas que deben responderse antes de que uno pueda intentar estimar la diferencia real entre el rendimiento de un montón de 100 elementos o una matriz de 100 elementos. Por lo tanto, tendría sentido hacer un experimento y medir el rendimiento real.

Me di cuenta de que esto está etiquetado con ''algoritmo'', pero eliminará algunas otras opciones, ya que probablemente también debería estar etiquetado como ''entrevista''.

¿Cuál es la fuente de los mil millones de números? Si se trata de una base de datos, entonces ''seleccionar valor del orden de tabla por valor desc límite 100'' haría el trabajo bastante bien, podría haber diferencias dialectales.

¿Es esto una sola vez, o algo que se repetirá? Si se repite, ¿con qué frecuencia? Si es de una sola vez y los datos están en un archivo, entonces ''cat srcfile | ordenar (opciones según sea necesario) | head -100 ''te hará realizar rápidamente un trabajo productivo por el que te pagan por hacer mientras la computadora maneja esta tarea trivial.

Si se repite, aconsejaría elegir cualquier enfoque decente para obtener la respuesta inicial y almacenar / almacenar en caché los resultados para que pueda informar continuamente los 100 primeros.

Finalmente, hay esta consideración. ¿Está buscando un trabajo de nivel de entrada y entrevistarse con un gerente geek o futuro compañero de trabajo? Si es así, puede desechar todo tipo de enfoques que describan los pros y los contras técnicos relativos. Si está buscando un trabajo más administrativo, acérquelo como lo haría un gerente, preocupado por los costos de desarrollo y mantenimiento de la solución, y diga "muchas gracias" y váyase si ese es el entrevistador que desea centrarse en las trivialidades de CS. . Es poco probable que él y usted tengan mucho potencial de avance allí.

Mejor suerte en la próxima entrevista.

Mi reacción inmediata para esto sería usar un montón, pero hay una manera de usar QuickSelect sin tener todos los valores de entrada a la mano en cualquier momento.

Cree una matriz de tamaño 200 y rellénela con los primeros 200 valores de entrada. Ejecute QuickSelect y descarte los 100 bajos, dejándole con 100 lugares libres. Lea los siguientes 100 valores de entrada y ejecute QuickSelect nuevamente. Continúe hasta que haya ejecutado toda la entrada en lotes de 100.

Al final tienes los 100 mejores valores. Para los valores de N, ha ejecutado QuickSelect aproximadamente N / 100 veces. Cada Quickselect cuesta alrededor de 200 veces la constante, por lo que el costo total es 2N veces la constante. Esto se ve lineal en el tamaño de la entrada para mí, independientemente del tamaño del parámetro que estoy programando para ser 100 en esta explicación.

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 jefe de la cola), quite el encabezado de la cola y agregue el nuevo número a la cola.

EDITAR: como señaló Dev, con una cola de prioridad implementada con un montón, la complejidad de la inserción en la cola es O(logN)

En el peor de los casos, obtiene billion log ₂ (100) que es mejor que billion log ₂ (billion)

En general, si necesita los K números más grandes de un conjunto de N números, la complejidad es O(NlogK) lugar de O(NlogN) , esto puede ser muy significativo cuando K es muy pequeño en comparación con N.

EDIT2:

El tiempo esperado de este algoritmo es bastante interesante, ya que en cada iteración puede ocurrir o no una inserción. La probabilidad de que se inserte el número i''th en la cola es la probabilidad de que una variable aleatoria sea mayor que al menos iK variables aleatorias de la misma distribución (los primeros k números se agregan automáticamente a la cola). Podemos usar estadísticas de orden (ver link ) para calcular esta probabilidad. Por ejemplo, supongamos que los números se seleccionaron aleatoriamente de manera uniforme de {0, 1} , el valor esperado de (iK) th número (de i números) es (ik)/i , y la probabilidad de que una variable aleatoria sea mayor que esto el valor es 1-[(ik)/i] = k/i .

Así, el número esperado de inserciones es:

Y el tiempo de ejecución esperado se puede expresar como:

( k tiempo para generar la cola con los primeros k elementos, luego nk comparaciones y el número esperado de inserciones como se describió anteriormente, cada una toma un log(k)/2 promedio log(k)/2 )

Tenga en cuenta que cuando N es muy grande en comparación con K , esta expresión está mucho más cerca de n que de NlogK . Esto es algo intuitivo, como en el caso de la pregunta, incluso después de 10000 iteraciones (que es muy pequeña en comparación con mil millones), la posibilidad de que se inserte un número en la cola es muy pequeña.

Puede usar el algoritmo de selección rápida para encontrar el número en el índice (por orden) [miles de millones-101] y luego iterar sobre los números y encontrar los números más grandes de ese número.

array={...the billion numbers...} result[100]; pivot=QuickSelect(array,billion-101);//O(N) for(i=0;i<billion;i++)//O(N) if(array[i]>=pivot) result.add(array[i]);

El tiempo de este algoritmo es: 2 XO (N) = O (N) (Rendimiento promedio del caso)

La segunda opción como Thomas Jungblut sugiere es:

Use Heap construyendo el MAX. El montón tomará O (N), luego los 100 números máximos máximos estarán en la parte superior del Heap, todo lo que necesita es sacarlos del montón (100 XO (Log (N)).

Este tiempo del algoritmo es: O (N) + 100 XO (Log (N)) = O (N)

Puedes iterar sobre los números que toman O (n)

Cuando 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.

Si bien la otra solución de selección rápida se ha bajado, el hecho es que la selección rápida encontrará la solución más rápido que usar una cola de tamaño 100. La selección rápida tiene un tiempo de ejecución esperado de 2n + o (n), en términos de comparaciones. Una implementación muy simple sería

array = input array of length n r = Quickselect(array,n-100) result = array of length 100 for(i = 1 to n) if(array[i]>r) add array[i] to result

Esto tomará 3n + o (n) comparaciones en promedio. Además, se puede hacer más eficiente con el hecho de que la selección rápida dejará los 100 elementos más grandes en la matriz en las 100 ubicaciones más a la derecha. De hecho, el tiempo de ejecución se puede mejorar a 2n + o (n).

Existe el problema de que este es el tiempo de ejecución esperado, y no el peor de los casos, pero al usar una estrategia de selección de pivotes decente (por ejemplo, elegir 21 elementos al azar y elegir la mediana de esos 21 como pivotes), entonces el número de comparaciones puede ser garantizado con alta probabilidad de estar como máximo (2 + c) n para una constante arbitrariamente pequeña c.

De hecho, al utilizar una estrategia de muestreo optimizada (por ejemplo, elementos sqrt (n) de muestra al azar y elegir el percentil 99), el tiempo de ejecución puede reducirse a (1 + c) n + o (n) para c arbitrariamente pequeño (Suponiendo que K, el número de elementos a seleccionar es o (n)).

Por otro lado, usar una cola de tamaño 100 requerirá comparaciones de O (log (100) n), y la base de registros 2 de 100 es aproximadamente igual a 6.6.

Si pensamos en este problema en el sentido más abstracto de elegir los elementos K más grandes de una matriz de tamaño N, donde K = o (N) pero K y N van al infinito, entonces el tiempo de ejecución de la versión de selección rápida será O (N) y la versión en cola será O (N log K), por lo que en este sentido la selección rápida también es asintóticamente superior.

En los comentarios, se mencionó que la solución de cola se ejecutará en el tiempo esperado N + K log N en una entrada aleatoria. Por supuesto, el supuesto de entrada aleatoria nunca es válido a menos que la pregunta lo indique explícitamente. La solución de la cola se podría hacer para atravesar la matriz en un orden aleatorio, pero esto incurrirá en el costo adicional de N llamadas a un generador de números aleatorios, así como permutar toda la matriz de entrada o bien asignar una nueva matriz de longitud N que contenga índices aleatorios.

Si el problema no le permite moverse por los elementos de la matriz original, y el costo de asignar memoria es alto, por lo que duplicar la matriz no es una opción, eso es un asunto diferente. Pero estrictamente en términos de tiempo de ejecución, esta es la mejor solución.

Si esto se solicita en una entrevista, creo que 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, por lo que quizás pueda preguntarle el rango o el significado de estos números para aclarar el problema. Hacer esto puede impresionar a un entrevistador. Si, por ejemplo, estos números corresponden a la edad de las personas dentro de un país (por ejemplo, China), entonces es un problema mucho más fácil. Con la suposición razonable de que nadie vivo tiene más de 200 años, puede usar una matriz int de tamaño 200 (quizás 201) para contar el número de personas con la misma edad en una sola iteración. Aquí el índice significa la edad. Después de esto es un pedazo de pastel para encontrar 100 número más grande. Por cierto este algo se llama ordenación de conteo .

De todos modos, hacer que la pregunta sea más específica y clara es bueno para usted en una entrevista.

Toma los primeros 100 números de los mil millones y ordénalos. ahora solo iterar a través de los mil millones, si el número de origen es mayor que el más pequeño de 100, insértelo en orden de clasificación. Lo que terminas es algo mucho más cercano a O (n) sobre el tamaño del conjunto.

Una solución muy fácil sería recorrer la matriz 100 veces. Que es O(n) .

Cada vez que saque el número más grande (y cambie su valor al valor mínimo, de modo que no lo vea en la siguiente iteración, o realice un seguimiento de los índices de las respuestas anteriores (al hacer un seguimiento de los índices que puede tener la matriz original). múltiplo del mismo número)). Después de 100 iteraciones, tienes los 100 números más grandes.

Posibles mejoras.

Si el archivo contiene 1 número de billones, leerlo podría ser muy largo ...

Para mejorar este funcionamiento puedes:

Divida el archivo en n partes, cree n subprocesos, haga que n subprocesos busque cada uno de los 100 números más grandes en su parte del archivo (usando la cola de prioridad), y finalmente obtenga los 100 números más grandes de todos los resultados de subprocesos.
Utilice un clúster para realizar una tarea de este tipo, con una solución como hadoop. Aquí puede dividir el archivo aún más y obtener un resultado más rápido para un archivo de 1 billón (o 10 ^ 12).

Esta pregunta se respondería con N log (100) complejidad (en lugar de N log N) con solo una línea de código C ++.

std::vector<int> myvector = ...; // Define your 1 billion numbers. // Assumed integer just for concreteness std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());

La respuesta final sería un vector donde se garantiza que los primeros 100 elementos serán los 100 números más grandes de su matriz, mientras que los elementos restantes no están ordenados.

C ++ STL (biblioteca estándar) es bastante útil para este tipo de problemas.

Nota: No estoy diciendo que esta sea la solución óptima, pero habría guardado su entrevista.

Hice mi propio código, no estoy seguro de si es lo que el "entrevistador" está buscando.

private static final int MAX=100; PriorityQueue<Integer> queue = new PriorityQueue<>(MAX); queue.add(array[0]); for (int i=1;i<array.length;i++) { if(queue.peek()<array[i]) { if(queue.size() >=MAX) { queue.poll(); } queue.add(array[i]); } }

La complejidad es O (N).

Primero cree una matriz de 100 ints. Inicialice el primer elemento de esta matriz como el primer elemento de los valores N, realice un seguimiento del índice del elemento actual con otra variable, llámelo CurrentBig

Iterar aunque los valores de N

if N[i] > M[CurrentBig] { M[CurrentBig]=N[i]; ( overwrite the current value with the newly found larger number) CurrentBig++; ( go to the next position in the M array) CurrentBig %= 100; ( modulo arithmetic saves you from using lists/hashes etc.) M[CurrentBig]=N[i]; ( pick up the current value again to use it for the next Iteration of the N array) }

cuando termine, imprima la matriz M desde CurrentBig 100 veces módulo 100 :-) Para el alumno: asegúrese de que la última línea del código no supere los datos válidos justo antes de que salga el código

La solución simple sería usar una cola de prioridad, agregar los primeros 100 números a la cola y hacer un seguimiento del número más pequeño en la cola, luego iterar a través de los otros mil millones de números, y cada vez que encontremos uno que sea mayor que el número más grande en la cola de prioridad, eliminamos el número más pequeño, agregamos el nuevo número y, de nuevo, hacemos un seguimiento del número más pequeño en la cola.

Si los números estuvieran en orden aleatorio, esto funcionaría bien porque a medida que recorremos mil millones de números aleatorios, sería muy raro que el próximo número esté entre los 100 más grandes hasta el momento. Pero los números podrían no ser aleatorios. Si la matriz ya estaba ordenada en orden ascendente, siempre insertaremos un elemento en la cola de prioridad.

Así que elegimos, digamos, 100.000 números aleatorios de la matriz primero. Para evitar el acceso aleatorio que podría ser lento, agregamos, por ejemplo, 400 grupos aleatorios de 250 números consecutivos. Con esa selección aleatoria, podemos estar seguros de que muy pocos de los números restantes están entre los cien primeros, por lo que el tiempo de ejecución será muy similar al de un simple bucle que compara un billón de números con un valor máximo.

Otro algoritmo O (n) -

El algoritmo encuentra los 100 más grandes por eliminación.

Consideremos todos los millones de números en su representación binaria. Comienza desde el bit más significativo. Encontrar si el MSB es 1 se puede realizar mediante una multiplicación de operación booleana con un número apropiado. Si hay más de 100 1 en este millón, elimine los otros números con ceros. Ahora, de los números restantes, proceda con el siguiente bit más significativo. mantenga un recuento del número de números restantes después de la eliminación y proceda siempre que este número sea mayor que 100.

La operación booleana principal se puede realizar paralelamente en GPUs

Veo muchas discusiones sobre O (N), por lo que propongo algo diferente solo para el ejercicio mental.

¿Hay alguna información conocida sobre la naturaleza de estos números? Si es de naturaleza aleatoria, no continúe y mire las otras respuestas. No obtendrás mejores resultados que ellos.

¡Sin embargo! Vea si el mecanismo de llenado de listas completó esa lista en un orden particular. ¿Están en un patrón bien definido donde puede saber con certeza que la mayor magnitud de los números se encontrará en una determinada región de la lista o en un cierto intervalo? Puede haber un patrón para ello. Si es así, por ejemplo, si se garantiza que están en algún tipo de distribución normal con la joroba característica en el medio, siempre tienen tendencias ascendentes repetitivas entre los subconjuntos definidos, tienen un pico prolongado en algún momento T en el medio de los datos establecido como tal vez una incidencia de uso indebido de información privilegiada o fallas en el equipo, o tal vez simplemente tener un "pico" en cada número N como en el análisis de fuerzas después de una catástrofe, puede reducir significativamente la cantidad de registros que debe verificar.

Hay algo para pensar de todos modos. Tal vez esto te ayude a dar a los futuros entrevistadores una respuesta reflexiva. Sé que me impresionaría si alguien me hiciera esa pregunta en respuesta a un problema como este: me diría que están pensando en la optimización. Solo reconozca que no siempre puede haber una posibilidad de optimizar.

Administrar una lista separada es un trabajo adicional y debe mover las cosas por toda la lista cada vez que encuentre otro sustituto. Solo qsort it y toma el top 100.

Descubriría quién tuvo tiempo de poner mil millones de números en una matriz y despedirlo. Debe trabajar para el gobierno. Al menos, si tuviera una lista vinculada, podría insertar un número en el medio sin mover medio billón para hacer espacio. Aún mejor un Btree permite una búsqueda binaria. Cada comparación elimina la mitad de tu total. Un algoritmo hash le permitiría rellenar la estructura de datos como un tablero de ajedrez, pero no tan bueno para datos dispersos. Como su mejor opción es tener una matriz de soluciones de 100 enteros y hacer un seguimiento del número más bajo en su matriz de soluciones para que pueda reemplazarlo cuando se encuentre con un número mayor en la matriz original. Tendría que mirar cada elemento de la matriz original suponiendo que para empezar no esté ordenado.

Encontrar el top 100 de los mil millones de números se hace mejor usando un min-heap de 100 elementos.

Primero cebe el montón mínimo con los primeros 100 números encontrados. min-heap almacenará el más pequeño de los primeros 100 números en la raíz (arriba).

Ahora a medida que avanza el resto de los números, solo compárelos con la raíz (el más pequeño de los 100).

Si el nuevo número encontrado es más grande que la raíz de min-heap, reemplace la raíz con ese número, de lo contrario, ignórelo.

Como parte de la inserción del nuevo número en min-heap, el número más pequeño en el montón llegará a la parte superior (raíz).

Una vez que hayamos repasado todos los números, tendremos los 100 números más grandes en el montón mínimo.

Es una pregunta de Google o de algún otro gigante de la industria. Puede que el siguiente código sea la respuesta correcta que su entrevistador espera. El costo de tiempo y el costo de espacio dependen del número máximo en la matriz de entrada. Para entrada de matriz int de 32 bits, el costo de espacio máximo es de 4 * 125M Bytes, el costo de tiempo es de 5 * Billion.

public class TopNumber { public static void main(String[] args) { final int input[] = {2389,8922,3382,6982,5231,8934 ,4322,7922,6892,5224,4829,3829 ,6892,6872,4682,6723,8923,3492}; //One int(4 bytes) hold 32 = 2^5 value, //About 4 * 125M Bytes //int sort[] = new int[1 << (32 - 5)]; //Allocate small array for local test int sort[] = new int[1000]; //Set all bit to 0 for(int index = 0; index < sort.length; index++){ sort[index] = 0; } for(int number : input){ sort[number >>> 5] |= (1 << (number % 32)); } int topNum = 0; outer: for(int index = sort.length - 1; index >= 0; index--){ if(0 != sort[index]){ for(int bit = 31; bit >= 0; bit--){ if(0 != (sort[index] & (1 << bit))){ System.out.println((index << 5) + bit); topNum++; if(topNum >= 3){ break outer; } } } } } } }

Este código es para encontrar N números más grandes en una matriz sin clasificar .

#include <iostream> using namespace std; #define Array_Size 5 // No Of Largest Numbers To Find #define BILLION 10000000000 void findLargest(int max[], int array[]); int checkDup(int temp, int max[]); int main() { int array[BILLION] // contains data int i=0, temp; int max[Array_Size]; findLargest(max,array); cout<< "The "<< Array_Size<< " largest numbers in the array are: /n"; for(i=0; i< Array_Size; i++) cout<< max[i] << endl; return 0; } void findLargest(int max[], int array[]) { int i,temp,res; for(int k=0; k< Array_Size; k++) { i=0; while(i < BILLION) { for(int j=0; j< Array_Size ; j++) { temp = array[i]; res= checkDup(temp,max); if(res == 0 && max[j] < temp) max[j] = temp; } i++; } } } int checkDup(int temp, int max[]) { for(int i=0; i<N_O_L_N_T_F; i++) { if(max[i] == temp) return -1; } return 0; }

Este podría no ser el eficiente, pero hace el trabajo.

Espero que esto ayude

He escrito una solución simple en Python en caso de que alguien esté interesado. Utiliza el bisectmódulo y una lista de devolución temporal que mantiene ordenada. Esto es similar a una implementación de cola de prioridad.

import bisect def kLargest(A, k): ''''''returns list of k largest integers in A'''''' ret = [] for i, a in enumerate(A): # For first k elements, simply construct sorted temp list # It is treated similarly to a priority queue if i < k: bisect.insort(ret, a) # properly inserts a into sorted list ret # Iterate over rest of array # Replace and update return array when more optimal element is found else: if a > ret[0]: del ret[0] # pop min element off queue bisect.insort(ret, a) # properly inserts a into sorted list ret return ret

Uso con 100,000,000 elementos y la entrada de caso más desfavorable que es una lista ordenada:

>>> from so import kLargest >>> kLargest(range(100000000), 100) [99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907, 99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915, 99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923, 99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931, 99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939, 99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947, 99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955, 99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963, 99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971, 99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979, 99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987, 99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995, 99999996, 99999997, 99999998, 99999999]

Tomó aproximadamente 40 segundos calcular esto para 100,000,000 elementos, así que tengo miedo de hacerlo por 1 billón. Sin embargo, para ser justos, le estaba dando el peor de los casos (irónicamente una matriz que ya está ordenada)

Puedes hacerlo a O(n)tiempo. Simplemente recorra la lista y realice un seguimiento de los 100 números más grandes que haya visto en un momento dado y el valor mínimo en ese grupo. Cuando encuentre un número nuevo más grande, el más pequeño de sus diez, entonces reemplácelo y actualice su nuevo valor mínimo de 100 (puede tomar un tiempo constante de 100 para determinar esto cada vez que lo haga, pero esto no afecta el análisis general) ).

Sé que esto podría enterrarse, pero aquí está mi idea de una variación en a radix MSD.

pseudo-code:

//billion is the array of 1 billion numbers int[] billion = getMyBillionNumbers(); //this assumes these are 32-bit integers and we are using hex digits int[][] mynums = int[8][16]; for number in billion putInTop100Array(number) function putInTop100Array(number){ //basically if we got past all the digits successfully if(number == null) return true; msdIdx = getMsdIdx(number); msd = getMsd(number); //check if the idx above where we are is already full if(mynums[msdIdx][msd+1] > 99) { return false; } else if(putInTop100Array(removeMSD(number)){ mynums[msdIdx][msd]++; //we''ve found 100 digits here, no need to keep looking below where we are if(mynums[msdIdx][msd] > 99){ for(int i = 0; i < mds; i++){ //making it 101 just so we can tell the difference //between numbers where we actually found 101, and //where we just set it mynums[msdIdx][i] = 101; } } return true; } return false; }

La función getMsdIdx(int num)devolvería el índice del dígito más significativo (distinto de cero). La función getMsd(int num)devolvería el dígito más significativo. La función removeMSD(int num)eliminaría el dígito más significativo de un número y devolvería el número (o devolvería el valor nulo si no quedaba nada después de eliminar el dígito más significativo).

Una vez hecho esto, todo lo que queda es atravesar mynumspara capturar los 100 dígitos principales. Esto sería algo como:

int[] nums = int[100]; int idx = 0; for(int i = 7; i >= 0; i--){ int timesAdded = 0; for(int j = 16; j >=0 && timesAdded < 100; j--){ for(int k = mynums[i][j]; k > 0; k--){ nums[idx] += j; timesAdded++; idx++; } } }

Debo tener en cuenta que aunque lo anterior parece que tiene una complejidad de tiempo alta, en realidad solo existirá O(7*100).

Una explicación rápida de lo que trata de hacer: Esencialmente, este sistema está tratando de usar cada dígito en una matriz 2d según el índice del dígito en el número y el valor del dígito. Los utiliza como índices para realizar un seguimiento de cuántos números de ese valor se han insertado en la matriz. Cuando se ha alcanzado 100, cierra todas las "ramas inferiores".

El tiempo de este algoritmo es algo así O(billion*log(16)*7)+O(100). Podría estar equivocado sobre eso. También es muy probable que esto necesite depuración ya que es un poco complejo y lo escribí de la cabeza.

EDIT: Downvotes sin explicación no son útiles. Si crees que esta respuesta es incorrecta, por favor deja un comentario por qué. Bastante seguro de que incluso te dice que lo hagas cuando votas a la baja.

Although in this question we should search for top 100 numbers, I will generalize things and write x. Still, I will treat x as constant value.

Algoritmo Mayor x elementos de n:

Voy a llamar a la lista de valores de retorno. Es un conjunto de elementos x (en mi opinión, que debería estar vinculado a la lista)

Los primeros x elementos se toman de la agrupación "como vienen" y se clasifican en la LISTA (esto se hace en tiempo constante, ya que x se trata como constante - tiempo O (x log (x)))
Para cada elemento que viene a continuación, verificamos si es más grande que el elemento más pequeño en la LISTA y si es que sacamos el más pequeño e insertamos el elemento actual en la LISTA. Dado que está en la lista ordenada, cada elemento debe encontrar su lugar en el tiempo logarítmico (búsqueda binaria) y, dado que está ordenada, la inserción de la lista no es un problema. Cada paso también se realiza en tiempo constante (tiempo O (log (x))).

Entonces, ¿cuál es el peor de los casos?

x log (x) + (nx) (log (x) +1) = nlog (x) + n - x

Entonces ese es O (n) tiempo para el peor de los casos.El +1 es la comprobación si el número es mayor que el más pequeño en la LISTA El tiempo esperado para el caso promedio dependerá de la distribución matemática de esos n elementos.

Posibles mejoras

Este algoritmo puede mejorarse ligeramente en el peor de los casos, pero IMHO (no puedo probar esta afirmación) que degradará el comportamiento promedio. El comportamiento asintótico será el mismo.

La mejora en este algoritmo será que no verificaremos si el elemento es mayor que el más pequeño. Para cada elemento intentaremos insertarlo y si es más pequeño que el más pequeño, lo ignoraremos. Aunque eso suena absurdo si consideramos solo el peor de los casos, tendremos

x log (x) + (nx) log (x) = nlog (x)

operaciones

Para este caso de uso no veo más mejoras. Sin embargo, debe preguntarse: ¿qué sucede si tengo que hacer esto más que log (n) veces y para diferentes x-es? Obviamente, ordenaríamos esa matriz en O (n log (n)) y tomaríamos nuestro elemento x cuando lo necesitemos.

Time ~ O(100 * N) Space ~ O(100 + N)

Crear una lista vacía de 100 espacios vacíos
Para cada número en la lista de entrada:
- Si el número es más pequeño que el primero, salta
- De lo contrario reemplazarlo con este número.
- Luego, presione el número a través del intercambio adyacente; hasta que sea más pequeño que el siguiente
Devolver la lista

Nota: si es así log(input-list.size) + c < 100, entonces la forma óptima es ordenar la lista de entrada, luego dividir los primeros 100 elementos.