In domanda 11.5 del libro di Gayle Laakman, Cracking il colloquio tecnico,ordinamento di un file da 20 GB con una corda per linea
"Immaginate di avere un file di 20 GB con una corda per riga. Spiegate come ordinare il file"
La mia reazione iniziale è stata esattamente la soluzione che ha proposto: suddividere il file in blocchi più piccoli (megabyte) leggendo in X mb di dati, ordinandolo e quindi scrivendolo su disco. E alla fine, unisci i file.
Ho deciso di non seguire questo approccio perché l'unione finale implicherebbe il mantenimento di tutti i dati nella memoria principale - e assumiamo che ciò non sia possibile. Se questo è il caso, in che modo esattamente questa soluzione tiene?
Il mio altro approccio si basa sul presupposto che abbiamo uno spazio su disco quasi illimitato, o almeno abbastanza da contenere 2X i dati che abbiamo già. Possiamo leggere in X mb di dati e quindi generare le chiavi di hash per loro - ogni chiave corrispondente a una riga in un file. Continueremo a farlo finché tutti i valori non saranno stati sottoposti a hash. Quindi dobbiamo solo scrivere i valori di quel file nel file originale.
Fatemi sapere cosa ne pensate.
Non capisco la tua proposta di hashing, puoi elaborare? Gli algoritmi hash tipici producono hash con un ordine di ordinamento diverso rispetto agli input. – tripleee