¿Cómo clasificaría 1 millón de enteros de 32 bits en 2 MB de RAM?

StackOverflow https://stackoverflow.com/questions/134158

Pregunta

Por favor, proporcione ejemplos de código en un idioma de su elección.

Actualizar : No hay restricciones establecidas en el almacenamiento externo.

Ejemplo: los enteros se reciben / envían a través de la red. Hay un espacio suficiente en el disco local para resultados intermedios.

Otros consejos

Divida el problema en partes lo suficientemente pequeñas como para que quepan en la memoria disponible, luego use fusionar clasificación para Combínalos.

1 millón de enteros de 32 bits = 4 MB de memoria.

Debería ordenarlos usando algún algoritmo que use almacenamiento externo. Mergesort, por ejemplo.

Necesitas proporcionar más información. ¿Qué almacenamiento adicional está disponible? ¿Dónde se supone que debes guardar el resultado?

De lo contrario, la respuesta más general: 1. cargue la primera mitad de los datos en la memoria (2MB), ordénelos por cualquier método, envíelos al archivo. 2. cargue la segunda mitad de los datos en la memoria (2MB), ordénelos por cualquier método, manténgalos en la memoria. 3. use el algoritmo de combinación para combinar las dos mitades ordenadas y generar el conjunto de datos ordenados completos en un archivo.

Clasificación de torneo dual con fusión polifásica 

#!/usr/bin/env python
import random
from sort import Pickle, Polyphase


nrecords = 1000000
available_memory = 2000000 # number of bytes
    #NOTE: it doesn't count memory required by Python interpreter 

record_size = 24 # (20 + 4) number of bytes per element in a Python list
heap_size = available_memory / record_size 
p = Polyphase(compare=lambda x,y: cmp(y, x), # descending order
              file_maker=Pickle, 
              verbose=True,
              heap_size=heap_size,
              max_files=4 * (nrecords / heap_size + 1))

# put records
maxel = 1000000000
for _ in xrange(nrecords):
    p.put(random.randrange(maxel))

# get sorted records
last = maxel
for n, el in enumerate(p.get_all()):
    if el > last: # elements must be in descending order
        print "not sorted %d: %d %d" % (n, el ,last)
        break
    last = el

assert nrecords == (n + 1) # check all records read
  • Um, guárdalos todos en un archivo.
  • El mapa de memoria del archivo (usted dijo que solo había 2M de RAM; supongamos que el espacio de direcciones es lo suficientemente grande como para asignar un archivo a la memoria).
  • ¡Ordénelos usando la tienda de respaldo de archivos como si fuera memoria real ahora!

Aquí hay una solución válida y divertida.

Cargue la mitad de los números en la memoria. Heap ordenarlos en su lugar y escribir la salida en un archivo. Repita para la otra mitad. Utilice la ordenación externa (básicamente una ordenación de fusión que toma en cuenta el archivo i / o) para fusionar los dos archivos.

Aparte:   Haga que el almacenamiento dinámico se clasifique más rápido frente al almacenamiento externo lento:

  • Comience a construir el montón antes de que todos los enteros estén en la memoria.

  • Comienza a colocar los enteros de nuevo en el archivo de salida mientras la ordenación del montón sigue extrayendo elementos

Como las personas mencionadas anteriormente mencionan el tipo int de 32 bits 4 MB.

Para ajustar tanto " Número " lo más posible en el menor espacio posible utilizando los tipos int, short y char en C ++. Podrías ser astuto (pero tener un código extraño) haciendo varios tipos de casting para rellenar cosas en todas partes.

Aquí está fuera del borde de mi asiento.

cualquier cosa que sea menor que 2 ^ 8 (0 - 255) se almacena como un char (tipo de datos de 1 byte)

cualquier cosa que sea menor que 2 ^ 16 (256 - 65535) y > 2 ^ 8 se almacena en forma corta (tipo de datos de 2 bytes)

El resto de los valores se pondrían en int. (Tipo de datos de 4 bytes)

Desearía especificar dónde comienza y termina la sección char, dónde comienza y termina la sección corta y dónde comienza y termina la sección int.

No hay ejemplo, pero Bucket Sort tiene una complejidad relativamente baja y es fácil de implementar

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top