# Dynamické pole, realokace

## Dynamické pole

### Indexovatelný seznam

│ • abstraktní datová struktura
│ • operace:
│   ◦ ‹append› – vloží prvek na konec
│   ◦ ‹remove› – odstraní poslední prvek
│   ◦ ‹get› – vrátí prvek na daném indexu
│   ◦ ‹size› – vrátí aktuální počet prvků
│ • srovnejte zásobník

### Implementace

│ • zřetězený seznam → ‹get› je ⟦O(n)⟧
│ • vyhledávací strom → ‹get› je ⟦O(log n)⟧
│ • standardní pole → neumí ‹append›

### Implementace: dynamické pole

│ • «dynamické pole» → vše konstantní
│   ◦ ale pouze amortizovaně
│ • vyhradíme paměť jako u běžného pole
│ • dojde místo → realokace
│   ◦ alokujeme větší pole
│   ◦ dosavadní prvky přesuneme
│   ◦ původní paměť uvolníme

### Amortizace

│ • uvažme posloupnost ⟦n⟧ operací
│ • jaká je průměrná složitost jedné?
│   ◦ ⟦n⟧ vložení v čase ⟦O(n)⟧
│   ◦ na jedno vložení připadne čas ⟦O(1)⟧
│ • metody analýzy → IB114

### Taktika zvětšování

│ • o konstantu
│   ◦ špatná asymptotická složitost
│   ◦ pouze speciální situace
│ • na dvojnásobek
│   ◦ zaručuje správnou složitost
│   ◦ jednoduché a účinné

### Exponenciální zvětšování

│ • na abstraktní úrovni optimální
│ • dopad na využití paměti?
│   ◦ fragmentace adresního prostoru
│   ◦ (ne)využitelnost uvolněné paměti
│ • možnosti řešení:
│   ◦ alternativní schéma zvětšování
│   ◦ speciální podpora v alokátoru

## Realokace paměti

### Situace

│ • implementujeme dynamické pole
│ • potřebujeme pole zvětšit
│ • triviálně:
│   ◦ nová alokace + kopie dat
│   ◦ dealokace původního
│ • lze provést i lépe?

### Využití stávající alokace

│ • vyžaduje spolupráci alokátoru
│ • použít následující volný blok
│   ◦ optimální – není potřeba přesun
│   ◦ 
│ • použít předchozí blok

### Využití předchozího bloku

│ • vyžaduje přesun dat
│   ◦ překryv podle poměru velikostí
│   ◦ dvojnásobek → bez překryvu
│ • celková potřebná paměť ⟦m⟧
│   ◦ oproti ⟦m + n⟧ pro novou alokaci
│   ◦ dvojnásobek → ⟦2n⟧ vs ⟦3n⟧

### Přesun dat

│ • kopie ‹for› cyklem po bajtech
│ • co překrývající se oblasti
│   ◦ někdy je potřeba iterovat odzadu
│   ◦ mnohem méně efektivní
│ • alternativní metody dle platformy

### Situace v praxi

│ • knihovna jazyka C má ‹realloc›
│   ◦ umožňuje i zmenšení alokace
│   ◦ poněkud komplikované rozhraní
│ • Rust, D také nabízí ‹realloc›
│ • C++ od podpory upustilo