Extern sortering är en teknik som används för att hantera stora datamängder som inte passar in i huvudminnet. En viktig aspekt av extern sortering beräknar sammanslagningskostnaden, vilket hjälper till att bestämma effektiviteten i sorteringsprocessen. Denna guide ger en steg-för-steg-strategi för att förstå och beräkna sammanslagningskostnader i extern sortering.

Förstå Extern Sortering

Extern sortering innebär att dela data i hanterbara bitar, sortera varje bit individuellt och sedan slå samman dessa sorterade bitar i en enda sorterad fil. Sammanslagningsprocessen kan utföras i flera pass, beroende på antalet bitar och tillgängligt minne.

Komponenter av Merge Cost

Sammanslagningskostnaden beror främst på antalet pass och mängden data som behandlas under varje pass. Det påverkas av:

  • Antalet initiala sorterade körningar (kanske)
  • Antalet filer sammanslagna samtidigt (fan-in)
  • Den totala storleken på data

Beräkning av Merge Cost

Den totala sammanslagningskostnaden kan beräknas med hjälp av formeln:

]Merge Cost = Antal pass × Total data som behandlas i varje pass

För att bestämma antalet pass, använd formeln:

]Antalet pass = logga ] fan-in ] (Antalet inledande körningar)]

Om det till exempel finns 16 inledande körningar och systemet kan slå samman 4 filer samtidigt, då:

Antal pass = log]4 16 = 2

Den totala data som behandlas i varje pass motsvarar den totala storleken på alla data som fusioneras under det passet. Sammanfattning över alla pass ger den totala sammanslagningskostnaden.