Ekstern sortering er en teknikk som brukes til å håndtere store datasett som ikke passer inn i hovedminnet. Et sentralt aspekt av ekstern sortering beregner sammenslåingskostnaden, noe som bidrar til å bestemme effektiviteten av sorteringsprosessen. Denne guiden gir en trinnvis tilnærming til å forstå og beregne sammenslåingskostnader i ekstern sortering.

Forstå ekstern sortering

Ekstern sortering innebærer å dele data i håndterbare deler, sortere hver del individuelt og deretter slå sammen disse sorterte bitene i en enkelt sortert fil. Sammenslåingsprosessen kan utføres i flere passeringer, avhengig av antall biter og tilgjengelig minne.

Komponenter i sammenslåingskostnad

Sammenslåingskostnaden avhenger primært av antall passeringer og mengden data som behandles under hvert pass. Det påvirkes av:

  • Antall første sorterte løp (chunks)
  • Antall filer som er slått sammen samtidig (fan-in)
  • Den totale størrelsen på dataene

Beregner sammenslåingskostnaden

Den totale sammenslåingskostnaden kan beregnes ved hjelp av formelen:

Foldekostnader = Antall passeringer × Totalt data som behandles i hvert pass]

For å bestemme antall passeringer, bruk formelen:

Antall pass = loggfan-in] (Antall første løp)

For eksempel, hvis det er 16 initiale løp og systemet kan slå sammen 4 filer på én gang, så:

Antall pass = logg]4 16 = 2

De samlede dataene som behandles i hvert pass, er lik den totale størrelsen på alle data som slås sammen under det passet. Summing over alle passeringer gir den totale sammenslåingskostnaden.