Quando abbiamo un file di dimensioni grandi, lo dividiamo in piccoli, li ordiniamo e quindi li uniamo in un file ordinato di grandi dimensioni.unione multi-way contro unione 2-way
Durante l'unione, è possibile eseguire molti passaggi di unione a 2 vie o unire unione multipla.
Mi chiedo quale approccio è migliore? e perché?
Un'unione multi-way è generalmente migliore. Consideriamo tre file di piccole dimensioni:
a1
a2
a3
e
b1
b2
b3
e infine
c1
c2
c3
Se fate una fusione con a e b, siamo lasciati con (diciamo)
a1
b1
a2
b2
b3
a3
e
c1
c2
c3
Una fusione finale sarebbe creare l'elenco ordinato, meno di notare come in questa fusione finale dobbiamo visitare di nuovo le voci a e b. È questa ri-fusione che è uno spreco nelle fusioni a cascata a due vie.
Ciò che si può fare è invece un'unica unione multipla. Tuttavia, fai attenzione a come lo fai. In particolare, evita il doppio loop ingenuo che analizza ogni cursore per vedere quale ha il valore minimo. Utilizzare invece un heap minimo. Ciò ridurrà la complessità a O(n log n).