Posted By: Jovo () on 'CZprogram'
Title:     Jovovy poznamky (sort, DJGPP)
Date:      Fri Feb  6 12:50:22 1998

Ahoj,
  trideni :

  Asi takhle : kdyz delas trideni fajlu, tak je nejlepsi asi bubblesort, nebo 
insertsort. Proc ten kacirsky nazor ? 
1) bubble je STABILNI, napise se na 10 radek a je v pohode. Malo kdy bude 
nekdo tridit vic nez 1000 fajlu a na to bubble staci. Na normalnim pentyju 
ani nepoznate rozdil a na 486ce ?  Koho by zajimalo, ze je to o nula cela 
neco pomalejsi, ze jo :-) 
2) insert sort. Ten je podle me lepsi, protoze tady nedostanes balik dat a 
trid boruvko. Tady data prichazeji sekvencne a je tedy mozne pouzit binarni 
vyhledavani + hned vlozeni -> slozitost se bude motat nekde kolem O(nlog n) 
plus minus autobus :-)   No, ma nekdo lepsi napad ? 

Quick sort & radix & spol je sice mnohem rychlejsi, ale chybi mu stabilita, 
i nejjednosussi verze nejsou trivialni a navic vetsinou  i rekurzivni (!) a 
tak je musime predelavat a to uz se nadela chyb (bubble napisete za 30 vterin 
:-)   Uznavam, ze na velke baliky dat je Quick & spol ZNATELNE lepsi, ale 
predstavte si tohle : 
  Nemate VUBEC zadnou diskovou cache. Ctete zaznamy a ladujete je do pole, 
ktere potom setridite. Pri cteni dalsiho musite cekat, nez disk najde 
pozadovana data -> a mezitim jste mohli delat to, co jsem popsal jako bod (2)!

  Jo a kdyz se vam nelibi, ze budete pri kazde vymene prvku prehazovat bloky 
pameti (zde nezalezi na vyberu algoritmu), tak si udelejte pole indexu a 
steridte ho, misto originalni posloupnosti :-)


  DJGPP +- Allegro : 
Asi takhle : pod BC odladim program 5x rychlejc (i na pentiu na 150). Duvod 
je pomalejsi kompilace (i bez optimalizaci) a hlavne linkovani. Troufnu si 
tvrdit, ze kdyz BCku bude link trvat .. 2 vteriny .. tak GCCcku to bude trvat 
nejmin 5. Pro BC staci 4MB ram a to v ni mate 1MB cache, kdezto pro DJGPP
toho musite mit nejmin 16MB, aby se vam neusoupal harddisk :-(
  Navic, kdyz linkujete Allegro, tak se vam link prodrazi klidanko z 5ti na 15 
vterin. Jinak Allegro verze 3.0 je velky jak prase (prelozena knihovna ma 
neco kolem 850Kb) a to se uz neda ustat. Sahnul jsem na disk, prelozil 
Allegro2.1 (280kB) a hned to bylo lepsi. 
  Jinak pri praci DJGPP mam nastavenou 8MB cache (32MB RAM je v compu celkem) 
a teprve potom se na disk skoro nehrabne, i kdyz linkujete allegro :-( 

  Ja to delam takhle (zrovna ladim diplomku s 3D grafikou - texturovani 
obecne plochy pro zajemce) :  Naprogramuju si to pod Borlandem, odladim a ve 
chvili, kdy jsem hotov, nebo kdyz mi to zacne delat blbe chyby (null pointer 
assigment a spol) prejdu plynule pod DJGPP a po vyreseni jedu zpet. Je jasne, 
ze mi pod borlandem nefunguje treba Zbuffer (640*480*sizeof(double) = neco 
kolem 2.5 MB ????) ale usetrim si spoustu casu.

  Az na male chybycky (treba ve watchi) ma DJGPP MNOHEM lepsi editor, nez 
borlandacke IDE. Bohuzel az do predchozich letnich prazdnin neumelo RHIDE 
krokovat (F8,F7,F4) a to se pak tezko ladi, ze jo :-) Ted je verze 1.4 a ta 
umi toho spoustu navic (zkuste treba napsat '#i'  a pak stisknete CTRL-SPACE 
- vice se doctete v helpu:/index/Pseudo Macros, nebo zvlast podarene, 
macknete si na vetsim zdrojaku ALT-F2 a najede vam seznam vsech funkci) 
proste uplne chrochtam blahem :-)

 ... to jsem se rozkecal, sorry lidi :-) ...
Jovo.
PS: HEJ !!!!!!!!!
    Pokud mate zajem, mam takovou malou pitominu, ktera vam umozni vzit 
zdrojak napsany pro BC i s grafikou (#include <graphics.h>) a bez velkych 
potizi to prelozi pod Allegrem. Pak muzete skakat mezi BC a DJGPP az do 
aleluja. Ne ze by to byl nejaky zazrak (berte to spis jako inspiraci). Adresa:

http://www.stud.fee.vutbr.cz/~xhovor00/alg.html

Funguje to oboje v 256 barvach a rozlisenich az 1024x768. Jdu tam dat novou 
verzi a prilozim i maly priklad. Jovo.
 

Search the boards