examples - algorithms book

Recuperando los 100 primeros números de cien millones de números

Question

A uno de mis amigos se le ha preguntado con una pregunta.

Recuperando los 100 primeros números máximos de cien millones de números

en una reciente entrevista de trabajo. ¿Tienes alguna idea para encontrar una manera eficiente de resolverlo?

Answer 1

¡@darius en realidad puede ser mejorado!
Al "podar" o aplazar la operación de reemplazo de pila según sea necesario

Supongamos que tenemos un = 1000 en la parte superior del montón
Tiene c, b hermanos
Sabemos que c, b> 1000

      a=1000
  +-----|-----+
 b>a         c>a




We now read the next number x=1035
Since x>a we should discard a.
Instead we store (x=1035, a=1000) at the root
We do not (yet) bubble down the new value of 1035 
Note that we still know that b,c<a but possibly b,c>x
Now, we get the next number y
when y<a<x then obviously we can discard it 

when y>x>a then we replace x with y (the root now has (y, a=1000))
=> we saved log(m) steps here, since x will never have to bubble down

when a>y>x then we need to bubble down y recursively as required

Worst run time is still O(n log m) 
But average run time i think might be O(n log log m) or something
In any case, it is obviously a faster implementation

Answer 2

Almaceno los primeros 100 números en Max-Montón de tamaño 100.

• En el último nivel, hago un seguimiento del número mínimo y el nuevo número que inserto y verifico con el número mínimo. Si el número entrante es candidato para los 100 primeros.

  - Otra vez llamo a reheapify, así que siempre tengo el máximo de top 100.

  Entonces su complejidad es O (nlogn).

Answer 3

Ejecútelos a través de un min-heap de tamaño 100: para cada número de entrada k , reemplace el valor actual de min m como max(k, m) . Después, el montón contiene las 100 entradas más grandes.

Un motor de búsqueda como Lucene puede usar este método, con refinamientos, para elegir las respuestas de búsqueda más relevantes.

Edit: Falla la entrevista. Me fallaron los detalles dos veces (después de haber hecho esto antes, en producción). Aquí está el código para comprobarlo; es casi lo mismo que el estándar heapq.nlargest() Python:

import heapq

def funnel(n, numbers):
    if n == 0: return []
    heap = numbers[:n]
    heapq.heapify(heap)
    for k in numbers[n:]:
        if heap[0] < k:
            heapq.heapreplace(heap, k)
    return heap

>>> funnel(4, [3,1,4,1,5,9,2,6,5,3,5,8])
[5, 8, 6, 9]

Answer 4

Fusione en lotes de 100, luego solo mantenga los 100 mejores.

Por cierto, puede escalar esto en todo tipo de direcciones, incluso al mismo tiempo.

Answer 5

Heapify la matriz en O (n). Luego saca los 100 mejores elementos.

Answer 6

No hay razón para ordenar la lista completa. Esto debería ser factible en O (n) tiempo. En pseudocódigo:

List top = new List

for each num in entireList
    for i = 0 to top.Length
        if num > top[i] then
            top.InsertBefore(num, i)
            if top.Length > 100 then
                top.Remove(top.Length - 1)
            end if
            exit for
        else
            if i = top.Length - 1 and i < 100 then
                top.Add(num)
            end if
        end if
    next
next

Answer 7

Ok, aquí hay una respuesta realmente estúpida, pero es válida:

• Cargar todos los 100 millones de entradas en una matriz
• Llame a alguna implementación de orden rápida en él
• Tome los últimos 100 elementos (ordena ascendente), o los primeros 100 si puede ordenar descendente.

Razonamiento:

• No hay un contexto en la pregunta, por lo que se puede argumentar la eficiencia. ¿Qué es eficiente? ¿Tiempo de computadora o tiempo de programador?
• Este método es implementable muy rápido.
• 100 millones de entradas: los números son solo un par de cientos de mb, por lo que cualquier trabajo decente puede ejecutar eso.

Es una solución aceptable para algún tipo de operación única. Apestaría corriendo x veces por segundo o algo así. Pero entonces, necesitamos más contexto, como mclientk también tenía con su simple declaración SQL, suponiendo que 100 millones de números no existan en la memoria es una pregunta factible, porque ... pueden provenir de una base de datos y la mayoría de las veces, cuando hablen. sobre los números de negocios relevantes.

Como tal, la pregunta es realmente difícil de responder: primero se debe definir la eficiencia.

Answer 8

Por TOP 100 , ¿te refieres a 100 más grande? Si es así:

SELECT TOP 100 Number FROM RidiculouslyLargeTable ORDER BY Number DESC

Asegúrese de decirle al entrevistador que asume que la tabla está indexada correctamente.

Answer 9

Primera iteración:

Quicksort, toma el top 100. O (n log n). Simple, fácil de codificar. Muy evidente.

¿Mejor? Estamos trabajando con números, haga una clasificación de radix (tiempo lineal) y tome el top 100. Espero que esto sea lo que el entrevistador está buscando.

