Algoritmo per ordinare dieci milioni di numeri interi a 7 cifre in ordine crescente con solo 1,5 Mb di RAM?

Question

Algoritmo per ordinare dieci milioni di numeri interi a 7 cifre in ordine crescente con solo 1,5 Mb di RAM?

#1 da (11 voti)
#2 da (3 voti)
#3 da (0 voti)

6

Given a file containing at most ten million 7-digit integers with no duplicates. What is an efficient way to print these numbers in ascending order using just 1.5MB RAM and reading the data just once? What if duplicates were permitted?

Ho trovato la domanda sopra a google ma id non trova alcuna risposta pertinente. Basato su ricerca / risposte google e sulla mia comprensione Credo che questo possa essere approccio e algoritmo (considera il linguaggio come Java anche se non ha importanza per la maggior parte dei punti) con query specifiche su ciascun punto

Supponendo che un numero intero sia un intero di 4 byte in java. Non penso che la lunghezza (come 7 cifre o 6 cifre) dovrebbe importare qui?
Numero di numeri interi che possono essere accomodati sotto 1.5 MB ram = 1.5 / 4 = 375k (dove 4 rappresenta il numero intero di 4 byte) che risulta essere .3 milioni di interi. Significa che .3 milioni di interi possono essere ordinati in una volta nella memoria di 1,5 MB
Ora ordina i primi 3 milioni di interi in memoria e li scrivi in un file temporaneo.
Scegli un altro lotto di .3 milioni e unisci questo aspetto con il file temporaneo creato nel passaggio 3 e crea un nuovo file temporaneo. Elimina quello al punto 3.
Ripeti il passaggio 4 fino al completamento del processo, ovvero 10 / .3 = 34 volte.

Questo algoritmo è corretto? Se sì, non sono in grado di influenzare qui i duplicati?

java algorithms sorting

posta M Sach 03.09.2018 - 15:59

fonte

3 risposte

3

10 milioni di numeri a 7 cifre senza duplicati ordinati sono: 0, 1, 2, 3, ..., 9.999.999.

Spero di darti un suggerimento per meno di 10 milioni, usando 1,25 MB di memoria e correndo in tempo lineare.

risposta data 03.09.2018 - 16:42

fonte

0

Il tuo algoritmo non può funzionare, perché il file temp diventa più grande ogni volta, e tornerai presto a esaurire la memoria.

Pensa a un approccio in cui dividi il intervallo dei numeri in "bucket" di dimensioni appropriate e assegni un file per bucket.
Quindi leggi un gruppo, assegnali ai rispettivi bucket e aggiungili ai rispettivi file "bucket".
Dopo aver eseguito tutti i numeri, ora hai i file bucket che puoi leggere e ordinare completamente nella memoria (supponendo che tu abbia scelto la dimensione del bucket corretta) e stampare nell'ordine corretto. Soprattutto, puoi essere sicuro che un bucket successivo non contenga un numero che avresti avuto bisogno di stampare adesso.

risposta data 03.09.2018 - 17:30

fonte

Leggi altre domande sui tag java algorithms sorting

Qual è la prassi standard per impedire agli utenti di avere aspettative irragionevoli? Quali metriche usi nel tuo progetto Scrum? [chiuso]

score 11 · Accepted Answer

Direi che potresti usare un campo di bit. Quello è che usi un bit per ogni numero da 0 a 9.999.999. Questo è 1,25 MByte di RAM.

Leggete il file una volta e segnate il bit corrispondente quando viene letto un numero. Quindi nel secondo passaggio si cammina sopra il bitfield e si stampa l'indice su tutte le voci che hanno il bit impostato. Funziona perché sai che non ci sono duplicati. Il massimo di 10.000.000 è solo una conseguenza di ciò. L'algoritmo funziona con qualsiasi numero di numeri.

Per quanto riguarda la domanda, cosa succede se sono consentiti i duplicati, non è chiaro se si debba stampare anche i duplicati o solo i numeri. Ovviamente anche quest'ultimo caso funzionerà, il primo no - ha bisogno di memorizzare ulteriori informazioni.