17.21. Třídění v paměti (ICSORT, ICSORTM, ICSORTP) Funkce: Příkaz CALL 'ICSORT' provádí třídění tabulky v paměti dle podklauzulí ASCENDING/DESCENDING z klauzule OCCURS. Způsob volání: CALL 'ICSORT' USING tabulka [počet-prvků] Pravidla: První argument "tabulka" označuje tabulku, která má být příkazem setříděna. Musí to být položka, která má ve svém popisu klauzuli OCCURS s podklauzulí ASCENDING/ DESCENDING. Tato položka smí být v příkazu CALL zapsána zcela bez indexů nebo s menším počtem indexů, než kolik klauzulí OCCURS se k ní vztahuje. V takovém případě se předpokládá, že explicitně uvedené indexy jsou prvními indexy pro položku a že poslední indexy jsou vynechané. Překladač u všech vynechaných indexů předpokládá implicitně hodnotu 1; je tedy ekvivalentní psát A(1) nebo A, psát B(1 1 1) nebo B, psát C(I J 1) nebo C(I J) apod. Argument "tabulka" určuje první prvek tabulky, jenž vstupuje do třídění. Chceme-li tedy - jak tomu bývá téměř vždy - třídit tabulku od jejího začátku, musí být poslední index položky "tabulka" hodnotu 1 nebo musí být vynechán. Není-li položka "tabulka" podřízena další položce s klauzulí OCCURS (tj. není-li součástí vícerozměrného pole), lze v tomto případě uvést položku "tabulka" zcela bez indexů. Je-li poslední index položky "tabulka" explicitně uveden a jeho hodnota není rovna 1, bude tabulka tříděna nikoliv od svého začátku, nýbrž až od prvku s uvedeným indexem, přičemž prvky s nižšími indexy do třídění nevstupují a zůstávají na místě. V tomto případě je prakticky nutné uvést druhý argument "počet-prvků", neboť implicitně vypočítaný počet prvků (viz dále) by byl většinou nevyhovující. Délka prvku tabulky (tj. položky uvedené jako první argument a tvořící svým opakováním tabulku) smí být až 32767 bytů. Druhý argument "počet-prvků" je nepovinný a uvádí se jen zcela výjimečně. Není-li uveden, bude počet prvků tabulky vstupujících do třídění roven a) není-li v klauzuli OCCURS u položky "tabulka" uvedena podklauzule DEPENDING, pak celému-číslu-2 uvedenému v této klauzuli OCCURS, jež zadává počet opakování prvku; b) je-li v klauzuli OCCURS u položky ""tabulka" uvedena podklauzule DEPENDING, pak okamžité hodnotě celočíselné numerické položky uvedené za slovem DEPENDING. Je-li tedy poslední index položky "tabulka" vynechán nebo má-li hodnotu 1 a není-li uveden druhý argument "počet-prvků", bude setříděna právě celá tabulka od začátku až do konce. V praxi bude tento případ zajisté daleko nejčastější. Druhý argument ""počet-prvků" se uvádí pouze tehdy, chceme-li třídit jiný počet prvků, než je plný počet všech prvků v tabulce. Je-li tento druhý argument "počet-prvků" uveden, určuje počet prvků tabulky vstupujících do třídění, přičemž "implicitní" plný počet prvků v tabulce se ignoruje. Tento druhý argument může být a) kladné celé číslo rovné požadovanému počtu prvků, b) celočíselná numerická položka s nezápornou hodnotou rovnou požadovanému počtu prvků, c) speciální index definovaný v popisu položky "tabulka" nebo v popisu některé jiné tabulky, která má touž délku opakujícího se prvku; počet prvků pak bude roven pořadí odpovídajícímu tomuto speciálnímu indexu (a to i v případě, že tabulka není tříděna od svého začátku!; pokud však tabulka je tříděna od svého začátku, musí tento speciální index ukazovat na poslední prvek vstupující do třídění); d) položka s USAGE INDEX, jejíž hodnota vznikla uložením speciálního indexu vyhovujícího bodu c. Je-li položka "tabulka" podřízena další položce s klauzulí OCCURS (tj. je-li součástí vícerozměrného pole), budou mít všechny prvky vstupující do třídění týž první až předposlední index, ať už jsou tyto indexy uvedeny explicitně nebo vynechány a implicitně předpokládány rovny 1; mění se tedy pouze poslední index. (Takže např. u dvourozměrného pole se jediným provedením příkazu CALL 'ICSORT' setřídí pouze jeden řádek se zadaným prvním indexem, viz též příklad.) Tabulka (resp. její část určená výše uvedenými pravidly) bude setříděna vzhledem ke všem klíčům uvedeným v podklauzuli ASCENDING/DESCENDING klauzule OCCURS v popisu položky "tabulka". V této podklauzuli může být uvedeno až 31 klíčů, jimž mohou příslušet různé způsoby srovnávání. Klíče rozpakované, pakované, binární (o délce 2 nebo 4 byty), exponenciální krátké a exponenciální dlouhé a dále klíče s USAGE INDEX se při třídění srovnávají numericky, zatímco klíče skupinové, alfanumerické, alfanumerické editované, binární o délce 8 bytů (!), exponenciální znakové (!) a numerické editované (!) se srovnávají alfanumericky. Poznámky: 1) Třídění je prováděno pomocí tzv. Shellova třídicího algoritmu. Prvky se přemísťují výhradně v zadané tabulce s jedním pracovním místem v pracovním poli přeloženého programu, žádná pomocná paměť se nevyhrazuje. 2) Hodláme-li třídit nejvýše 10-15 prvků, je výhodné místo jména ICSORT uvést jméno ICSORTM (argumenty jsou stejné o témže významu). Přeložený program se tím zkrátí o několik desítek bytů a poněkud se i zrychlí. 3) Příkaz CALL 'ICSORT' je vhodný pro třídění tabulek menších rozsahů (asi do 2000 prvků), zatímco pro rozsáhlejší tabulky je vhodnější použít příkaz SORT se vstupní a výstupní rutinou (jenž ovšem vyžaduje daleko více psaní). Následující tabulka ukazuje přibližnou dobu třídění v tisícinách vteřiny na počítači PC/AT (12 MHz) při délce prvku 20 bytů a jediném alfanumerickém klíči o délce 5 bytů s náhodnými hodnotami (viz ICGEN): počet prvků CALL 'ICSORT' CALL 'ICSORTM' příkaz SORT --------------------------------------------------------- 0 0.1 0.1 0.8 2 0.2 0.2 1.0 4 0.4 0.3 1.3 6 0.6 0.4 1.6 8 1.0 0.7 1.9 10 1.4 1.1 2.2 12 1.8 1.6 2.5 14 2.2 2.2 2.8 16 2.6 2.8 3.3 18 3.0 3.6 3.8 20 3.4 4.4 4.4 24 4.1 6.0 5.0 28 5.1 8.2 6.2 32 6.8 10.7 7.4 40 10 17 9 50 14 23 12 60 18 31 15 80 26 58 21 100 34 108 27 150 66 241 50 200 99 421 73 250 129 635 96 300 176 892 121 400 307 1590 167 500 453 2444 200 600 586 3617 271 800 825 6427 410 1000 987 9670 493 1500 1760 21200 820 2000 2690 37790 1200 2500 3840 60090 1540 3000 5110 1920 4) Příkaz CALL 'ICSORTP' s týmiž argumenty jako příkaz CALL 'ICSORT' smí být použit pouze tehdy, jsou-li první až předposlední prvek tabulky již setříděny. Příkaz CALL 'ICSORTP' pak tuto tabulku setřídí, to jest zařadí poslední prvek tabulky na patřičné místo a všechny další prvky počínaje tímto místem posune o jedno místo doprava. 5) Z hlediska rychlosti třídění je nejvýhodnějším typem klíče jednobytová položka (libovolného typu, avšak bez S v PICTURE), pak dvoubytová nebo čtyřbytová binární položka (nebo položka s USAGE INDEX), pak exponenciální krátká nebo dlouhá položka (má-li počítač vestavěnou pohyblivou aritmetiku), pak skupinová, alfanumerická nebo alfanumerická editovaná položka anebo rozpakovaná nebo pakovaná položka bez S v PICTURE (srovnání se zde provádí alfanumericky), a nejméně výhodným klíčem je rozpakovaná nebo pakovaná položka s S v PICTURE. 6) Příkaz CALL 'ICSORT' resp. CALL 'ICSORTM' resp. CALL 'ICSORTP' je překládán nikoliv voláním funkce, nýbrž přímo obyčejnými příkazy jazyka C; je proto velmi efektivní. Žádné podprogramy se jmény ICSORT, ICSORTM a ICSORTP neexistují a nejsou dodávány. Příklad: 01 A. 02 B OCCURS 1000 DEPENDING N ASCENDING C. 03 C PIC 9(5). 03 D PIC X(15). Příkaz CALL 'ICSORT' USING B setřídí prvky B(1),...,B(N) (tj. právě celou tabulku B) dle klíče C vzestupně. Příkaz CALL 'ICSORT' USING B 80 setřídí prvky B(1),...,B(80) dle klíče C vzestupně (i kdyby bylo N menší než 80). Příkaz CALL 'ICSORT' USING B(I) M setřídí prvky B(I),B(I+1), ...,B(I+M-1) dle klíče C vzestupně; nevyžaduje se, aby bylo I >= 1 a I+M-1 <= N resp. 1000. Příkaz CALL 'ICSORT' USING B(I) bez druhého argumentu by setřídil prvky B(I),...,B(I+N-1), což si asi uživatel nepřál (ledaže by úmyslně uložil do N nikoliv počet prvků v tabulce, nýbrž počet prvků, které se mají třídit). Místo takové značně nesrozumitelné a nebezpečné taktiky je vhodnější uvést explicitně druhý argument "počet-prvků". Příklad: 01 A. 02 B OCCURS 10 DEPENDING N INDEXED I. 03 C OCCURS 20 INDEXED J. 04 D OCCURS 30 ASCENDING E. 05 E PIC S9999 COMP. 05 F PIC X(8). Příkaz CALL 'ICSORT' USING D(I J) setřídí prvky D(I J 1), D(I J 2),...,D(I J 30) dle klíče E vzestupně; setřídí tedy pouze jeden řádek této trojrozměrné tabulky. Chceme-li setřídit všech N*20 řádků (tj. každý zvlášť), musíme provést příkaz CALL 'ICSORT' (N*20)-krát např. takto: PERFORM VARYING I UNTIL I > N AFTER J UNTIL J > 20 CALL 'ICSORT' USING D(I J).