algorithm - tiene - ejemplos de billones con letra y numero

Encontrar los cien números más grandes en un archivo de mil millones

Question

Fui a una entrevista hoy y me hicieron esta pregunta:

Supongamos que tiene mil millones de enteros que no están ordenados en un archivo de disco. ¿Cómo determinarías los cientos de números más grandes?

Ni siquiera estoy seguro de dónde comenzaría esta pregunta. ¿Cuál es el proceso más eficiente a seguir para obtener el resultado correcto? ¿Necesito revisar el archivo del disco cientos de veces tomando el número más alto que aún no figura en mi lista, o hay una forma mejor?

Answer 1

1. Suponiendo que 1 bill + 100ion numbers encajen en la memoria, el mejor algoritmo de ordenamiento es el tipo de montón. formar un montón y obtener los primeros 100 números. complejidad o (nlogn + 100 (para buscar los primeros 100 números))

   mejorando la solución

   divida la implementación en dos (por lo tanto, la inserción es menos compleja) y mientras recupera los primeros 100 elementos, haga un algoritmo imperial de fusión.

Answer 2

Aquí está mi algoritmo inicial:

create array of size 100 [0..99].
read first 100 numbers and put into array.
sort array in ascending order.
while more numbers in file:
    get next number N.
    if N > array[0]:
        if N > array[99]:
            shift array[1..99] to array[0..98].
            set array[99] to N.
        else
            find, using binary search, first index i where N <= array[i].
            shift array[1..i-1] to array[0..i-2].
            set array[i-1] to N.
        endif
    endif
endwhile

Esto tiene la ventaja (muy leve) de que no hay un orden O (n ^ 2) para los primeros 100 elementos, solo un orden O (n log n) y que identifica muy rápidamente y descarta aquellos que son demasiado pequeños. También utiliza una búsqueda binaria (7 comparaciones máximas) para encontrar el punto de inserción correcto en lugar de 50 (en promedio) para una búsqueda lineal simplista (no es que sugiera que otra persona haya ofrecido una solución de este tipo, solo que puede impresionar al entrevistador). )

Incluso puede obtener puntos de bonificación por sugerir el uso de operaciones de shift optimizadas como memcpy en C siempre que pueda estar seguro de que la superposición no es un problema.

Otra posibilidad que puede considerar es mantener tres listas (de hasta 100 enteros cada una):

read first hundred numbers into array 1 and sort them descending.
while more numbers:
    read up to next hundred numbers into array 2 and sort them descending.
    merge-sort lists 1 and 2 into list 3 (only first (largest) 100 numbers).
    if more numbers:
        read up to next hundred numbers into array 2 and sort them descending.
        merge-sort lists 3 and 2 into list 1 (only first (largest) 100 numbers).
    else
        copy list 3 to list 1.
    endif
endwhile

No estoy seguro, pero eso puede terminar siendo más eficiente que el continuo barajado.

El merge-sort es una selección simple en la línea de (para las listas de clasificación por fusión 1 y 2 en 3):

list3.clear()
while list3.size() < 100:
    while list1.peek() >= list2.peek():
        list3.add(list1.pop())
    endwhile
    while list2.peek() >= list1.peek():
        list3.add(list2.pop())
    endwhile
endwhile

En pocas palabras, sacando los 100 mejores valores de la lista combinada en virtud del hecho de que ya están ordenados en orden descendente. No he revisado en detalle si eso sería más eficiente, solo lo estoy ofreciendo como una posibilidad.

Sospecho que los entrevistadores quedarán impresionados con el potencial de pensar "de fábrica" ​​y con el hecho de que usted indicó que debería evaluarse por su desempeño.

Como con la mayoría de las entrevistas, la habilidad técnica es una de las cosas que están viendo.

Answer 3

Aquí hay otra solución (más o menos un año después, ¡no lo lamento!) Basada en la segunda provista por @paxdiablo. La idea básica es que deberías leer otros números k solo si son mayores que el mínimo que ya tienes y esa clasificación no es realmente necesaria:

