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

Question

Proporcione ejemplos de código en el idioma de su elección.

Actualización: No hay restricciones establecidas en el almacenamiento externo.

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

Answer 1

Sorting a million 32-bit integers in 2MB of RAM using Python by Guido van Rossum

Answer 2

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

Debe ordenarlos usando algún algoritmo que use almacenamiento externo. Mergesort, por ejemplo.

Answer 3

Divida el problema en pedazos lo suficientemente pequeños como para caber en la memoria disponible, luego use merge sort para combinarlos.

Answer 4

Debe proporcionar más información. ¿Qué almacenamiento adicional está disponible? ¿Dónde se supone que almacenar 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 y envíelos a un archivo. 2. Cargue la segunda mitad de datos en la memoria (2MB), oriéntelos por cualquier método, guárdelos en la memoria. 3. utilice el algoritmo de combinación para fusionar las dos mitades ordenadas y envíe el conjunto completo de datos ordenados a un archivo.

Answer 5

Como las personas mencionadas arriba, escriba int de 32bit 4 MB.

Para colocar tanto "Número" como sea posible en la menor cantidad de espacio posible usando los tipos int, short y char en C++. Podrías ser hábil (pero tener un código sucio extraño) al hacer varios tipos de casting para rellenar cosas en todas partes.

Aquí está fuera del borde de mi asiento.

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

cualquier cosa que es menor que 2^16 (256 - 65535) y> 2^8 se almacena como un corto (tipo de datos de 2 bytes)

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

Desea especificar dónde comienza y finaliza la sección de caracteres, dónde comienza y finaliza la sección corta, y dónde comienza y finaliza la sección int.

Answer 6

Este wikipedia article on External Sorting tiene alguna información útil.

Answer 7

Dual tournament sort with polyphased merge

#!/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 

Answer 8

Ningún ejemplo, pero Bucket Sort tiene una complejidad relativamente baja y es bastante fácil de implementar

Answer 9

• Um, almacenarlas todas en un archivo.
• Memoria mapear el archivo (dijiste que solo había 2M de RAM, supongamos que el espacio de direcciones es lo suficientemente grande como para mapear la memoria de un archivo).
• ¡Ordénelos utilizando la tienda de respaldo de archivos como si ahora fuera una memoria real!

Answer 10

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

Cargue la mitad de los números en la memoria. Heap los clasifica en su lugar y escribe la salida en un archivo. Repita para la otra mitad. Utilice la ordenación externa (básicamente una clasificación de combinación que tenga en cuenta el archivo E/S) para fusionar los dos archivos.

Aparte: Hacer una pila de clasificación más rápido en la cara de almacenamiento externo lenta:

• inicio la construcción de la pila antes de que todos los números enteros están en la memoria.

• empezar a poner los números enteros de nuevo en el archivo de salida, mientras que la pila de clasificación aún está extrayendo elementos