MFF UK / Ústav teoretické fyziky / Tomáš Ledvinka
Přednášky
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
  Úvod
  Programy a algoritmy
  Píšeme program
  Píšeme program II
  Procedury a funkce
  Malujeme funkce
  Chyby. Typy I.
  Typy II. Pole a Záznamy
  Pole II.Řetězce.Soubory.
  Gnuplot.Interpolace...
  Matice. Velké O...
    Matice
    Soustava lineárních rovnic
    Časová náročnost algoritmu
    Seznamy
  Fronta,Zásobník. Postscript
  Bin. soubory, ...
  Ukazatele,Objekty, ...
Počítačová algebra
Klasická elektrodynamika (2.r)
Vybrané partie OTR

Cvičení
. . . . . . . . . . . . . . . . . . . . . . . . . .
Programování pro fyziky (1.r)
Teoretická mechanika (2.r)
Klasická elektrodynamika (2.r)


Věda
. . . . . . . . . . . . . . . . . . . . . . . . . .
Diskové zdroje v OTR
Hyperbolické systémy v OTR


Kontakt
. . . . . . . . . . . . . . . . . . . . . . . . . .
Email
Konzultační hodiny


Ostatní
. . . . . . . . . . . . . . . . . . . . . . . . .
Mallorca
Ze společnosti

Seznamy a jiné lineární datové struktury

Mimo jiné si zde ukážeme, že má smysl mluvit o typickém a nejhorším možném případě a jeho časové náročnosti.

Netříděný seznam


Jmeno='Pavel'
Teplota=36.5
Jmeno='Martin'
Teplota=37.5
Jmeno='Jan'
Teplota=36.9
Jmeno='Hugo'
Teplota=39.5
Jmeno='Igorl'
Teplota=37.2
Jmeno='Ivo'
Teplota=37.1


Přístup přes index..... O(1)
Přidání položky O(1)
Ubrání položky O(N)
Nalezení položky O(N)

Seřazený seznam

Jmeno='Hugo'
Teplota=39.5
Jmeno='Igorl'
Teplota=37.2
Jmeno='Ivo'
Teplota=37.1
Jmeno='Jan'
Teplota=36.9
Jmeno='Martin'
Teplota=37.5
Jmeno='Pavel'
Teplota=36.5
 

 

Přístup přes index O(1)
Přidání položky O(N)
Ubrání položky O(N)
Nalezení položky podle klíče.... O(log(N))
Nalezení položky obecně O(N)

Komentář: Nejlepší, nejhorší a typický případ pro operaci přidání.
Cvičení
: napište proceduru, která v seřazeném seznamu hledá pomocí půlení intervalu a ukažte, že časová náročnost je O(log(N)).

Poznámka: toto je důležitý návod jak hledat v tabulkách funkčních hodnot pokud nejsou hodnoty nezávislé proměnné rovnou ekvidistantní, kdy se dostáváme na O(1).

Asociativní pole

Jde o velmi zajímavou a důležitou datovou strukturu. Základní idea po uživatelské stránce je mít možnost jako index použít místo pořadí rovnou klíč, třeba řetězec.

Bohužel není možné psát přímo

TeplotaPacienta := Pacineti['Pavel'].Teplota

a) protože to Object Pascal neumí b) protože není jasné jestli tam položka s klíčem 'Pavel' vůbec je

proto se přístup (vlastně vyhledání) podle klíče rodělí na dva kroky

1. Nalezení indexu k položce a ověření její existence
2. Vlasní přístup přes index

Trik spočívá v tom, že první operaci lze uskutečnit v čase O(1).

1. Nejprve se spočte hodnota tzv. matlací (hash) funkce, která přiřadí klíči celé číslo. Tato funkce musí mít velmi divokou závislost své hodnoty na klíči, rozhodně nestačí součet hodnot znaků řetězce nebo něco jiného jendoduchého, ale zároveň nesmí být výpočetně příliš náročná.
hash('Pavel') --> 1249765812

2. Poté se spočte, kde by podle matlací hodnoty měla v poli ležet hledaná hodnota
1249765812 mod VelikostPole ---> 7

3. Na indexu 7 se buď

a) nenachází nic
b) je tam hledaný prvek
c) je tam nějaký jiný prvek se stejnou hodnotou MatlaFce mod VelikostPole.
Pak se dějí věci, např. se prohlížejí všechny položky až do první prázdné, jestli není tam, když už bylo správné místo obsazené.

Důležité je, že pokud Matlafunkce funguje správně, je nepravděpopdobné, že se v jednom políčku sejdou dvě položky a bude třeba řešit kolizi, pokud máme pole dimenzováno, řekněme, třeba na dvojnásobek požadované kapacity.

Podobně se přidává prvek, hned poté, co zjistíme jestli tam náhodou už není a nejde tedy jen o přepsání.

(Pozn. Hotovou máme v Delphi bohužel jen strukturu (objekt) THashedStringList)

Více o asociativních polích se do přednášky nevejde, je ale důležité vědět, že informatici tuto strukturu promysleli a v případě potřeby máme k dipozici seznam následujících parametrů:

Přístup přes index O(1)
Přidání položky O(1)
Ubrání položky O(1)
Nalezení položky podle klíče.... O(1)
Nalezení položky obecně O(N)