// your variables
n = 100
k = a number > n and << 1 billion
create array1[n], array2[k]

read first n numbers into array2
find minimum and maximum of array2 
while more numbers:
  if number > maximum:
    store in array1
    if array1 is full: // I don''t need contents of array2 anymore
       array2 = array1
       array1 = []
  else if number > minimum:
    store in array2
    if array2 is full:
       x = n - array1.count()
       find the x largest numbers of array2 and discard the rest
       find minimum and maximum of array2
  else:
    discard the number
endwhile

// Finally
x = n - array1.count()
find the x largest numbers of array2 and discard the rest
return merge array1 and array2 

El paso crítico es la función para encontrar los números x más grandes en array2. Pero puede usar el hecho de que conoce el mínimo y el máximo para acelerar la función y encontrar los mayores números x en array2.

En realidad, hay muchas optimizaciones posibles, ya que realmente no necesita clasificarlas, solo necesita los x números más grandes.

Además, si k es lo suficientemente grande y tiene suficiente memoria, incluso podría convertirlo en un algoritmo recursivo para encontrar los n números más grandes.

Finalmente, si los números ya están ordenados (en cualquier orden), el algoritmo es O (n).

Obviamente, esto es solo teóricamente porque en la práctica usaría algoritmos de clasificación estándar y el cuello de botella probablemente sería el IO.

Answer 4

Aquí hay un código python que implementa el algoritmo sugerido por ferdinand beyer arriba. esencialmente es un montón, la única diferencia es que la eliminación se ha fusionado con la operación de inserción

import random
import math

class myds:
""" implement a heap to find k greatest numbers out of all that are provided"""
k = 0
getnext = None
heap = []

def __init__(self, k, getnext ):
    """ k is the number of integers to return, getnext is a function that is called to get the next number, it returns a string to signal end of stream """
    assert k>0
    self.k = k
    self.getnext = getnext


def housekeeping_bubbleup(self, index):
    if index == 0:
        return()

    parent_index = int(math.floor((index-1)/2))
    if self.heap[parent_index] > self.heap[index]:
        self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
    self.housekeeping_bubbleup(parent_index)
    return()

def insertonly_level2(self, n):
    self.heap.append(n)
    #pdb.set_trace()
    self.housekeeping_bubbleup(len(self.heap)-1)

def insertonly_level1(self, n):
    """ runs first k times only, can be as slow as i want """
    if len(self.heap) == 0:
        self.heap.append(n)
        return()
    elif n > self.heap[0]:
        self.insertonly_level2(n)
    else:
        return()

def housekeeping_bubbledown(self, index, length):
    child_index_l = 2*index+1
    child_index_r = 2*index+2
    child_index = None
    if child_index_l >= length and child_index_r >= length: # No child
        return()
    elif child_index_r >= length: #only left child
        if self.heap[child_index_l] < self.heap[index]: # If the child is smaller
            child_index = child_index_l
        else:
            return()
    else: #both child
        if self.heap[ child_index_r] < self.heap[ child_index_l]:
            child_index = child_index_r
        else:
            child_index = child_index_l

    self.heap[index], self.heap[ child_index] = self.heap[child_index], self.heap[index]
    self.housekeeping_bubbledown(child_index, length)
    return()

def insertdelete_level1(self, n):
    self.heap[0] = n
    self.housekeeping_bubbledown(0, len(self.heap))
    return()

def insert_to_myds(self,  n ):
    if len(self.heap) < self.k:
        self.insertonly_level1(n)
    elif n > self.heap[0]:
        #pdb.set_trace()
        self.insertdelete_level1(n)
    else:
        return()

def run(self ):
    for n in self.getnext:
        self.insert_to_myds(n)
        print(self.heap)
        #            import pdb; pdb.set_trace()
    return(self.heap)

def createinput(n):
    input_arr = range(n)
    random.shuffle(input_arr)
    f = file(''input'', ''w'')
    for value in input_arr:
        f.write(str(value))
        f.write(''/n'')

