Stapsgewijze handleiding voor het berekenen van de kosten van samenvoegen in extern sorteren

Extern sorteren is een techniek die wordt gebruikt om grote datasets te verwerken die niet passen in het hoofdgeheugen. Een belangrijk aspect van externe sorteren is het berekenen van de mergekosten, wat helpt de efficiëntie van het sorteerproces te bepalen. Deze handleiding biedt een stapsgewijze benadering van het begrijpen en berekenen van mergekosten bij externe sorteren.

Begrijpen van externe sorteren

Extern sorteren houdt in dat gegevens worden verdeeld in beheersbare brokken, dat elke brok afzonderlijk wordt gesorteerd en dat deze gesorteerde brokken worden samengevoegd tot één gesorteerd bestand. Het samenvoegen van proces kan in meerdere passen worden uitgevoerd, afhankelijk van het aantal brokken en het beschikbare geheugen.

Componenten van Samenvoegen Kosten

De kosten van de samenvoeging zijn voornamelijk afhankelijk van het aantal pasjes en de hoeveelheid gegevens die tijdens elke pas verwerkt worden.

• Het aantal aanvankelijk gesorteerde runs (chunks)
• Het aantal bestanden dat gelijktijdig is samengevoegd (fan-in)
• De totale grootte van de gegevens

Berekenen van de kosten van samenvoegen

De totale kosten van de samenvoeging kunnen worden berekend met behulp van de formule:

Samengevoegde kosten = aantal passen × Totale gegevens die in elke pas worden verwerkt

Om het aantal passen te bepalen, gebruik de formule:

Aantal passen = log_fan-in (Aantal eerste runs)

Bijvoorbeeld, als er 16 eerste runs zijn en het systeem 4 bestanden tegelijk kan samenvoegen, dan:

Aantal passen = log₄ 16 = 2

De totale gegevens die in elke pas worden verwerkt, zijn gelijk aan de totale grootte van alle data die tijdens die pas worden samengevoegd. Samengevat over alle pasjes geeft de totale merge kosten.