Hello Coderek!

Nagy kerdessel fordulok hozzatok! A szamtech tanarom adott egy
feladatot: 3 ismeretlenes egyenletrendszer megoldasa pascalban Gauss
eliminacioval. A problema az ott van, hogy gozom sincs, hogy mi ez, es
hogy mukodik. Aki tehat tud valamit a temaval kapcsolatban, az legyen
olyan kedves, es irja meg! (nem forraskod kell, hanem magyarazat)

Elore is koszi: Ulrich David

K. coderek,

 ...ez valahogy hosszura sikeredett...

VAti irta a rendezesrol:
> tankonyvben, 1000 folotti elemszamnal azonban csak a Quick Sort
> nevre hallgato eljaras jon szoba. (a qsort is ezt valositja
> meg, es egy beepitett fgv.nel gyorsabbat ugyse irsz)
 ...
> QuickSort-nal gyorsabb algoritmus elmeletileg se nagyon
> letezik. Csodak nincsenek.udv: VAti

ezeknek a kategorikus kijelentéseknek nem tudtam ellenálni (en meg tanultam

a nagy O-rol :-), ezért kísérleteztem egy picit. Knuth-ot (A
szamitogep-programozas
muveszete 3, 1988-as magyar kiadas) csak az eredmenyek megszerzese utan
konzultaltam. Ott megtalalhato az elmelet, en most inkabb arra voltam
kivancsi,
mire kepes egy (meglehetosen kommersz :-) C++ fordito es konyvtar.

Eloszor is a platform: PII 300MHz, 144MB RAM, Win NT 4.0, MS VC 6.0,
"optimize
for speed", realtime prioritassal futtatott tesztek. Az idoket
QueryPerformaceCounter()-rel mertem, ez az en gepemen 1193182-szer ut
masodpercenkent, vagyis az eredmenyeknek mondjuk a 4. tizedesjegyig batran
hihetunk...ami most eleg. Mas platformon persze gettimeofday(), miegymas.

Bemeneti parameterek: sztringek (sorok) szama (32 ezertol 1 millioig);
karakterek szama soronkent. Szovegfajl-bemenet eseten a rovidebb sorokat
szokozzel toltottem fel erre a hosszra (ez persze vitathato). Amit most
mondani
fogok, addig jo, amig minden belefer a memoriaba (nem is page-l); ezutan
tessek a Knuth-ot masutt follapozni.

A bemenet: ket veletlenszeruen generalt tomb (random1, random2), a teljes
angol
Biblia-forditas (King James), Shakespeare-osszes. A szovegfajokat 2x
olvastam
be, kulonbozo hosszusagu sorokba tordelve. Annyi elmondhato, hogy a random
inputok nyilvan sokkal egyenletesebb eloszlasuak, mint a Biblia (ahol
sokkal tobb
sor kezdodik pl. a-val, mint x-szel).

Az algoritmusok (ezek persze pointereket mozgatnak, nem magukat a
sztringeket):
a standard C konyvtarbol:
  q(uick)-sort (VAti ajanlata)

a standard C++ (STL, standard template library) konyvtarbol:
  (quick-)sort,
  stable-sort (ebbe bele sem neztem, szoval nem is t'om milyen algoritmus),
  heap-sort (ezt csak gondolkodas nelkul alkalmaztam, lehet hogy tobbre
kepes,
     mint amit mutatott)
amit en irtam:
  egy rendkivul primitiv, rekurziv(!) merge-sortot (osszefesulo rendezes,
     Knuth 5.2.4) 15 perc alatt
  es par ora alatt egy elegge optimalizalt radix-sortot (szetoszto
rendezes,
     Knuth 5.2.5). Az utobbi persze csak az   elso k(=2,4,6) jegy alapjan
     rendez szetosztassal, ezutan atmegy quick-sortba a fonnmarado rovid
     rendezetlen szakaszokon. Ezt elmagyarazhatom reszletesebben,
     ha valakit erdekel (ld. Knuth, 195-196. o).

Az eredmenyek masodpercben (>nem< 1 futtatas utan; beolvasas+egyeb
adminisztracio nelkul):
Input:         random1   random2  bible.txt bible.txt shake.txt shake.txt
Sorok:          100000   1000000      32678    119533    147542    361891
Kar./sor:          160        16        400        40       160        16
qsort:        0.633658  7.398052   0.243408  0.749268  1.874299  2.674157
STL sort:     0.492606  6.096468   0.243541  0.660227  1.300007  2.128240
STL stable:   0.645598  6.841123   0.263715  0.915037  1.499647  2.375374
STL heapsort: 0.643203  9.465724   0.224219  0.845729  1.447876  2.982673
Merge:        0.430895  5.464989   0.183319  0.616789  1.092378  1.906171
Radix2:       0.198983  2.454733   0.213976  0.478770  0.977200  1.324238
Radix4:       0.270723  2.496851   0.223944  0.470482  0.964905  1.223633
Radix6:       0.378967  3.555291   0.214221  0.501114  0.990408  1.322525

Par kovetkeztetes:
1. élből nem mondanam azt, hogy >ezen< a platformon, >ilyen< bemenettipusok

mellett a qsort() feltetlen hive lennek :-)
2. ha pl. a telefonkonyvet kene rendeznem, akkor a fenti adatokbol en
semmire
sem kovetkeztetnek, hanem kiserleteznek egy kicsit (felteve, hogy tenyleg
>muszaj< rendezni es hogy tenyleg a rendezes a >bottleneck<).
3. Meglepo (?), hogy az C++-fele rekurziv template-s qsort gyorsabb, mint
a C-fele rekurziobol-csinaljunk-iteraciot qsort. Persze, az STL-t nemcsak
ezert szeressuk.
4. Persze az is fontos (lehet), hogy mennyi plusz memoriat igenyelnek az
egyes algoritmusok. Ezt most ne reszletezzuk.
5. A beszuro-, buborek-, egyeb kvadratikus rendezesek vedelmere annyit,
hogy
a qsort() is atmegy insert-sortba pluszminusz16 elem alatt; ezenkivul
>majdnem< rendezett tombok csakis insert-sortra vágynak.
6. ... Shakespeare rendezesere azonban csak a Shake Sort nevre hallgato
eljaras jon szoba. (VAti utan szabadon).