input_arr = []
with open(''input'') as f:
    input_arr = [int(x) for x in f]
myds_object = myds(4, iter(input_arr))
output = myds_object.run()
print output

Answer 5

Atravesaría la lista en orden. A medida que avanzo, agrego elementos a un conjunto (o multiset dependiendo de los duplicados). Cuando el conjunto llegó a 100, solo insertaba si el valor era mayor que el mínimo en el conjunto (O (log m)). Luego borra el min.

Llamando al número de valores en la lista ny al número de valores para encontrar m:

esto es O (n * log m)

Answer 6

Crea una matriz de 100 números siendo todos -2 ^ 31.

Compruebe si el primer número que lee del disco es mayor que el primero de la lista. Si se trata de copiar el array, baje 1 índice y actualícelo al nuevo número. Si no, marque el siguiente en el 100 y así sucesivamente.

Cuando hayas terminado de leer los mil millones de dígitos, deberías tener los 100 más altos en la matriz.

Trabajo hecho.

Answer 7

Creo que alguien debería haber mencionado una cola de prioridad por ahora. Solo necesita mantener los 100 mejores números actuales, saber cuál es el más bajo y poder reemplazarlo con un número mayor. Eso es lo que hace una cola de prioridad para usted: algunas implementaciones pueden clasificar la lista, pero no es necesaria.

Answer 8

Creo que la manera más rápida de hacer esto es usando un mapa de bits muy grande para registrar qué números están presentes. Para representar un entero de 32 bits, esto necesitaría ser de 2 ^ 32/8 bytes, que es aproximadamente == 536MB. Escanee los enteros simplemente configurando el bit correspondiente en el mapa de bits. Luego busque las 100 entradas más altas.

NOTA: Esto encuentra los 100 números más altos, no las 100 instancias más altas de un número si ve la diferencia.

¡Este tipo de enfoque se discute en el muy buen libro Programming Pearls que su entrevistador puede haber leído!

Answer 9

Hay muchos enfoques inteligentes (como las soluciones de cola de prioridad), pero una de las cosas más simples que puede hacer también puede ser rápida y eficiente.

Si desea la parte superior k de n , considere:

allocate an array of k ints
while more input
  perform insertion sort of next value into the array

Esto puede sonar absurdamente simplista. Puede esperar que sea O(n^2) , pero en realidad solo es O(k*n) , y si k es mucho más pequeño que n (como se postula en el enunciado del problema), se aproxima a O(n) .

Podría argumentar que el factor constante es demasiado alto porque hacer un promedio de k/2 comparaciones y movimientos por entrada es mucho. Pero la mayoría de los valores serán rechazados trivialmente en la primera comparación contra el k ésimo valor más grande visto hasta ahora. Si tiene mil millones de entradas, solo una pequeña fracción probablemente sea más grande que la centésima hasta el momento.

( Podría interpretar una entrada de peor caso donde cada valor es más grande que su predecesor, por lo que se requieren k comparaciones y movimientos para cada entrada. Pero eso es esencialmente una entrada ordenada, y el enunciado del problema dice que la entrada no está ordenada).

Incluso la mejora de la búsqueda binaria (para encontrar el punto de inserción) solo reduce las comparaciones al ceil(log_2(k)) , y a menos que sea especial una comparación adicional en contra de la k -és-tan-lejos, es mucho menos probable que obtener el rechazo trivial de la gran mayoría de las entradas. Y no hace nada para reducir el número de movimientos que necesita. Teniendo en cuenta los esquemas de caché y la predicción de ramas, hacer 7 comparaciones no consecutivas y luego 50 movimientos consecutivos no parece ser significativamente más rápido que hacer 50 comparaciones y movimientos consecutivos. Es por eso que muchos tipos de sistemas abandonan Quicksort a favor de la ordenación de inserción para tamaños pequeños.