Pro fyzika nabízí tato struktura možnost "kešovat" výsledky volání funkce.

Pokud výpočet funkce několika diskrétních parametrů trvá dlouho, může se vyplatit schovat si již jednou vypočtené hodnoty. Narozdíl od funkce s jedním parametrem jako je faktoriál, kde si hodnoty schováme do pole a je to, musíme v tomto případě sáhnout po složitějším řešení. Parametry dohromady tvoří klíč. Ten zamatláme a podle matlacího indexu výsledek spolu s klíčem uložíme v poli. Pokud pak potřebujeme znovu již jednou spočtený výsledek, můžeme okamžitě zjistit, zda je ještě k dispozici, nebo byla kolonka "keše" přepsána. Obvykle totiž kolize řešíme zahozením původního obsahu. To jsme u seznamu nemohli. Pokud víme, že se stejné parametry opakují 10x na každých 10 000 volání, víme, že hotovostní paměť na 1000 výsledků nás vytrhne i když výsledky v okamžiku kolize v keši zahazujeme.

Vnitřní třídění seznamu

Třídění = řazení.Vnitřní proto, že se odehrává uvnitř polovodičové části počítače a ne třeba na magnetické pásce.

Potřebujeme mít definovanou funkci <= dvou parametrů typu položky pole k setřídění. Část položky, která obsahuje informaci potřebnou pro porovnání se nazývá klíč. Obvykle z klíče nevyplývá přímo poloha v setříděném seznamu a má význam jen při porovnání s jiným klíčem.

Seznam považujeme za setříděný, platí-li
A1 <= A2 <= A3 <= ... <= AN

Uvažujme tři příklady algoritmů pro třídění seznamu.

Třídění výběrem největšího prvku

Nejdříve najdeme mezi položkami 1..N tu největší a tu pak přehodíme s tou poslední.
Poté mezi položkami 1..N-1 najdeme tu největší a tu dáme na N-1 místo.
Atd. Algoritmus je viditelně O(N^2).


Třídění probubláváním

Spočívá v likvidaci všech míst, kde nejsou výše uvedené nerovnosti splněny. Seznam procházíme zdola nahoru a kdykoli narazíme na pár sousedních prvků seznamu, který nesplňuje pořadované řazení, oba prvky prohodíme. Když na žádnou inverzi nenarazíme, je hotovo. Jde o složitější variantu předchozího, pravděpodobně inspirovanou magnetickými páskami a jinými sekvenčními zařízeními pro ukládání dat. Počet přehazování totiž oproti minulé variantě výrazně stoupl, ale porovnávání i přehazovanání se odehrává blízko sebe.

Quicksort

je název algoritmu (Hoare cca 1960), který většinou dokáže seřadit seznam v čase O(N log N). Využívá toho, že do přesné polohy položky mají nejvíce co mluvit ty sousední. Proto:

  • Rozdělí celý seznam na dvě skupiny: tu, kde jsou položky menší než nějaká zvolená a tu druhou, rozdělení probíhá přehazováním položek, které do příslušných částí nepatří.
  • Poté obě části předá sám sobě k rekurentnímu přeřazení. Pokud nám minulý krok rozdělí pole na zhruba dvě stejně velké části, dostáváme, podobně jako metody u půlení  intervalu, jen logaritmický počet kroků, kterých je zapotřebí, abychom došli k seznamu délky 1, který již není třeba třídit.

Potíž spočívá v tom, že položku, podle které rozdělujeme seznam na dvě části, vezmeme aniž víme jestli je blízko "prostředku". Proto se může stát, že pro nevhodně uspořádaný vstup vezmeme vždy tu nejmenší/největší a skočíme u časové náročnosti O(N^2).

Cvičení: Vyzkoušejte si to napsat pro jednoduché pole čísel a) pomocí rekurze b) pomocí zásobníku.

Motivace: Otevřete si stránku http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html s prohlédněte si animace a porovnejte rychlost výše uvedených algoritmů.Ty tam najdete pod názvy Selection Sort, Bubble Sort a Quick Sort.

Kód programu testujícího quicksort by mohl vypadat takto:

Program Sort;

procedure Quicksort(var A: array of real; l, r: Integer);
var  i, j : Integer;
     swp, rozhod: real;
begin
  rozhod := A[(l + r) div 2];

  i := l; j := r;
  while i<j do begin
    while (A[i] < rozhod)  do i:=i+1;
    while (rozhod < A[j])  do j:=j-1;
    if i <= j then begin
      swp := A[i]; A[i] := A[j]; A[j] := swp;
      i:=i+1; j:=j-1;
    end;
  end;
  if l < j then Quicksort(A, l, j);
  if i < r then Quicksort(A, i, r);
end;

var data : array [0..220000 ] of real;

       i : integer;
begin
  for i :=0 to High(data) do data[i]:=random;
  Quicksort(data,0,High(data));
  for i :=1 to High(data) do if data[i-1]>data[i] then writeln('NESETRIDEN0');
  Writeln('OK');
  readln;
end.

Potíž se tříděním dnes nespočívá v neznalosti algoritmu, ale v tom, jak naučit knihovní funkci, která třídění za nás obstará třídit data jejichž strukturu sama nezná. O tom ale příště.

.