int21h

Bublifuk turbo

Třídící algoritmy je zcela základní téma počítačové vědy a dříve nebo později se s nimi setká každý programátor. Zdálo by se tedy, že jde o oblast probádanou a že není třeba psát stokrát omleté téma.
Jenže co když až tak probádané není?

Dá se říci, že existují dvě hlavní skupiny třídicích algorimů. Rozdělení jde podle nárůstu časové náročnosti v závislosti na objemu tříděných dat neboli tak zvané třídicí složitosti.
Algoritmy založené na buble sortu (neboli jak já říkám "bublifuky") nebo na přímém vkládání mají složitost O*n*n. Co to přesně znamená nevím, ale je zřejmé, že průměrná doba průchodu roste se druhou mocninou objemu dat.
Algoritmy rodiny QuickSort mají obvykle složitost O*(n*log(n)) nebo při ideálním uspořádání vstupních dat mohou dosahovat lineární složitosti. Pro algoritmus HeapSort platí to samé co pro QuickSort, ale je méně paměťově náročný. QuickSort se obvykle řeší rekurzivně (je obtížné napsat ho iteračně) a HeapSort obvykle nerekurzivně.

Zůstaneme ale u Bublifuků.
Tyto algoritmy jsou jednoduché a příjde na ně i začátečník. Vypadají nějak takhle:

Procedure Bublifuk(var pole:array of integer);
var z:boolean;
    n,j,k,i,ii:integer;
begin
n:=high(pole)-1;
repeat
z:=false;
i:=0;
while i<=n do
    begin
    j:=pole[i];
    ii:=i+1;
    k:=pole[ii];
    if j>k then
       begin
       pole[i]:=k;
       pole[ii]:=j;
       z:=true;
       end;
    i:=ii;
    end;
until not Z;
end;

Tato implementace patří mezi ty pokročilejší. Navíc jsem se pokusil ji maximálně optimalizovat. Vidíte, že prvky se v každém posouvají vždy maximálně o jedno místo v poli a vždy jedním směrem. Tento postup se dá v některých případech urychlit občasnou změnou pohybu prvků. Takto vylepšené bublifuky se nazývají Přetřásací algoritmy.

Teď se ale podívejte na tento algoritmus. Nic si nedělejte z toho, jestli nerozumíte, jak přesně pracuje. Já ho taky nechápu. Každopádně ale taktéž patří mezi bublifuky.

Procedure BublifukTurbo(var pole:array of integer);
var i,j,l,k,n:integer;
begin
i:=0;
j:=0;
l:=0;
k:=1;
n:=high(pole);
while k>=i do
   begin
   k:=-1;
   while n>k do
      begin
      inc(k);
      l:=pole[k];
      if j>l then
         begin
         pole[i]:=l;
         inc(i);
         pole[k]:=j;
         end;
      if l>j then
         begin
         i:=k;
         j:=pole[k];
         end;
      end;
   j:=0;
   n:=i-1;
   end;
end;

Důležitá ovšem v tuto chvíli není složitost zápisu, ale co umí. Tedy, kolik sežere paměti a jak je rychlý. Je zřejmé, že si drží kladnou vlastnost všech bublifuků, kterou je minimální paměťová náročnost.
A rychlost?
Rychlost si změřte sami...

{!Bude chtit unit Crt!}
const max=5000;
      pocet_pulzu = 300;
var pole:array[0..max] of integer;
    i,x,d:longint;
begin
randomize;
x:=0;
d:=MemW[Seg0040:$6c];
while d=MemW[Seg0040:$6c] do; {pockam, az skonci aktualni pulz}

repeat
for i:=0 to max do
    begin
    pole[i]:=random(80);      {pole naplnim nahodnymi cisly}
   (*write(pole[i],' ');*)    {pokud bys je chtel videt, tak tohle odkomentuj}
    end;

(*writeln;readln;*)

Bublifuk{Turbo}(pole);   {Tridici rutina. Napred zkus jednu varianu, pak druhou}

(*for i:=0 to 152 do           {zase - kdybys chtel videt setridene pole...}
    begin
    write(pole[i],' ');
    end;*)

inc(x);
until MemW[Seg0040:$6c]>d+pocet_pulzu;

writeln('Probehlo ',x,' cyklu.');
readln;
writeln;
writeln;
end.

Máte změřeno?
Řeknu vám, že mě úplně orosilo. Takový nárůst výkonu jsem opravdu nečekal. První, obyčejný, bublifuk jsem napsal já a myslel jsem si, jak jsem ho hezky optimalizoval. A výsledek vidíte sami...
Zajímá vás, kdo je autorem BublifukuTurbo? No, já to nejsem.
Pravda je taková, že autorem není nikdo!
BublifukTurbo totiž napsal počítač. Přesněji řečeno je to produkt náhodné mutace kódu. Existuje totiž program, který simuluje evoluci. Zadáte tam zdrojový kód a program ho nechá náhodně mutovat a jednotlivé mutace pak mezi sebou nějak soutěží (asi v rychlosti) a přežívají ty nejlepší kusy. Za nějakou dobu, nevím, jestli jsou to hodiny nebo dny nebo ještě déle se vyselektují skutečně VELMI dobré algoritmy.
Jak už tušíte, tak BublifukTurbo vznikl sérií náhodných mutací původního Bublifuku. (S tím, že oba algoritmy byly původně v C a já je přepsal do pascalu.)

A jak je to se složitostí algoritmu? Nevím.
QuickSort je podle vědců z laboratoře, kde tohle monstrum vzniklo, pořád o něco rychlejší u zcela náhodných polí. (Z čehož vyplývá, že moje testovací rutina není optimální), ale u polí, která jsou alespoň trochu už předtím uspořádaná, vítězí BublifukTurbo.
A částečně uspořádaná vstupní data jsou v programátorské praxi častější než totální chaos.

Co říct závěrem?
Tohle je první hmatatelný výsledek genetických algoritmů, které mám tu čest vidět. Je to fascinující, ale zároveň i dost děsivé...