algorithm - tipos - unsigned short int
¿Cómo clasificaría 1 millón de enteros de 32 bits en 2 MB de RAM? (10)
Por favor, proporcione ejemplos de código en el idioma que elija.
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.
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.
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: haga que la ordenación de pila sea más rápida frente a un almacenamiento externo lento:
Comience a construir el montón antes de que todos los enteros estén en la memoria.
Comience a volver a poner los enteros en el archivo de salida mientras el tipo de ordenamiento sigue extrayendo elementos
Como se menciona arriba, escribe 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.
todo lo que sea menor a 2 ^ 8 (0 - 255) se almacena como un carácter de datos (tipo de datos de 1 byte)
todo lo que sea 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)
Debería especificar dónde comienza y dónde termina la sección char, dónde comienza y termina la sección corta, y dónde comienza y termina la sección int.
Divida el problema en pedazos lo suficientemente pequeños como para caber en la memoria disponible, luego use la combinación de clasificación para combinarlos.
Este artículo de wikipedia sobre clasificación externa contiene información útil.
Necesitas dar 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), oriéntelos por cualquier método y envíelos a un archivo. 2. cargue la segunda mitad de datos en la memoria (2MB), ordene por cualquier método, guárdelo en la memoria. 3. Utilice el algoritmo de fusión para fusionar las dos mitades ordenadas y envíe el conjunto completo de datos ordenados a un archivo.
No hay ningún ejemplo, pero Bucket Sort tiene una complejidad relativamente baja y es bastante fácil de implementar
Tipo de torneos 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, almacenarlos todos en un archivo.
- La memoria mapea 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 usando la tienda de respaldo de archivos como si ahora fuera una memoria real!