Druhá série třicátého osmého ročníku KSP
Celý leták v PDF.
Řešení úloh
- 38-2-1: Všechny cesty vedou přes Řím
- 38-2-2: Stop STOPkám
- 38-2-3: Opisování
- 38-2-4: Zákeřná parkovací místa
- 38-2-S: Hledá se pivot
38-2-1 Všechny cesty vedou přes Řím (Zadání)
První si označme Kolín jako vrchol u a Brno jako vrchol v. Teď pojďme přemýšlet v řeči grafů. Vrchol na všech uv-cestách (všech cestách z u do v) si označme dominující. Cíl úlohy je pro každý vrchol zjistit, zda je dominující.
Ve zbytku řešení zafixujeme nějakou libovolnou uv-cestu, označme ji P. Vrcholy x ∉P z definice nejsou dominující (jelikož neleží na všech uv-cestách) a vrchol x ∈P není dominující, právě když jde najít nějaká cesta P' taková, že x ∉P'. Intuitivně se pro každé x ∈P snažíme zjistit, zda jde "obejít".
Jak může taková P' vypadat? Cest s x ∉P' může být opravdu hodně, ale dá se rozmyslet, že pokud x není dominující, tak vždycky bude existovat cesta P', která začíná stejně jako P, pak jde nějakou dobu výhradně po hranách a vrcholech mimo P a pak končí stejně jako P.
Označme vrcholy na cestě P popořadě jako w1, w2, … , wℓ. Předchozí pozorování se dá zformalizovat do následujícího tvrzení: vrchol wj ∈P není dominující, právě když existují vrcholy wi a wk pro i < j < k takové, že mezi wi a wk se dá dojít po vrcholech mimo P. Jeho pravdivost nahlédneme snadno: pokud takové dva vrcholy existují, pak vrchol wj můžeme obejít. Naopak pokud wj můžeme obejít, tj. pokud existuje P' not∋wj, tak se v P' dá najít vhodné wi a wk.
Stačí nám tedy pro každý vrchol wi spočítat, do jakého nejpravějšího vrcholu wk ∈P z něj umíme najít obchůzku. Označme index takového vrcholu jako ki.
Spočítat ki můžeme například prohledáváním do hloubky upraveným tak, že si zakážeme používat vrcholy v P. Průběžně si udržujeme nejpravější vrchol P, který jsme dosud viděli, a na konci jeho index uložíme jako ki.
Naivní řešení spočítá ki pro všechna wi v čase O(|P| (M + N)) ⊂ O(N (M + N)). Teď máme |P| intervalových tvrzení tvaru "vrcholy mezi i a ki nejsou dominující". Naivně pak můžeme v čase O(|P|2) ⊂ O(N2) pro každý vrchol rozhodnout, zda je dominující. Celková časová složitost je O(N (M + N)).
Jak tento algoritmus zrychlit? Důležité je následující pozorování: vůbec nemusíme počítat ki, stačí nám jen vždycky určit, jestli se z wi umíme dostat dál než ze všech předchozích wj pro j < i, a případně kam. Pokud ne, tak nám vrchol wi nedává žádnou novou informaci (obchůzka z něj je ostře horší než nějaká jiná). Speciálně při DFS z wi stačí navštěvovat jen vrcholy, které jsme ještě nenavštívili v předchozích voláních: u těch navštívených už totiž víme, že nám nepomohou objevit z wi lepší obchůzku. Můžeme tedy všechna DFS pustit s jednou globální značkou "navštíveno" pro každý vrchol, kterou mezi voláními neresetujeme. Tak za celý běh algoritmu navštívíme každý vrchol a hranu nejvýše jednou a celková časová složitost prohledávání bude jen O(N + M).
S takto upraveným algoritmem umíme snadno zjistit, které vrcholy jsou dominující. Udržujeme si m, index nejvzdálenějšího vrcholu na P, do kterého se umíme dostat z nějakého j < i. Pokud při příchodu do vrcholu wi platí m ≤ i, pak je vrchol wi dominující, jinak není.
Celkem nám algoritmus zabere času v O(N + M) pro nalezení P a dalších O(N + M) pro nalezení obejitelných vrcholů na P.
38-2-2 Stop STOPkám (Zadání)
Zhrnutie
Úloha od nás chce aby sme našli takú cestu z vrcholu 1 do vrcholu N, ktorá prioritne minimalizuje počet zastavení na STOPkách a sekundárne dĺžku cesty. Je známe, že ak by sme chceli iba minimalizovať dĺžku cesty, tak by sme mohli použiť napríklad Dijkstrov algoritmus. V tejto úlohe však máme dve kritériá, ktoré chceme minimalizovať, avšak ukážeme si že po malej modifikácii to Dijkstrovým algritmom stále pôjde.
Dijkstrov algoritmus
Dijkstrov algoritmus funguje tak, že postupne hľadá najkratšie cesty do všetkých vrcholov zo začiatočného vrcholu. Začne v začiatočnom vrchole, do ktorého sa vieme dostať prejdením nulovej vzdialenosti. Následne pre každého jeho suseda vieme že sa do neho vieme dostať prejdením vzdialenosti rovnajúcej sa vzdialenosti do aktuálneho vrcholu plus dĺžke hrany medzi nimi. V ďaľšom kroku vyberieme vrchol s najmenšou vzdialenosťou, ktorú sme zatiaľ našli, a ešte sme z neho neprechádzali jeho susedov, a opakujeme proces, teda zisťujeme najkratšie cesty do jeho susedov. Detaily o Dijkstrovom algoritme môžete nájsť na Wiki stránke.
Modifikácia Dijkstrovho algoritmu
Použitie dvoch kritérií nám úlohu mierne komplikuje, avšak vieme si všimnúť, že algoritmus vie fungovať aj s viacerími kritériami. Stačí, aby sme namiesto ukladania jednej hodnoty vzdialenosti ukladali dvojicu hodnôt, počet zastavení a vzdialenosť. Porovnanie bude fungovať lexikograficky, teda najprv porovnáme počet zastavení a ak sú rovnaké, tak porovnáme vzdialenosť. Vidíme že takéto porovnanie vždy prioritne minimalizuje počet zastavení a sekundárne dĺžku cesty, čo je presne to, čo chceme. Teda po tejto modifikácií vieme spustiť štandardný Dijkstrov algoritmus.
Ako riešiť hlavné a vedľajšie cesty?
Implementačný trik na či je cesta je hlavná alebo vedľajšia je, že si v každom vrchole zoradíme hrany podľa priority, a následne sa vždy iba pozrieme či je hrana po ktorej sme prišli medzi dvoma hranami s najvyššou prioritou.Ak nie je, tak sme prišli po vedľajšej ceste a musíme pripočítať jedno zastavenie, pretože budeme musieť čakať na STOPke. Je si avšak treba dať pozor na špeciálny prípad, keď prídeme do koncového vrcholu N, tam totiž čakať nemusíme, takže vtedy zastavenie nepripočítavame.
Ako rekonštruovať cestu?
Cestu vieme rekonštruovať štandardným spôsobom, teda si pri každom vrchole pamätáme takzvaný back-pointer, teda z ktorého vrcholu sme do neho prišli po najkrašej ceste. Po skončení algoritmu vieme začať v koncovom vrchole N a postupne chodiť po back-pointeroch až kým nedôjdeme do vrcholu 1. Týmto spôsobom získame cestu v opačnom poradí, takže ju ešte treba otočiť.Zložitost
Dijkstrov algoritmus s použitím prioritnej fronty beží v čase O((M+N) log N), kde N je počet vrcholov a M počet hrán.Pamäťová zložitosť je O(N+M) na uloženie grafu a ďalších O(N) na ukladanie vzdialeností a back-pointerov.
38-2-3 Opisování (Zadání)
Pojďme si nejdřív rozmyslet, s čím to vlastně pracujeme: Dostali jsme tabulku N×M, tedy víme pro každého studenta, kterou úlohu umí. Co ale pro nás bude důležitější, je, že víme pro každou úlohu, který student ji umí – a tedy pro každou úlohu, kolik studentů ji umí.
Pro každou úlohu si tedy spočítáme, kolik studentů ji umí. Teď vezměme tu, kterou umí co nejméně studentů – neboli kterou neumí co nejvíce studentů. Když před neznalými studenty nebude žádný znalý, tak všechny neznalé s jistotou vyhodíme!
Jde to ale lépe? Můžeme teď zase třídit sekundárně podle druhé nejméně známé otázky, a tak dále? Myšlenka je to lákavá, ale ukážeme si, že ne: nechť K je počet studentů, kteří neumí nejtěžší otázku. Platí, že ať uspořádáme studenty jakkoliv, (K+1)-tý z nich (a tedy i každý další) správně odpoví na všechny otázky. To proto, že pro každou otázku existuje nanejvýš K studentů, kteří ji neumějí, tudíž mezi K+1 prvními studenty bude aspoň jeden, který tuto otázku umí. (K+1)-tý student tedy díky opisování správně odpoví všechny otázky.
Naše řešení jednou projde celou tabulku N×M, pro každou otázku zjistí počet znalých studentů a nakonec všechny znalé studenty nasází nakonec a neznalé dopředu, což zvládneme v čase Θ(N). Celková časová složitost bude tedy v Θ(NM).
38-2-4 Zákeřná parkovací místa (Zadání)
S dovolením budeme referovat pouze k hodnotám parkovacích míst a jejích umístění v řadě. To, že jsou to parkovací místa a že na nich stojí auta, ačkoliv nás naplňuje nepokojem, protože jistě alespoň polovina ze zúčastněných mohla přijet městskou hromadnou dopravou a ušetřit tím jak peníze, tak životní prostředí, není algoritmicky zajímavé.
Co vlastně můžeme usoudit, když se podíváme na hodnotu na jednom místě? A ono vlastně vůbec nic – samotná hodnota jednoho místa nám nic neřekne. Když se ale podíváme i na jeho sousedy, hned z toho můžeme něco zjistit. Mohou nastat tři situace:
- Oba sousedi mají nižší/stejnou hodnotu – našli jsme hledané místo.
- Jeden soused má nižší/stejnou hodnotu a jeden vyšší – co v tu chvíli můžeme usoudit o směru, ve kterém je ten vyšší? Jelikož hodnoty nemůžou růst pořád, páč by jistě narazily na okraji, tak se někde tímto směrem určitě nachází nějaké vyhovující místo. Tedy se můžeme koukat jenom na místa tímto směrem s jistotou, že tam nějaké vyhovující místo je.
- Oba sousedi mají vyšší hodnotu – můžeme si vybrat, kterým směrem se vydáme a aplikujeme předchozí tvrzení.
No a nakonec už si akorát všimneme, že takhle se můžeme podívat do poloviny prohledávaného úseku a tím polovinu jistě zahodit. Tedy v každém kroku snížíme počet prohledávaných pozic na zhruba polovinu. Tedy celkem uvidíme 3· log2 N pozic, což je v O(log N).
Poznámka na závěr: pokud bychom chtěli zlepšovat konstantu před log2 N, existuje na to chytrý algoritmus jménem metoda zlatého řezu. Ta používá podobnou myšlenku, že ze tří hodnot jsme schopni vyloučit část parkoviště, ale místo tří sousedních parkovacích míst volí místa trochu složitěji, čímž na každé úrovni rekurze musíme vyhodnotit jen jednu novou pozici. Nevýhodou je, že rekurze je trochu hlubší, jelikož pole nepůlíme přesně v půlce. Přesto počet dotazů díky tomu klesne, a to konkrétně na zhruba 1,44 log2 N. Pokud jste zvědaví, můžete si přečíst víc na anglické Wikipedii.
38-2-S Hledá se pivot (Zadání)
Úkol 1 – Worst-case hloubka rekurze [1b]
K důkazu nám stačí jednoduché pozorování – Pokaždé, když vložíme na zásobník větší úsek, tak za nový aktuální úsek prohlásíme ten menší. Tedy jsme délku aktuálního úseku alespoň vydělili dvěma. Protože délka aktuálního úseku musí být kladná, budeme mít na zásobníku nejvýše log(n) úseků.
Úkol 2 – Quicksort [3b]
Níže najdete naši implementaci Quicksortu v C++. Obsahuje naimplementované všechny části z následujících úkolů, které se nastavují pomocí preprocesorových maker. Čas měříme uvnitř programu, abychom nezapočítávali čtení vstupu.
#include <assert.h>
#include <algorithm>
#include <iostream>
#include <random>
#include <time.h>
#include <tuple>
#include <unistd.h>
#include <utility>
#include <vector>
using std::cin, std::cerr, std::cout, std::min, std::pair, std::swap, std::tuple, std::vector;
typedef unsigned int uint;
#ifndef CUTOFF
#define CUTOFF 10
#endif
#ifndef GET_PIVOT
#define GET_PIVOT pivot_median_of_three
#endif
struct interval {
int start;
int end;
int depth;
const int length() const {
return end - start + 1;
}
const int middle() const {
return start + length()/2;
}
};
static std::mt19937 rng;
uint pivot_median_of_three(const vector<uint> &arr, const interval interval) {
uint a = arr[interval.start];
uint b = arr[interval.middle()];
uint c = arr[interval.end];
if (a > b)
swap(a, b);
if (c > b)
return b;
else if (c > a)
return c;
else
return a;
}
uint pivot_middle(const vector<uint> &arr, const interval interval) {
return arr[interval.middle()];
}
uint pivot_random(const vector<uint> &arr, const interval interval) {
std::uniform_int_distribution<uint> dist(interval.start, interval.end);
return arr[dist(rng)];
}
static void bubblesort(vector<uint> &arr, const interval interval) {
bool swapped = true;
auto end = interval.end;
while (swapped) {
swapped = false;
for (int i=interval.start; i<end; i++) {
if (arr[i] > arr[i+1]) {
swap(arr[i], arr[i+1]);
swapped = true;
}
}
end--;
}
}
static void mergesort(vector<uint> &arr, const interval interval) {
vector<uint> merged;
merged.reserve(arr.size());
for (int len = 1; len < interval.length(); len *= 2) {
for (int i = interval.start; i <= interval.end; i += 2*len) {
merged.clear();
int l = i;
int r = i + len;
while (l < i+len && r < i+2*len && r <= interval.end) {
if (arr[l] <= arr[r])
merged.push_back(arr[l++]);
else
merged.push_back(arr[r++]);
}
for (; l < min(i+len, interval.end+1); l++)
merged.push_back(arr[l]);
for (; r < min(i+2*len, interval.end+1); r++)
merged.push_back(arr[r]);
for (int j = 0; j < (int) merged.size(); j++)
arr[i + j] = merged[j];
}
}
}
static pair<int, int> divide(
vector<uint> &arr, const interval interval, const uint pivot
) {
int l = interval.start;
int r = interval.end;
while (l <= r) {
while (arr[l] < pivot) l++;
while (arr[r] > pivot) r--;
if (l <= r)
swap(arr[l++], arr[r--]);
}
return {l, r};
}
static tuple<int, int, int> divide_two_pivot(
vector<uint> &arr, const interval interval, uint pivot1, uint pivot2
) {
if (pivot1 > pivot2)
swap(pivot1, pivot2);
int k = interval.start;
int l = interval.start;
int r = interval.end;
while (l <= r) {
if (arr[l] < pivot1) {
swap(arr[k++], arr[l++]);
} else if (arr[l] <= pivot2) {
l++;
} else {
while (l < r && arr[r] > pivot2)
r--;
swap(arr[l], arr[r--]);
}
}
return {k, l, r};
}
void quicksort(vector<uint> &arr, uint seed) {
rng.seed(seed);
#ifdef ALPHA
const int hybrid_depth = ALPHA * log2(arr.size());
#endif
#ifdef SHUFFLE
std::shuffle(arr.begin(), arr.end(), rng);
#endif
interval current = {0, (int) arr.size() - 1, 0};
vector<interval> intervals;
while (true) {
if (current.length() <= CUTOFF) {
if (CUTOFF > 1)
bubblesort(arr, current);
if (intervals.size() == 0)
break;
current = intervals.back();
intervals.pop_back();
#ifdef ALPHA
} else if (current.depth >= hybrid_depth) {
mergesort(arr, current);
if (intervals.size() == 0)
break;
current = intervals.back();
intervals.pop_back();
#endif
} else {
#ifdef TWO_PIVOT
uint pivot1 = GET_PIVOT(arr, current);
uint pivot2 = GET_PIVOT(arr, current);
auto [k, l, r] = divide_two_pivot(arr, current, pivot1, pivot2);
interval left = {current.start, k-1, current.depth+1};
interval middle = {k, l-1, current.depth+1};
interval right = {l, current.end, current.depth+1};
if (left.length() < right.length())
swap(left, right);
if (middle.length() < right.length())
swap(middle, right);
intervals.push_back(left);
intervals.push_back(middle);
current = right;
#else
uint pivot = GET_PIVOT(arr, current);
auto [l, r] = divide(arr, current, pivot);
interval left = {current.start, r, current.depth+1};
interval right = {l, current.end, current.depth+1};
if (left.length() < right.length())
swap(left, right);
intervals.push_back(left);
current = right;
#endif
}
}
}
uint64_t get_time()
{
return (uint64_t)((double)clock() / CLOCKS_PER_SEC * 1'000'000'000);
}
int main(int argc, char* argv[]) {
if (argc != 2) {
cerr << "Použití: ./quicksort <seed>\n";
return 1;
}
uint seed = strtoull(argv[1], NULL, 16);
int n;
cin >> n;
vector<uint> arr(n);
for (int i=0; i<n; i++)
cin >> arr[i];
auto start = get_time();
quicksort(arr, seed);
auto end = get_time();
// Sanity check
for (int i=0; i<n-1; i++)
assert(arr[i] <= arr[i+1]);
cout << (end - start) << "\n";
}
Úkol 3 – Generátor [2b]
Nejdřív si rozmysleme, jak vyrobit co nejhorší vstup pro náš výběr pivota ze tří prvků. Pokud poslední prvek bude největší a prostřední druhý největší, tak vybereme za pivota prostřední. Ten v rozdělování prohodíme s předposledním prvkem a zarekurzíme se na o 2 kratší úsek.
Náš vstup pro délku n (s čísly [0,…,n-1]) vyrobíme pozpátku: Vezmeme nejhorší vstup pro délku n-2, přidáme za něj čísla n-2 a n-1 a prohodíme prostřední a předposlední prvek. V našem generátoru najdete iterativní verzi, abychom nemuseli přenastavovat limit velikosti zásobníku.
Generátor by tedy mohl vypadat následovně:
#include <algorithm>
#include <filesystem>
#include <fstream>
#include <functional>
#include <random>
#include <string>
#include <vector>
using std::function, std::pair, std::string, std::swap, std::vector;
typedef unsigned int uint;
const std::filesystem::path INPUTS_DIR = "inputs";
static std::mt19937 gen(0xdeadbeef);
static std::uniform_int_distribution<uint> dist;
uint random_uint() {
return dist(gen);
}
vector<uint> gen_rand(size_t n) {
vector<uint> result(n);
for (int i=0; i<n; i++)
result[i] = random_uint();
return result;
}
vector<uint> gen_increasing(size_t n) {
vector<uint> result = gen_rand(n);
std::sort(result.begin(), result.end());
return result;
}
vector<uint> gen_worst_case(size_t n) {
vector<uint> result(n);
for (size_t i = 0; i < n; i++)
result[i] = i+1;
for (size_t i = 4 + n % 2; i <= n; i += 2)
swap(result[i/2], result[i-2]);
return result;
}
vector<uint> gen_fibonacci(size_t n) {
vector<uint> result = {0, 1};
for (int i=2; i<n; i++)
result.push_back(result[i-2] + result[i-1]);
return result;
}
int main() {
vector<pair<string, function<vector<uint>(size_t)>>> input_kinds = {
{"rand", gen_rand},
{"inc", gen_increasing},
{"wc", gen_worst_case},
{"fib", gen_fibonacci},
};
std::filesystem::create_directory(INPUTS_DIR);
for (auto [name, gen]: input_kinds) {
for (int k=15; k<40; k++) {
size_t n = pow(1.4, k);
vector<uint> arr = gen(n);
std::ofstream input(INPUTS_DIR / (name + "_" + std::to_string(n) + ".in"));
input << n << '\n';
for (int i=0; i<n; i++)
input << arr[i] << (i == n-1 ? "\n" : " ");
}
}
}
Za povšimnutí stojí, že vstupy vyrábíme v 32-bitových bezznaménkových intech, na kterých aritmetika automaticky počítá modulo 232 (takže nemusíme modulit my).
Úkol 4 – Hranice pro ukončení rekurze [2b]
Náš testovací skript vypadá následovně:
#!/usr/bin/env python3
import json
import os
import subprocess
import sys
from typing import NoReturn
BUILD_DIR = "build"
INPUTS_DIR = "inputs"
SEEDS = [
"d323d84f",
"e1b51a58",
"4e2d7fbc",
"cc9539b7",
"e5aff378"
]
def run_subprocess(
args: list[str], stdin: str | None = None, capture_output: bool = False
) -> subprocess.CompletedProcess[bytes]:
print(" ".join(args) + (f" < {stdin}" if stdin else ""), file=sys.stderr)
_stdin = stdin and open(stdin)
return subprocess.run(args, stdin=_stdin, capture_output=capture_output)
def fail(msg: str) -> NoReturn:
print(msg, file=sys.stderr)
exit(1)
def compile(variants: list[list[str]]) -> list[str]:
binaries = []
os.makedirs(BUILD_DIR, exist_ok=True)
for variant in variants:
binary_name = "quicksort_" + "_".join(variant)
binaries.append(binary_name)
args = [
"g++",
"quicksort.cpp",
"-o",
os.path.join(BUILD_DIR, binary_name),
"-O2",
"-march=native"
]
for flag in variant:
args += ["-D", flag]
run_subprocess(args)
return binaries
def gen_inputs() -> None:
gen = os.path.join(BUILD_DIR, "gen")
run_subprocess(["g++", "gen.cpp", "-o", gen, "-O2"])
run_subprocess([f"./{gen}"])
def measure(program: str, inp: str) -> int:
times = []
for seed in SEEDS:
proc = run_subprocess([f"./{program}", seed], stdin=inp, capture_output=True)
times.append(int(proc.stdout.decode()))
times.sort()
return sum(times[1:4]) // 3
def input_data(inp: str) -> tuple[str, int]:
k, n = inp.removesuffix(".in").split("_")
return k, int(n)
if __name__ == "__main__":
try:
subtask = int(sys.argv[1])
except (IndexError, ValueError):
fail("Použití: ./measure.py <číslo podúlohy>")
if subtask == 4:
binaries = compile([
["CUTOFF=1"],
["CUTOFF=3"],
["CUTOFF=5"],
["CUTOFF=7"],
["CUTOFF=10"],
["CUTOFF=20"],
["CUTOFF=30"],
])
elif subtask == 5:
binaries = compile([
["CUTOFF=7", "GET_PIVOT=pivot_middle"],
["CUTOFF=7", "GET_PIVOT=pivot_median_of_three"],
["CUTOFF=7", "GET_PIVOT=pivot_random"],
["CUTOFF=7", "GET_PIVOT=pivot_middle", "SHUFFLE"],
])
elif subtask == 6:
binaries = compile([
["CUTOFF=7", "GET_PIVOT=pivot_random", "ALPHA=0.0"],
["CUTOFF=7", "GET_PIVOT=pivot_random", "ALPHA=1.0"],
["CUTOFF=7", "GET_PIVOT=pivot_random", "ALPHA=2.0"],
["CUTOFF=7", "GET_PIVOT=pivot_random", "ALPHA=2.5"],
["CUTOFF=7", "GET_PIVOT=pivot_random", "ALPHA=3.0"],
["CUTOFF=7", "GET_PIVOT=pivot_random", "ALPHA=5.0"],
["CUTOFF=7", "GET_PIVOT=pivot_random", "ALPHA=10.0"],
])
elif subtask == 7:
binaries = compile([
["CUTOFF=7", "GET_PIVOT=pivot_random", "ALPHA=2.0"],
["CUTOFF=7", "GET_PIVOT=pivot_random", "ALPHA=2.0", "TWO_PIVOT"],
])
else:
fail("Neznámá podúloha")
if not os.path.exists(INPUTS_DIR):
gen_inputs()
data = []
inputs = os.listdir(INPUTS_DIR)
inputs.sort(key=input_data)
for binary in binaries:
for inp in inputs:
time = measure(os.path.join(BUILD_DIR, binary), os.path.join(INPUTS_DIR, inp))
input_kind, n = input_data(inp)
data.append({
"solution": binary,
"input_kind": input_kind,
"n": n,
"time": time
})
print(json.dumps(data, indent=4))
Náš hardware měl následující parametry:
- Procesor: AMD Ryzen 5 7640U
- Taktovací frekvence: 4.972 GHz
- Množství paměti: 32 GB
- Operační systém: Linux
Naměřili jsme následující:
Na náhodném a Fibonacciho vstupu vidíme, že menší hranice vyhrávají. Na worst-case vstupech také vyhrávají, ale vidíme hlavně kvadratickou závislost na délce vstupu. Na rostoucím vstupu jsou naopak lepší vyšší hranice – Bubblesort skončí v lineárním čase.
My jsme vybrali hranici 7. Na náhodném, Fibonacciho a worst-case vstupu se chová velmi dobře, a zároveň neztrácí příliš na rostoucí posloupnosti (můžeme chtít skoro-seřazené posloupnosti umět seřadit rychle).
Úkol 5 – Výběr pivota [2b]
Na náhodném a Fibonacciho vstupu vidíme obdobné výsledky – nejrychlejší je rovnou brát prostřední. Potom následuje náhodný (generování náhody něco trvá) a výpočetně náročnější medián ze tří. Nejhůř je na tom zamíchání na začátku. Abychom pochopili, proč je pomalé, potřebujeme uvažovat o keších.
Hlavní paměť počítače je totiž mnohem pomalejší než procesor – za dobu jednoho přístupu do paměti je procesor schopen provést až stovky instrukcí. Aby program na paměť pořád nečekal, procesor si pomáhá takzvanou keší (cache): to je mnohem menší, a díky tomu mnohem rychlejší paměť, do které si ukládá data, se kterými nedávno pracoval. Detailní rozbor fungování keší by si zasloužil delší povídání (zájemce odkazujeme na medvědův text o programování s ohledem na hardware), ale zde prozradíme, že nejrychlejší je přistupovat opakovaně k malému množství dat, o něco pomalejší sekvenčně číst nebo zapisovat, a úplně nejpomalejší po paměti náhodně skákat. A přesně to poslední se děje, pokud prvky náhodně mícháme.
Zpět k volbě pivota. V rostoucím vstupu vidíme, že náhodný prvek je přibližně pomalejší. To by nás nemělo překvapit, zatímco nenáhodné přístupy vybírají medián, náhodný prvek vybírá jen pseudomedián. Náhodné zamíchání je značně pomalejší, ale ve skutečnosti stejně pomalé jako na ostatních vstupech. Ostatní algoritmy si totiž ušetří spoustu času v rozdělování: Neprohazují prvky, takže z paměti jenom čtou, a navíc se v nich podmínky chovají předvídatelně (což je také důležité pro rychlost: když procesor dopředu uhodne, jak bude program pokračovat, může si instrukce předem rozpracovat; detaily opět viz Medvědův text).
Na worst-case vstupu jsou náhodné pivoty výrazně lepší, nejde jim totiž podhodit garantovaně zlý vstup.
Pro další experimenty jsme si vybrali jako pivota brát náhodný prvek.
Úkol 6 – Hybridsort [2b]
Na náhodném, rostoucím a Fibonacciho vstupu vidíme, že nastavovat α > 2.0 vede ke stejným až horším výsledkům. Mergesort používá více paměti, čímž ztrácí na efektivitě. Na worst-case vstupu naopak vyšší α ztrácí, proto nastavujeme α = 2.0.
Úkol 7 – Dvoupivotový quicksort [3b]
Dvoupivotový Quicksort jsme naprogramovali tak, že opět rozděluje na místě. Získáme tři úseky, z nichž nejmenším pokračujeme, zatímco zbylé dva odložíme na zásobník. To opět garantuje logaritmickou hloubku zásobníku.
Z výsledků překvapivě plyne, že jednopivotový Quicksort má nad dvoupivotovým převahu – v závislosti na typu vstupu drobnou nebo trochu větší. Přiznáváme, že přesně nevíme, proč. Podezíráme větší počet prohození během rozdělování.