¿Alguna otra consideración? Bueno, un millón de números no es una gran cantidad de memoria, pero si desea minimizar la memoria, puede mantener un máximo de 100 números encontrados hasta el momento y luego escanear los números. ¿Cuál sería la mejor manera?

Algunos han mencionado un montón, pero una solución un poco mejor podría ser una lista doblemente enlazada, donde mantienes el puntero al mínimo de los 100 principales encontrados hasta ahora. Si encuentra un número a que es más grande que el actual más pequeño en la lista, en comparación con el siguiente elemento, y mueva el número de al lado del actual hasta que encuentre un lugar para el nuevo número. (Esto es básicamente un montón especializado para la situación). Con algunos ajustes (si el número es mayor que el mínimo actual, compare con el máximo actual para ver en qué dirección ir a la lista para encontrar el punto de inserción) esto sería relativamente efectivo y solo tomaría como 1.5k de memoria.

Answer 10

Si los datos ya están en una matriz que puede modificar, puede utilizar una variante del algoritmo de selección de Hoare, que es (a su vez) una variante de Quicksort.

La idea básica es bastante simple. En Quicksort, divide la matriz en dos partes, una de los elementos más grandes que el pivote y la otra de los elementos más pequeños que el pivote. Luego ordenes recursivamente cada partición.

En el algoritmo de selección, realice el paso de partición exactamente igual que antes, pero en lugar de clasificar recursivamente ambas particiones, mire qué partición contiene los elementos que desea y seleccione SÓLO en esa partición de forma recursiva. Por ejemplo, suponiendo que su partición de 100 millones de elementos se reduzca casi a la mitad, las primeras iteraciones que va a ver solo en la partición superior.

Eventualmente, es probable que llegue a un punto en el que la parte que desea "une" dos particiones; por ejemplo, tiene una partición de ~ 150 números, y cuando particiona, termina con dos partes de ~ 75 cada una. En ese momento, solo cambia un detalle menor: en lugar de rechazar una partición y continuar trabajando solo la otra, acepta la partición superior de 75 elementos y luego continúa buscando los 25 primeros en la partición inferior.

Si estuviera haciendo esto en C ++, podría hacerlo con std::nth_element (que normalmente se implementará aproximadamente como se describe anteriormente). En promedio, esto tiene una complejidad lineal, que creo que es tan buena como se puede esperar (a falta de un orden preexistente, no veo ninguna forma de encontrar los elementos N superiores sin mirar todos los elementos).

Si los datos aún no están en una matriz, y usted (por ejemplo) está leyendo los datos de un archivo, por lo general, desea usar un montón. Básicamente, lee un elemento, lo inserta en el montón, y si el montón es más grande que su objetivo (100 elementos, en este caso), elimina uno y vuelve a heapificar.

Lo que probablemente no sea tan obvio (pero en realidad es cierto) es que normalmente no desea utilizar un máximo de pila para esta tarea. A primera vista, parece bastante obvio: si desea obtener el máximo de artículos, debe usar un montón máximo.

Sin embargo, es más sencillo pensar en términos de los elementos que está "eliminando" del montón. Un montón máximo le permite encontrar rápidamente el elemento más grande del montón. Sin embargo, no está optimizado para encontrar el elemento más pequeño en el montón.

En este caso, estamos interesados ​​principalmente en el elemento más pequeño del montón. En particular, cuando leemos cada elemento del archivo, queremos compararlo con el elemento más pequeño del montón. Si (y solo si) es más grande que el elemento más pequeño del montón, queremos reemplazar ese elemento más pequeño actualmente en el montón con el nuevo elemento. Dado que es (por definición) más grande que el elemento existente, entonces tendremos que analizarlo en la posición correcta en el montón.

Pero tenga en cuenta que si los elementos del archivo se ordenan de forma aleatoria, a medida que leemos el archivo, alcanzamos rápidamente un punto en el que la mayoría de los elementos que leemos en el archivo serán más pequeños que el elemento más pequeño de nuestro montón. Ya que tenemos fácil acceso al elemento más pequeño del montón, es bastante rápido y fácil hacer esa comparación, y para los elementos más pequeños nunca se insertan en el montón.

Answer 11

Supongamos que mylist es una lista de cientos de millones de datos. para que podamos ordenar la lista y tomar los últimos cientos de datos de mylist.

mylist.sort ()

mylist [-100:]

Segunda forma:

importación montón

heapq.nlargest (100, mylist)

Answer 12

int numbers[100000000000] = {...};
int result[100] = {0};
for( int i = 0 ; i < 100000000000 ; i++ )
{
    for( int j = 0 ; j < 100 ; j++ )
    {
         if( numbers[i] > result[j] )
         {
              if( j < 99 )
              {
                  memcpy(result+j+1, result+j, (100-j)*sizeof(int));
              }
              result[j] = numbers[i];
              break;
         }
    }
}