Erdekes lenne ezeket az adatokat mas platformon (hw, oprszr, fordito,
konyvtar)
is ellenorizni; nekem most sajnos csak NT-hez van hozzaferesem (ill. a
tobbi
gepunkon nincs jo C++ forditonk).
Forrast kuldhetek (nem a listara, mert kb. 400 sor).

Udv
Balázs Gyuri, MIS AG, Prága

Sziasztok!

Teljesen uj vagyok a listan, de maris beleutom az orrom a 
dolgokba, ha nem baj... :))

 > ...
 >   Regs.w.ax=0x2;
 >// BE : BX = val•s m•dbeli szegmens sz…ma
*>   Regs.w.bx=VESAInfo->pOEMSeg;
 >   S.ds=S.es=S.fs=S.gs=FP_SEG(&S);
 >// DPMI Segment to Descriptorfunkcio INT31/AX=2
 >   int386x(0x31,&Regs,&Regs,&S);
*>!  OEMString=(char far *)MK_FP(Regs.w.ax,*((Word
*)(&VESAInfo->pOEM)));
 >   printf("%s\n",OEMString);
>
>Na, a kerdesem az lenne, hogy a debuggerben (WD) miert ad helyes eredmenyt,
>(azaz az OEMString az "S3 Incorporated. ViRGE /DX /GX" szovegre mutat nalam)
>a programban pedig nem ?

Csak annyi a kulonbseg, hogy a WD-ben futtatod, vagy amikor nem
hasznalsz debuggert
ujra is forditod a debug opciok nelkul?
Jol van beallitva a structure member alignmented?
A *-os sorokban a struktura ket kulonbozo tagjara hivatkozol, viszont a
strukturaban,
amit irtal, csak a szegmens-offszet-es valtozat van definialva.
Ez a kodban tulajdonkeppen hogy van?

>...Nem erre lenne jo az a DPMI funkcio ? Vagy csak rosszul probaltam meg kiirn
i ?
>Meg lehet ezt oldani masolas nelkul is ?

Miert nem hasznalod ki azt, hogy DOS/4G alatt a teljes memoriat
linearisan tudod 
cimezni? Az RM far pointerbol igy konnyen lehet PM near mutatot
csinalni!
Kicsit gany, de muxik! :)

>Mas: Ha teszek a programba delay()-t, akkor miert var mar ez elejen (amikor a
>DOS/4GW szoveget kiirta) is egy kicsit, mig ha nem teszek akkor szinte azonnal
>elindul a programom ? A sleep()-nel nincs ilyen gond, de az nem millisec-ben,
>hanem sec-ben varja a parametert.

A delay-el (ha jol emlexem) jar egy kis inicializalo rutin, ami az
indulaskor
kalibralja a delay idozitociklusat az adott rendszer sebessegehez. (Jo
mi?)
Azt nem tudom, hogy mi tortenik akkor, ha a program futasa _kozben_
nyomod
meg a TURBO gombot, vagy multitask OS alatt futtatod a programodat... :)

********************

>Így kis helyen telepedne a program és nem használná el az egész
>hagyományos memóriámat.

Ha jol ertem, Te irtal egy programot es szetetned, ha
nem zabalna meg a teljes 64K-t, csak amennyit Te allokalsz.
Ez altalaban attol szokott fuggni, hogy mennyi heap-et es
stack-et tartatsz fent a linkerrel a program szamara.
Milyen nyelven irod, es milyen orditot hasznalsz?

Na, sziasztok, megyek dolgozni! :)

-- 
ifj. Jako Balazs				MH: 359-9873/624, 359-9872/624
mailto:		mailto:
mailto: (privat)	http://www.extra.hu/bazsi

Hali!

Itten van egy eljaras Dbase/Paradox filek packolasara ( Foleg
Sanyi figyelmebe ajanlom a Windows programozas szepsegeit, de a
tobbit majd eloben  :)

procedure PackTable(Sender: TObject; TabName: PChar);
var
  hDb       :hDBIDb;
  hCursor   :hDBICur;
  dbResult  :DBIResult;
  PdxStruct :CRTblDesc;
;

Na ennyit, remelem segithettem mindenkinek;

OPi;