B-halda - B-heap

A B-halda je binární hromada implementován tak, aby udržoval podstromy v jednom strana. To snižuje počet stránek, které jsou při použití při velkých hromadách až desetkrát přístupné virtuální paměť ve srovnání s tradiční implementací.[1] Tradiční mapování prvků na místa v pole umístí téměř každou úroveň na jinou stránku.

Existují i ​​další haldy, které jsou účinné v počítačích využívajících virtuální paměť nebo mezipaměti, jako například mezipaměťové algoritmy, hromady k,[2] a rozložení van Emde Boas.[3]

Motivace

Tradičně, binární stromy jsou uloženy v po sobě jdoucí paměti podle a n -> {2n, 2n + 1} pravidlo, což znamená, že pokud je uzel v poloze n, jeho levé a pravé dítě je bráno v poloze 2n a 2n + 1 v poli. Kořen je v poloze 1. Běžnou operací na binárních stromech je vertikální traverz; sestupování mezi úrovněmi stromu, aby se dospělo k prohledávanému uzlu. Avšak vzhledem ke způsobu, jakým je paměť organizována na moderních počítačích do stránek ve virtuální paměti, může být toto schéma rozložení binárního stromu vysoce neúčinné. Důvodem je, že stejně jako při procházení hlouběji do stromu vzdálenost k dalšímu uzlu roste exponenciálně, takže každý další získaný uzel bude pravděpodobně na samostatné stránce paměti. Tím se zvýší počet stránka chybí, které jsou velmi drahé. Halda B řeší tento problém tak, že podřízené uzly v paměti rozloží jiným způsobem a snaží se co nejvíce umístit podstromy na jednu stránku. Jak tedy postupuje vertikální traverz, několik po sobě jdoucích načtených uzlů bude ležet na stejné stránce, což povede k nízkému počtu chyb na stránce.

Implementace

Podrobně lze hromadu b implementovat následujícím způsobem. Poul-Henning Kamp[4] dává dvě možnosti pro rozložení uzlů: jednu, ve které jsou zbytečné dvě pozice na stránku, ale je zachována přísná binární struktura stromu, a další, která využívá celý dostupný prostor stránek, ale strom se nerozbalí pro jednu úroveň při vstupu na novou stránku (uzly na této úrovni mají pouze jedno dítě). Důležitým bodem je v každém případě to, že po opuštění stránky jsou oba podřízené uzly vždy na společné jiné stránce, protože ve svislém příčném směru algoritmus obvykle porovná obě děti s rodičem, aby věděl, jak postupovat. Z tohoto důvodu lze o každé stránce říci, že obsahuje dva paralelní podstromy, které jsou navzájem proložené. Samotné stránky lze považovat za m-ary strom, a protože polovina prvků na každé stránce budou listy (na stránce), má „strom stránek“ dělicí faktor velikost stránky / 2.

Nadřazená funkce

Na rozdíl od klasického rozložení podobného poli je nadřazená funkce v hromadě B složitější, protože index nadřazeného uzlu musí být vypočítán odlišně v závislosti na tom, kde na stránce je. Za předpokladu, že pozice uvnitř stránky jsou označeny od 0 do velikost stránky, nadřazená funkce může být následující.

U uzlů 0 a 1 se používají pouze ve variantě, která využívá veškerý možný prostor. V tomto případě je nadřazený index obou uzlů stejný, je na jiné stránce a jeho konkrétní posun v rámci této stránky závisí pouze na aktuálním čísle stránky. Chcete-li konkrétně vypočítat číslo stránky rodiče, jednoduše vydělte číslo stránky aktuálního uzlu faktorem rozdělení „stromu stránky“, což je velikost stránky / 2. Chcete-li na stránce získat správné posunutí, zvažte, že musí být jedním z uzlů listu na nadřazené stránce, takže začněte na posunutí velikost stránky / 2. Pak přidejte rozdíl mezi aktuálním číslem stránky a číslem stránky rodiče, minus jedno od první stránky poté, co má nadřazená stránka svůj nadřazený uzel v indexu (velikost stránky / 2).

U uzlů 2 a 3 se nadřazená položka liší v závislosti na režimu. V režimu úspory místa jsou rodiči jednoduše uzly 0 a 1, takže je třeba odečíst pouze 2. Na druhou stranu, v režimu přísného binárního stromu jsou tyto uzly místo toho kořeny stránky 0 a 1, a tak se jejich společný rodič počítá stejným způsobem, jak je popsáno výše.

U všech ostatních uzlů bude jejich nadřazený prvek na stejné stránce a stačí rozdělit jejich posun v rámci jejich stránky o 2, aniž by se změnilo číslo stránky.

Viz také

Reference

  1. ^ Kamp, Poul-Henning (2020-07-26). "Děláš to špatně". Fronta ACM.
  2. ^ Naor, Dalit; Martel, Charles U .; Matloff, Norman S. (1991). "Výkon struktur prioritních front v prostředí virtuální paměti". Comput. J. 34 (5): 428–437. doi:10.1093 / comjnl / 34.5.428.
  3. ^ van Emde Boas, P.; Kaas, R .; Zijlstra, E. (1976). Msgstr "Návrh a implementace efektivní fronty priorit". Teorie matematických systémů. 10: 99–127. doi:10.1007 / BF01683268.
  4. ^ phk.freebsd.dk http://phk.freebsd.dk/B-Heap/. Citováno 2019-06-08. Chybějící nebo prázdný | název = (Pomoc)

externí odkazy