Además, tenga en cuenta que esto requiere casi ninguna memoria adicional y que el algoritmo es extremadamente compatible con la caché (lo que puede o no ser cierto para una cola de prioridad o de almacenamiento dinámico), y es trivial escribir sin errores.

El proceso de lectura del archivo es probablemente el mayor cuello de botella, por lo que es probable que el rendimiento real sea mayor haciendo una simple solución para la selección, puede enfocar sus esfuerzos en encontrar una buena estrategia de almacenamiento en búfer para minimizar la E / S.

Si k puede ser arbitrariamente grande, acercándose a n , entonces tiene sentido considerar una cola de prioridad u otra estructura de datos más inteligente. Otra opción sería dividir la entrada en múltiples fragmentos, ordenarlos en paralelo y fusionarlos.

Answer 10

La velocidad del algoritmo de procesamiento es absolutamente irrelevante (a menos que sea completamente tonto).

El cuello de botella aquí es I / O (se especifica que están en el disco). Así que asegúrate de trabajar con buffers grandes.

Answer 11

Mantenga una matriz fija de 100 enteros. Inicialízalos en un Int.MinValue. Cuando esté leyendo, desde mil millones de enteros, compárelos con los números en la primera celda de la matriz (índice 0). Si es más grande, luego pasa al siguiente. De nuevo, si es más grande, luego suba hasta que llegue al final o un valor menor. Luego, guarde el valor en el índice y cambie todos los valores en las celdas anteriores, una celda hacia abajo ... haga esto y encontrará 100 enteros máximos.

Answer 12

Obviamente, los entrevistadores quieren que señale dos hechos clave:

• No puede leer toda la lista de enteros en la memoria, ya que es demasiado grande. Entonces deberás leerlo uno por uno.
• Necesita una estructura de datos eficiente para contener los 100 elementos más grandes. Esta estructura de datos debe admitir las siguientes operaciones:
  • Get-Size : obtener la cantidad de valores en el contenedor.
  • Find-Min : Obtenga el valor más pequeño.
  • Delete-Min : Delete-Min el valor más pequeño para reemplazarlo con un nuevo valor más grande.
  • Insert : inserta otro elemento en el contenedor.

Al evaluar los requisitos para la estructura de datos, un profesor de informática esperaría que recomendara utilizar un Heap (Min-Heap), ya que está diseñado para admitir exactamente las operaciones que necesitamos aquí.

Por ejemplo, para montones de Fibonacci , las operaciones Get-Size , Find-Min e Insert all son O(1) y Delete-Min es O(log n) (con n <= 100 en este caso).

En la práctica, puede usar una cola de prioridad de la biblioteca estándar de su idioma favorito (por ejemplo, priority_queue de #include <queue> en C ++) que generalmente se implementa con un montón.

Answer 13

Si encuentra la estadística de orden 100 usando clasificación rápida, funcionará en promedio O (mil millones). Pero dudo que con tales números y debido al acceso aleatorio necesario para este enfoque sea más rápido que O (mil millones log (100)).

Answer 14

Vas a tener que verificar cada número, no hay forma de evitarlo.

Solo como una ligera mejora en las soluciones ofrecidas,

Dada una lista de 100 números:

9595
8505
...
234
1

Verificará si el nuevo valor encontrado es> valor mínimo de nuestra matriz, si es así, insértelo. Sin embargo, hacer una búsqueda de abajo hacia arriba puede ser bastante costoso, y puede considerar tomar un enfoque de dividir y conquistar, por ejemplo, evaluando el artículo número 50 en el conjunto y haciendo una comparación, entonces usted sabe si el valor debe insertarse en los primeros 50 elementos, o el inferior 50. Puede repetir este proceso para una búsqueda mucho más rápida ya que hemos eliminado el 50% de nuestro espacio de búsqueda.

También considere el tipo de datos de los enteros. Si son enteros de 32 bits y está en un sistema de 64 bits, es posible que pueda realizar un manejo inteligente de la memoria y operaciones bit a bit para manejar dos números en el disco a la vez si están continuamente en la memoria.