Ulkoinen lajittelu on tekniikka, jota käytetään käsittelemään suuria tietokokonaisuuksia, jotka eivät sovi päämuistiin. Keskeinen tekijä ulkoisessa lajittelussa on yhdistämiskustannusten laskeminen, mikä auttaa määrittämään lajitteluprosessin tehokkuuden. Tämä opas tarjoaa vaihe vaiheelta lähestymistavan ymmärtää ja laskea yhdistämiskustannuksia ulkoisessa lajittelussa.

Ulkoisen lajittelun ymmärtäminen

Ulkoinen lajittelu tarkoittaa tietojen jakamista hallittaviin osiin, kunkin palan lajittelua erikseen, ja sitten näiden lajiteltujen osien yhdistämistä yhteen lajiteltuun tiedostoon. Yhdistämisprosessi voidaan suorittaa useassa solassa riippuen osien määrästä ja käytettävissä olevasta muistista.

Yhdistämiskustannusten osatekijät

Yhdistymiskustannukset riippuvat ensisijaisesti kulkulupien määrästä ja kunkin välityksen aikana käsiteltävien tietojen määrästä.

  • Alustavien lajiteltujen juoksujen määrä (paloja)
  • Tiedostojen lukumäärä yhdistyi samanaikaisesti (fan-in)
  • Tietojen koko

Yhdistämiskustannusten laskeminen

Yhdistymiskustannusten kokonaismäärä voidaan laskea kaavalla:

Yrityskustannukset = kulkulupien lukumäärä × Kussakin kulkuluvassa käsitellyt kokonaistiedot

Määrittääksesi kulkulupien määrän, käytä kaavaa:

passien lukumäärä = log[fan-in (Ensimmäisten ajojen lukumäärä)

Jos esimerkiksi on 16 alkuajoa ja järjestelmä voi yhdistää 4 tiedostoa kerralla, sitten:

Passien lukumäärä = log4 16 = 2

Kussakin solassa käsiteltävät kokonaistiedot vastaavat kaikkien kyseisen passin aikana sulautettavien tietojen kokonaismäärää. Yhteenlaskeminen kaikkien syöttöjen kesken antaa yhdistämiskustannukset.