\input style \chapnotrue \chapno=5\subchno=4\subsubchno=6 1) pRIVEDENNYE FORMULY POKAZYVAYUT, CHTO SORTIROVKA YAVLYAETSYA, V SUSHCHNOSTI, FUNKCIEJ OT PROIZVEDENIYA~$N$ I~$C$, A NE OT~$N$ I~$C$ POROZNX. zA ISKLYUCHENIEM NESKOLXKIH OTNOSITELXNO NEZNACHITELXNYH SOOBRAZHENIJ (NAPRIMER, CHTO $B$~VYBIRAETSYA KRATNYM $C$), IZ NASHIH FORMUL SLEDUET, CHTO SORTIROVKA ODNOGO MILLIONA ZAPISEJ PO 10 LITER KAZHDAYA ZAJMET PRIMERNO STOLXKO ZHE VREMENI, CHTO I SORTIROVKA 100000 ZAPISEJ PO 100 LITER KAZHDAYA. nA SAMOM DELE ZDESX MOZHET POYAVITXSYA RAZLICHIE, NE OBNARUZHIMOE V NASHIH FORMULAH, TAK KAK VO VREMYA VYBORA S ZAMESHCHENIEM NEKOTOROE PROSTRANSTVO ISPOLXZUETSYA DLYA POLEJ SVYAZI. v LYUBOM SLUCHAE RAZMER \emph{KLYUCHA} EDVA LI OKAZHET KAKOE-LIBO VLIYANIE, ESLI TOLXKO KLYUCHI NE BUDUT STOLX DLINNYMI I SLOZHNYMI, CHTO VNUTRENNIE VYCHISLENIYA NE SMOGUT UGNATXSYA ZA LENTAMI. pRI DLINNYH ZAPISYAH I KOROTKIH KLYUCHAH SOBLAZNITELXNO VYDELITX KLYUCHI, OTSORTIROVATX IH, A ZATEM KAK-NIBUDX PERESTAVITX ZAPISI CELIKOM. nO |TA IDEYA, KAZHETSYA, NE RABOTAET: ONA MOZHET TOLXKO OTSROCHITX AGONIYU, POSKOLXKU PROCEDURA OKONCHATELXNOJ PERESTANOVKI TREBUET POCHTI STOLXKO ZHE VREMENI, SKOLXKO POTREBOVALA BY OBSHCHEPRINYATAYA SORTIROVKA SLIYANIEM. 2) mY VIDELI, CHTO TREBUETSYA OT~15 DO~19~MIN, CHTOBY OTSORTIROVATX 100000~ZAPISEJ PO 100~LITER PRI SOBLYUDENII NASHIH PREDPOLOZHENIJ. sKOLXKO VREMENI ZANYALA BY IH SORTIROVKA NA KARTOCHNOM SORTIROVSHCHIKE? eTOT VOPROS IMEET PRAKTICHESKIJ INTERES POTOMU, CHTO KARTOCHNYE SORTIROVSHCHIKI DESHEVLE evm. dOPUSKAYA, CHTO KAZHDAYA ZAPISX MOZHET BYTX VTISNUTA V 80-KOLONNUYU KARTU I CHTO ALFAVITNYJ KLYUCH ZANIMAET SHESTX KOLONOK, PRICHEM DLYA SORTIROVKI PO KAZHDOJ KOLONKE TREBUETSYA V SREDNEM $1{2\over3}$~PROHODA, POLUCHAEM, CHTO MY DOLZHNY PROPUSTITX KAZHDUYU KARTU CHEREZ MASHINU PRIMERNO 10~RAZ. pRI SKOROSTI 1000 KART V MINUTU |TO ZANYALO BY 1000~MIN, T.~E.~POCHTI 17~CH. (iMEETSYA VESXMA BOLXSHAYA VEROYATNOSTX, CHTO ZA |TO VREMYA NEKOTORYE KARTY OKAZHUTSYA NECHAYANNO "PEREPUTANNYMI" ILI BUDUT "ZAMYATY" V MASHINE.) 3) pRI NAPISANII PROGRAMMY SORTIROVKI, KOTORAYA DOLZHNA ISPOLXZOVATXSYA MNOGOKRATNO, RAZUMNO OCHENX TSHCHATELXNO OCENITX VREMYA RABOTY I SRAVNITX TEORIYU S DEJSTVITELXNYMI NABLYUDAEMYMI HARAKTERISTIKAMI VYPOLNENIYA. tAK KAK TEORIYA SORTIROVKI RAZVITA DOVOLXNO HOROSHO, TO |TA PROCEDURA, KAK IZVESTNO, SPOSOBNA VNEZAPNO VYYAVITX DEFEKTY V OBORUDOVANII ILI PROGRAMMNOM OBESPECHENII VVODA/VYVODA V SUSHCHESTVUYUSHCHIH SISTEMAH. oKAZYVAETSYA OBSLUZHIVANIE RABOTALO MEDLENNEE, CHEM SLEDOVALO, I NIKTO |TOGO NE ZAMECHAL, POKA |TO NE PROYAVILOSX NA PROGRAMME SORTIROVKI! 4) nEKOTORYE VYCHISLITELXNYE SISTEMY IMEYUT DVA "BANKA" %%401 LENTOPROTYAZHNYH USTROJSTV, PRISOEDINENNYH K OTDELXNYM "KANALAM" TAKIM SPOSOBOM, CHTO ODNOVREMENNOE CHTENIE I ZAPISX DOPUSKAETSYA TOLXKO DLYA LENT IZ RAZNYH BANKOV. dLYA TAKOJ KONFIGURACII BOLXSHE VSEGO PODHODIT SBALANSIROVANNOE SLIYANIE. rASSMOTRIM, NAPRIMER, SLUCHAJ SHESTI LENT PO TRI V KAZHDOM BANKE I PREDPOLOZHIM, CHTO MY HOTIM VYPOLNITX MNOGOFAZNOE SLIYANIE S~$T=6$. vOVREMYA PYATIPUTEVOGO SLIYANIYA DVE IZ VVODNYE LENT BUDUT NE V TOM BANKE, TAK CHTO, GRUBO GOVORYA, DVE PYATYH VREMENI VVODA NE BUDUT SOVMESHCHENY S VYVODOM. eTO DOBAVLYAET KO VREMENI SORTIROVKI PRIBLIZITELXNO 40\%, TAK CHTO SBALANSIROVANNOE SLIYANIE OKAZHETSYA LUCHSHE MNOGOFAZNOGO DAZHE V SLUCHAE OBRATNOGO CHTENIYA. 5) nASH ANALIZ VYBORA S ZAMESHCHENIEM BYL VYPOLNEN DLYA "SLUCHAJNYH" FAJLOV, NO FAJLY, VSTRECHAYUSHCHIESYA NA PRAKTIKE, OCHENX CHASTO UZHE UPORYADOCHENY V TOJ ILI INOJ STEPENI. (fAKTICHESKI INOGDA LYUDI BUDUT SORTIROVATX FAJLY, UZHE UPORYADOCHENNYE, TOLXKO CHTOBY UBEDITXSYA V |TOM.) tAKIM OBRAZOM, OPYT DAZHE V BOLXSHEJ MERE, CHEM UKAZYVAYUT NASHI FORMULY, POKAZAL, CHTO VYBOR S ZAMESHCHENIEM PREDPOCHTITELXNEE DRUGIH VIDOV VNUTRENNEJ SORTIROVKI. eTO PREIMUSHCHESTVO NESKOLXKO OSLABLYAETSYA V SLUCHAE MNOGOFAZNOJ SORTIROVKI S OBRATNYM CHTENIEM, TAK KAK DOLZHEN BYTX POROZHDEN RYAD UBYVAYUSHCHIH OTREZKOV; NA SAMOM DELE r.~l.~gILST|D (ON PERVYJ OPUBLIKOVAL MNOGOFAZNOE SLIYANIE) PERVONACHALXNO PO |TOJ PRICHINE OTVERG METOD OBRATNOGO CHTENIYA. nO POZDNEE ON ZAMETIL, CHTO CHEREDOVANIE NAPRAVLENIJ BUDET VSE ZHE DAVATX DLINNYE VOZRASTAYUSHCHIE OTREZKI. kROME TOGO, MNOGOFAZNYJ METOD S OBRATNYM CHTENIEM---|TO EDINSTVENNYJ STANDARTNYJ METOD, KOTORYJ BLAGOSKLONEN K UBYVAYUSHCHIM VHODNYM FAJLAM, RAVNO KAK I K VOZRASTAYUSHCHIM. 6) dRUGOE PREIMUSHCHESTVO VYBORA S ZAMESHCHENIEM SOSTOIT V TOM, CHTO |TOT METOD DOPUSKAET SOVMESHCHENIE PROCESSOV CHTENIYA, ZAPISI I VYCHISLENIJ. eSLI BY MY PROSTO VYPOLNYALI VNUTRENNYUYU SORTIROVKU OCHEVIDNYM SPOSOBOM---ZAPOLNYAYA PAMYATX, SORTIRUYA EE I ZATEM ZAPISYVAYA EE PO MERE TOGO, KAK ONA ZAPOLNYAETSYA NOVYM SODERZHIMYM,---TO PROHOD RASPREDELENIYA ZANYAL BY PRIMERNO VDVOE BOLXSHE VREMENI! iZ RASSMOTRENNYH NAMI METODOV VNUTRENNEJ SORTIROVKI ESHCHE TOLXKO ODIN MOZHNO PRISPOSOBITX K ODNOVREMENNOMU CHTENIYU, ZAPISI I VYCHISLENIYAM---PIRAMIDALXNUYU SORTIROVKU. (eTA IDEYA BYLA ISPOLXZOVANA PRI PODGOTOVKE PRIMERA~10 SHEMY~a.) pREDPOLOZHIM DLYA UDOBSTVA, CHTO VNUTRENNYAYA PAMYATX SODERZHIT 1000~ZAPISEJ, A KAZHDYJ BLOK NA LENTE---PO 100. dEJSTVOVATX MOZHNO SLEDUYUSHCHIM OBRAZOM (CHEREZ $B_1$, $B_2$,~\dots, $B_{10}$ OBOZNACHENO SODERZHIMOE PAMYATI, RAZDELENNOJ NA 10~BLOKOV PO 100~ZAPISEJ). %% 402 {\sl shAG 0.\/} zAPOLNITX PAMYATX I SDELATX TAK, CHTOBY |LEMENTY $B_2$\dots $B_{10}$ UDOVLETVORYALI NERAVENSTVAM PIRAMIDY (S NAIMENXSHIM |LEMENTOM V VERSHINE). {\sl shAG 1.\/} sVESTI $B_1$\dots$B_{10}$ V PIRAMIDU, ZATEM VYBRATX NAIMENXSHIE 100 ZAPISEJ I PEREPISATX IH V $B_{10}$. {\sl shAG 2.\/} zAPISATX IZ $B_{10}$; V TO ZHE VREMYA VYBRATX NAIMENXSHIE 100 ZAPISEJ IZ $B_1$\dots$B_{9}$ I POMESTITX IH V $B_9$. {\sl shAG 3.\/} pROCHITATX V~$B_{10}$ I ZAPISATX IZ $B_9$; V TO ZHE VREMYA VYBRATX NAIMENXSHIE 100~ZAPISEJ IZ $B_1$\dots$B_8$ I POMESTITX IH V~$B_8$. \dots {\sl shAG 9.\/} pROCHITATX V $B_4$ I ZAPISATX IZ~$B_3$; V TO ZHE VREMYA VYBRATX NAIMENXSHIE 100~ZAPISEJ IZ $B_1$ $B_2$, POMESTITX IH V $B_2$ I SDELATX TAK, CHTOBY NERAVENSTVA PIRAMIDY BYLI SPRAVEDLIVY DLYA $B_5$\dots$B_{10}$. {\sl shAG 10.\/} pROCHITATX V~$B_3$ I ZAPISATX IZ~$B_2$, SORTIRUYA~$B_1$, V TO ZHE VREMYA SDELATX TAK, CHTOBY NERAVENSTVA PIRAMIDY BYLI SPRAVEDLIVY DLYA $B4$\dots$B_{10}$. {\sl shAG 11.\/} pROCHITATX V~$B_2$ I ZAPISATX IZ~$B_1$; V TO ZHE VREMYA SDELATX TAK, CHTOBY $B_3$\dots$B_{10}$ UDOVLETVORYALI NERAVENSTVAM PIRAMIDY. {\sl shAG 12.\/} pROCHITATX V~$B_1$, DELAYA TAK, CHTOBY $B_2$\dots$B_{10}$ UDOVLETVORYALI NERAVENSTVAM PIRAMIDY. vERNUTXSYA K SHAGU 1. \endmark 7) mY PREDPOLAGAEM, CHTO CHISLO SORTIRUEMYH ZAPISEJ~$N$ NE IZVESTNO ZARANEE. nA SAMOM ZHE DELE V BOLXSHINSTVE VYCHISLITELXNYH MASHIN ESTX VOZMOZHNOSTX VSE VREMYA SLEDITX ZA CHISLOM ZAPISEJ VO VSEH FAJLAH, I MY MOGLI BY SCHITATX, CHTO NASHA VYCHISLITELXNAYA SISTEMA SPOSOBNA SOOBSHCHITX ZNACHENIE~$N$. nASKOLXKO BY NAM |TO POMOGLO? k SOZHALENIYU, NE OCHENX! mY VIDELI, CHTO VYBOR S ZAMESHCHENIEM VESXMA VYGODEN, NO ON VEDET K NEPREDSKAZUEMOMU CHISLU NACHALXNYH OTREZKOV. v SBALANSIROVANNOM SLIYANII MY MOGLI BY ISPOLXZOVATX INFORMACIYU OB~$N$ DLYA USTANOVLENIYA TAKOGO RAZMERA BUFERA~$B$, CHTOBY $S$~OKAZALOSX, SKOREE VSEGO, CHUTX MENXSHE STEPENI~$P$; V MNOGOFAZNOM RASPREDELENII S OPTIMALXNYM RAZMESHCHENIEM FIKTIVNYH OTREZKOV MY MOGLI BY ISPOLXZOVATX INFORMACIYU OB~$N$, CHTOBY RESHITX, KAKOJ UROVENX VYBRATX (SM. TABL. 5.4.2-2). iDYA PO DRUGOMU PUTI I NE ISPOLXZUYA VYBORA S ZAMESHCHENIEM, MY MOGLI BY PRIMENITX SLIYANIE V PRYAMOM PORYADKE, OPISANNOE V KONCE P.~5.4.4, VSTROIV EGO V OSCILLIRUYUSHCHUYU SORTIROVKU, RASPREDELYAYUSHCHUYU NACHALXNYE OTREZKI SOOTVETSTVUYUSHCHEGO NAPRAVLENIYA V SOOTVETSTVUYUSHCHIJ MOMENT (VMESTO TOGO CHTOBY BRATX IH S "LENTY~$A$", KAK OPISANO). eTOT METOD, V SUSHCHNOSTI, \emph{OPTIMALEN} SREDI VSEH METODOV, VYPOLNYAYUSHCHIH VNUTRENNYUYU SORTIROVKU BEZ VYBORA S ZAMESHCHENIEM, TAK KAK ON SLIVAET V SOOTVETSTVII S NAILUCHSHIM VOZMOZHNYM $P\hbox{-ARNYM}$ DEREVOM, NO ON VSE ZHE RABOTAET MEDLENNEJ METODOV, OSNOVANNYH NA VYBORE S ZAMESHCHENIEM. %% 403 8) lENTOPROTYAZHNYE USTROJSTVA CHASTO OKAZYVAYUTSYA NAIMENEE NADEZHNYMI CHASTYAMI evm. oBSLUZHIVAYUSHCHIJ PERSONAL OBYCHNO POLUCHAET VYZOVY DLYA ISPRAVLENIYA LENTOPROTYAZHNYH USTROJSTV CHASHCHE, CHEM DLYA LYUBOGO DRUGOGO KOMPONENTA MASHINY, I OPERATORY VYCHISLITELXNOJ MASHINY DOLZHNY UMETX VOZOBNOVLYATX RABOTU POSLE SBOYA LENTY. aVTOR NIKOGDA DAZHE NE VIDEL USTANOVOK S~10 ILI BOLEE LENTOPROTYAZHNYMI USTROJSTVAMI, KOTORYE BY VSE ODNOVREMENNO NAHODILISX V HOROSHEM RABOCHEM SOSTOYANII. sLEDOVATELXNO, MOZHNO PRINYATX ZA AKSIOMU, CHTO \emph{ISHODNAYA VVODNAYA LENTA NI V KOEM SLUCHAE NE DOLZHNA IZMENYATXSYA, POKA NE STANET IZVESTNO, CHTO VSYA SORTIROVKA UDOVLETVORITELXNO ZAVERSHENA.} v NEKOTORYH PRIMERAH SHEMY~A SUSHCHESTVUET DOSADNOE "VREMYA, POKA OPERATOR NE SMENIT LENTU", NO BYLO BY SLISHKOM RISKOVANNO ZATIRATX ISHODNYE DANNYE VVIDU VOZMOZHNOSTI KAKOJ-LIBO NEISPRAVNOSTI VO VREMYA DLINNOJ SORTIROVKI. 9) pRI PEREHODE OT PRYAMOJ ZAPISI K OBRATNOMU CHTENIYU MY MOZHEM S|KONOMITX NEKOTOROE VREMYA, VOVSE NE ZAPISYVAYA POSLEDNIJ BUFER NA LENTU; ON V LYUBOM SLUCHAE BUDET VNOVX PROCHITAN! sHEMA~A POKAZYVAET, CHTO |TOT PRIEM V DEJSTVITELXNOSTI |KONOMIT SRAVNITELXNO NEMNOGO VREMENI, ZA ISKLYUCHENIEM SLUCHAYA OSCILLIRUYUSHCHEJ SORTIROVKI, KOGDA NAPRAVLENIYA MENYAYUTSYA CHASTO. 10) eSLI V NASHEM RASPORYAZHENII MNOGO LENTOCHNYH USTROJSTV, TO NE VSEGDA STOIT ISPOLXZOVATX IH VSE V CELYAH POLUCHENIYA "VYSOKOGO PORYADKA SLIYANIYA". tAK, NAPRIMER, BOLEE VYSOKIJ PORYADOK SLIYANIYA OBYCHNO OZNACHAET MENXSHIJ RAZMER BLOKA, A PROCENTNAYA RAZNOSTX MEZHDU $\log_P S$ I~$\log_{P+1} S$ NE OCHENX VELIKA PRI BOLXSHIH~$P$. pODUMAJTE TAKZHE O BEDNOM OPERATORE evm, KOTORYJ DOLZHEN USTANOVITX VSE |TI RABOCHIE LENTY. s DRUGOJ STORONY, V UPR.~12 OPISAN INTERESNYJ SPOSOB ISPOLXZOVANIYA DOPOLNITELXNYH LENTOPROTYAZHNYH USTROJSTV, GRUPPIRUEMYH TAK. CHTOBY SOVMESTITX VREMYA VVODA I VYVODA BEZ UVELICHENIYA PORYADKA SLIYANIYA. 11) nA MASHINAH, PODOBNYH \MIX, KOTORYE IMEYUT FIKSIROVANNYJ I DOVOLXNO MALENXKIJ RAZMER BLOKOV, DLYA SLIYANIYA EDVA LI TREBUETSYA MNOGO VNUTRENNEJ PAMYATI. zDESX OSCILLIRUYUSHCHAYA SORTIROVKA BOLEE PREDPOCHTITELXNA; pOTOMU CHTO STANOVITSYA VOZMOZHNYM SOHRANYATX DEREVO VYBORA S ZAMESHCHENIEM V PAMYATI VO VREMYA SLIYANIYA. nA SAMOM DELE V |TOM SLUCHAE MOZHNO USOVERSHENSTVOVATX OSCILLIRUYUSHCHUYU SORTIROVKU (KAK PREDLOZHIL k.~dZH.~bELL V 1962~G.), SLIVAYA NOVYJ NACHALXNYJ OTREZOK V VYVOD KAZHDYJ RAZ, KOGDA MY SLIVAEM S RABOCHIH LENT! 12) mY VIDELI, CHTO FAJLY NA NESKOLXKIH BOBINAH DOLZHNY SORTIROVATXSYA POSLEDOVATELXNO BOBINA ZA BOBINOJ, CHTOBY IZBEZHATX CHREZMERNOJ RABOTY PO PERESTANOVKE LENT. fAKTICHESKI SBALANSIROVANNOE SLIYANIE S SHESTXYU LENTAMI, ESLI ONO TSHCHATELXNO %% 404 ZAPROGRAMMIROVANO, MOZHET SORTIROVATX \emph{TRI} BOBINY DO MOMENTA OKONCHATELXNOGO SLIYANIYA. dLYA SLIYANIYA OTNOSITELXNO BOLXSHOGO CHISLA OTDELXNO OTSORTIROVANNYH BOBIN BYSTREJSHIM BUDET DEREVO SLIYANIYA S MINIMALXNOJ DLINOJ PUTI (SR. S~P.~5.4.4). eTO POSTROENIE BYLO VPERVYE OSUSHCHESTVLENO e.~X.~fR|NDOM [{\sl JACM\/}, {\bf 3}(1956), 166--167] I ZATEM u.~X.~bURZHEM [{\sl Information and Control,\/} {\bf 1} (1958), 181--197], KOTORYE OTMETILI, CHTO OPTIMALXNYJ SPOSOB SLIYANIYA OTREZKOV DANNYH (VOZMOZHNO, NERAVNYH) DLIN POLUCHAETSYA S POMOSHCHXYU POSTROENIYA DEREVA S MINIMALXNOJ \emph{VZVESHENNOJ} DLINOJ PUTI, ISPOLXZUYA DLINY OTREZKOV V KACHESTVE VESOV (SM.~P.~2.3.4.5 I~5.4.9), ESLI PRENEBRECHX VREMENEM USTANOVKI LENT. nO FAJLY, ZANIMAYUSHCHIE NESKOLXKO BOBIN, VEROYATNO, SLEDUET HRANITX NA DISKAH ILI DRUGOM ZAPOMINAYUSHCHEM USTROJSTVE BOLXSHOJ EMKOSTI, A NE NA LENTAH. 13) v NASHEM OBSUZHDENII MY, NE ZADUMYVAYASX, PREDPOLAGALI, CHTO IMEETSYA VOZMOZHNOSTX ISPOLXZOVATX NEPOSREDSTVENNO INSTRUKCII VVODA/VYVODA I CHTO NIKAKOJ SLOZHNYJ SISTEMNYJ INTERFEJS NE MESHAET NAM ISPOLXZOVATX LENTY S TAKOJ |FFEKTIVNOSTXYU, NA KAKUYU RASSCHITYVALI KONSTRUKTORY APPARATURY. eTI IDEALXNYE PREDPOLOZHENIYA POZVOLILI NAM PRONIKNUTX V SUTX PROBLEM SLIYANIYA, I ONI MOGUT DATX NEKOTORYJ PODHOD K KONSTRUIROVANIYU SOOTVETSTVUYUSHCHIH OPERACIONNYH SISTEM. oDNAKO SLEDUET PONIMATX, CHTO MULXTIPROGRAMMIROVANIE I MULXTIPROCESSIROVANIE MOGUT ZNACHITELXNO USLOZHNITX SITUACIYU. 14) oBSUZHDAEMYE NAMI VOPROSY BYLI VPERVYE RASSMOTRENY V PECHATI e.~X.~fR|NDOM [{\sl JACM,\/} {\bf 3} (1956), 134--165],u.~zOBERBXEROM [{\sl Electron. Datenverarb.,\/} {\bf 5} (1960), 28--44] I m.~a.~gOTCEM [Digital Computer User's Handbook (New York, McGraw-Hill, 1967) 1.292--1.320]. \section rEZYUME. mY MOZHEM SLEDUYUSHCHIM OBRAZOM VKRATCE VYRAZITV VSE, CHTO UZNALI O SRAVNENII RAZLICHNYH SHEM SLIYANIYA: \proclaim tEOREMA a. tRUDNO RESHITX, KAKAYA SHEMA SLIYANIYA YAVLYAETSYA NAILUCHSHEJ V KONKRETNOJ SITUACII. \endmark pRIMERY, KOTORYE MY VIDELI NA SHEME~a, POKAZYVAYUT, KAK 100000~ZAPISEJ PO 100~LITER (ILI 1~MILLION ZAPISEJ PO 10~LITER), RASPOLOZHENNYH V SLUCHAJNOM PORYADKE, MOGLI BY BYTX OTSORTIROVANY S ISPOLXZOVANIEM SHESTI LENT PRI DOSTATOCHNO REALISTICHESKIH PREDPOLOZHENIYAH. eTI DANNYE ZANIMAYUT OKOLO POLOVINY LENTY I MOGUT BYTX OTSORTIROVANY PRIBLIZITELXNO ZA 15--19 MIN; ODNAKO SUSHCHESTVUYUSHCHEE LENTOCHNOE OBORUDOVANIE SILXNO RAZLICHAETSYA PO VOZMOZHNOSTYAM, I VREMYA VYPOLNENIYA TAKOJ RABOTY NA RAZNYH MASHINAH IZMENYAETSYA V DIAPAZONE PRIBLIZITELXNO OT~ %%405 CHETYREH MINUT DO~DVUH CHASOV. v NASHIH PRIMERAH OKOLO 3~MIN RASHODUETSYA NA NACHALXNOE RASPREDELENIE OTREZKOV I VNUTRENNYUYU SORTIROVKU, OKOLO 4.5~MIN---NA OKONCHATELXNOE SLIYANIE I PEREMOTKU VYVODNOJ LENTY I OKOLO 7.5--11.5~MIN---NA PROMEZHUTOCHNYE STADII SLIYANIYA. eSLI IMEETSYA SHESTX LENT, KOTORYE NELXZYA CHITATX V OBRATNOM NAPRAVLENII, TO NAILUCHSHIM METODOM SORTIROVKI PRI NASHIH PREDPOLOZHENIYAH BYLO "MNOGOFAZNOE SLIYANIE S RASSHCHEPLENIEM LENT" (PRIMER~4), A DLYA LENT, DOPUSKAYUSHCHIH OBRATNOE CHTENIE, NAILUCHSHIM METODOV OKAZALSYA MNOGOFAZNYJ METOD S OBRATNYM CHTENIEM SO SLOZHNYM RAZMESHCHENIEM FIKTIVNYH OTREZKOV (PRIMER~7). oSCILLIRUYUSHCHAYA SORTIROVKA (PRIMER~9) ZANIMAET VTOROE MESTO. v OBOIH SLUCHAYAH KASKADNOE SLIYANIE BOLEE PROSTO I LISHX NEZNACHITELXNO MEDLENNEE (PRIMERY~5 I~8). v SLUCHAE PRYAMOGO CHTENIYA OBYCHNOE SBALANSIROVANNOE SLIYANIE (PRIMER~1) OKAZALOSX UDIVITELXNO |FFEKTIVNYM, CHASTICHNO IZ-ZA UDACHI V |TOM KONKRETNOM PRIMERE, A CHASTICHNO IZ-ZA TOGO, CHTO ONO TRATIT SRAVNITELXNO MALO VREMENI NA PEREMOTKU. pOLOZHENIE NESKOLXKO IZMENILOSX BY, ESLI BY V NASHEM RASPORYAZHENII BYLO DRUGOE CHISLO LENT. \section gENERATORY SORTIROVKI. v USLOVIYAH BOLXSHOGO RAZNOOBRAZIYA HARAKTERISTIK DANNYH I OBORUDOVANIYA POCHTI NEVOZMOZHNO NAPISATX EDINSTVENNUYU PROGRAMMU VNESHNEJ SORTIROVKI, KOTORAYA BYLA BY UDOVLETVORITELXNOJ V PODAVLYAYUSHCHEM BOLXSHINSTVE SLUCHAEV. tAKZHE VESXMA TRUDNO SOZDATX PROGRAMMU, KOTORAYA V REALXNYH USLOVIYAH |FFEKTIVNO RABOTAET S LENTAMI. sLEDOVATELXNO, IZGOTOVLENIE PROGRAMMNOGO OBESPECHENIYA SORTIROVKI---SAMOSTOYATELXNAYA ZADACHA, TREBUYUSHCHAYA BOLXSHOJ RABOTY. \dfn{gENERATOR SORTIROVKI}---|TO PROGRAMMA, KOTORAYA, OSNOVYVAYASX NA PARAMETRAH, OPISYVAYUSHCHIH FORMAT DANNYH I KONFIGURACIYU OBORUDOVANIYA, POROZHDAET MASHINNUYU PROGRAMMU, SPECIALXNO PRISPOSOBLENNUYU K KONKRETNOMU PRIMENENIYU SORTIROVKI. pODOBNAYA PROGRAMMA CHASTO SVYAZANA S YAZYKAMI VYSOKOGO UROVNYA, TAKIMI, KAK~kOBOL ILI~PL/1, ILI ONA MOZHET BYTX NAPISANA KAK NABOR MAKROOPREDELENIJ DLYA ISPOLXZOVANIYA SOVMESTNO S MAKROASSEMBLEROM. oDNOJ IZ OSOBENNOSTEJ, OBYCHNO OBESPECHIVAEMYH GENERATOROM SORTIROVKI, YAVLYAETSYA VOZMOZHNOSTX VSTAVLYATX "SOBSTVENNYE KOMANDY"---OSOBYE INSTRUKCII, KOTORYE DOLZHNY VKLYUCHATXSYA V PERVYJ I POSLEDNIJ PROHODY PROGRAMMY SORTIROVKI. sOBSTVENNYE KOMANDY PERVOGO PROHODA OBYCHNO ISPOLXZUYUTSYA, CHTOBY OTREDAKTIROVATX ISHODNYE ZAPISI, CHASTO SOKRASHCHAYA IH ILI NEZNACHITELXNO UDLINYAYA, CHTOBY PRIVESTI IH K FORME, BOLEE PROSTOJ DLYA SORTIROVKI. pUSTX, NAPRIMER, ISHODNYE ZAPISI DOLZHNY BYTX OTSORTIROVANY PO DEVYATILITERNOMU KLYUCHU, IZOBRAZHAYUSHCHEMU DATU V FORMATE MESYAC-DENX-GOD: %%406 $$ |JUL04| \ |OCT311517| \ |NOV051605| \ |JUL141789| \ |NOV201917| $$ tREHBUKVENNYE KODY MESYACEV MOZHNO NAJTI V TABLICE I ZAMENITX CHISLAMI, PRICHEM NAIBOLEE ZNACHASHCHIE POLYA MOGUT BYTX POMESHCHENY SLEVA: $$ |17760704| \ |15171031| \ |16051105| \ |17890714| \ |19171120| $$ eTO UMENXSHAET DLINU ZAPISEJ I DELAET BOLEE PROSTYM POSLEDUYUSHCHEE SRAVNENIE. (kOD KLYUCHEJ MOG BY BYTX SDELAN DAZHE BOLEE KOMPAKTNYM.) sOBSTVENNYE KOMANDY POSLEDNEGO PROHODA MOGUT ISPOLXZOVATXSYA DLYA VOSSTANOVLENIYA ISHODNOGO FORMATA I/ILI DLYA VNESENIYA DRUGIH ZHELATELXNYH IZMENENIJ V FAJL I/ILI DLYA VYCHISLENIYA KAKOJ-LIBO FUNKCII OT VYVODNYH ZAPISEJ. aLGORITMY SLIYANIYA, KOTORYE MY IZUCHILI, ORGANIZOVANY TAKIM OBRAZOM, CHTO POSLEDNIJ PROHOD LEGKO OTLICHITX OT OSTALXNYH FAZ SLIYANIYA. zAMETIM, CHTO ESLI IMEYUTSYA SOBSTVENNYE KOMANDY, TO DOLZHNO BYTX PO KRAJNEJ MERE DVA PROHODA PO FAJLU, DAZHE ESLI ON PERVONACHALXNO NAHODILSYA V PORYADKE. sOBSTVENNYE KOMANDY, IZMENYAYUSHCHIE RAZMER ZAPISEJ, MOGUT ZATRUDNITX SOVMESHCHENIE NEKOTORYH OPERACIJ VVODA/VYVODA V OSCILLIRUYUSHCHEJ SORTIROVKE. gENERATORY SORTIROVKI TAKZHE ZABOTYATSYA O SISTEMNYH DETALYAH, TAKIH, KAK SOGLASHENIYA O METKAH LENT; ONI TAKZHE CHASTO OBESPECHIVAYUT PODSCHET KONTROLXNOJ SUMMY ILI INYE PROVERKI TOGO, CHTO NIKAKAYA CHASTX FAJLA NE PROPALA I NE IZMENILASX. iNOGDA IMEYUTSYA SREDSTVA DLYA OSTANOVKI SORTIROVKI V UDOBNYH MESTAH I VOZOBNOVLENIYA EE POZDNEE. sAMYE VYSOKOKACHESTVENNYE GENERATORY POZVOLYAYUT ZAPISYAM IMETX DINAMICHESKI MENYAYUSHCHIESYA DLINY [SM. D.~J.~Waks, {\sl CACM,\/} {\bf 6} (1963), 267--272]. \section *sLIYANIE S MENXSHIM CHISLOM BUFEROV. mY VIDELI, CHTO $2P+2$~BUFEROV DOSTATOCHNO DLYA PODDERZHANIYA BYSTROGO DVIZHENIYA LENT V TECHENIE $P\hbox{-PUTEVOGO}$ SLIYANIYA. v ZAVERSHENIE |TOGO PUNKTA PROVEDEM MATEMATICHESKIJ ANALIZ VREMENI SLIYANIYA V TOM SLUCHAE, KOGDA IMEETSYA MENXSHE $2P+2$~BUFEROV. oCHEVIDNO, CHTO ZHELATELXNY DVA BUFERA VYVODA, TAK KAK MY SMOZHEM ZAPISYVATX IZ ODNOGO BUFERA, OBRAZUYA V |TO ZHE VREMYA SLEDUYUSHCHIJ BLOK VYVODA V DRUGOM. pO|TOMU MY MOZHEM VOOBSHCHE NE RASSMATRIVATX VOPROS VYVODA I ZANYATXSYA TOLXKO VVODOM. dOPUSTIM, IMEETSYA $P+Q$~BUFEROV VVODA, GDE $1\le Q\le P$. vOSPOLXZUEMSYA DLYA OPISANIYA NASHEJ SITUACII MODELXYU, PREDLOZHENNOJ l.~dZH.~vUDRAMOM [{\sl IBM Systems J.,\/} {\bf 9} (1970), 118--144]. chTENIE ODNOGO BLOKA LENTY ZANIMAET ODNU EDINICU VREMENI. iMEETSYA VEROYATNOSTX~$p_0$ TOGO, CHTO V TECHENIE |TOGO VREMENI NI ODIN IZ BUFEROV VVODA NE STANET PUSTYM, $p_1$---CHTO ODIN BUFER STANET PUSTYM, $p{\ge 2}$---CHTO DVA ILI BOLXSHE BUFEROV STANUT %%407 PUSTYMI I~T.~D. pO ZAVERSHENII CHTENIYA LENTY MY OKAZYVAEMSYA V ODNOM IZ $Q+1$~SOSTOYANIJ: \medskip {\sl sOSTOYANIE~$0$:\/} $Q$~BUFEROV PUSTY. mY NACHINAEM CHITATX BLOK PODHODYASHCHEGO FAJLA V ODIN IZ NIH, ISPOLXZUYA METOD PROGNOZIROVANIYA, OPISANNYJ RANEE V |TOM PUNKTE. chEREZ ODNU EDINICU VREMENI MY PEREHODIM V SOSTOYANIE~$1$ S VEROYATNOSTXYU~$p_0$, V PROTIVNOM SLUCHAE MY OSTAEMSYA V SOSTOYANII~$0$. {\sl sOSTOYANIE~$1$:\/} $Q-1$~BUFEROV PUSTY. mY NACHINAEM CHITATX V ODIN IZ NIH, PREDSKAZYVAYA PODHODYASHCHIJ FAJL. chEREZ ODNU EDINICU VREMENI MY PEREHODIM V SOSTOYANIE~$2$ S VEROYATNOSTXYU~$p_0$, V SOSTOYANIE~$1$ S VEROYATNOSTXYU~$p_1$ I V SOSTOYANIE~$0$ S VEROYATNOSTXYU~$p_{\ge2}$. $\vdots$ {\sl sOSTOYANIE~$Q-1$:\/} ODIN BUFER PUST. mY NACHINAEM CHITATX V NEGO, PREDSKAZYVAYA PODHODYASHCHIJ FAJL. chEREZ ODNU EDINICU VREMENI MY PEREHODIM V SOSTOYANIE~$Q$ S VEROYATNOSTXYU~$p_0$, V SOSTOYANIE~$Q-1$ S VEROYATNOSTXYU~$p_1$,~\dots, V SOSTOYANIE~$1$ S VEROYATNOSTXYU~$P_{Q-1}$, I V SOSTOYANIE~$0$ S VEROYATNOSTXYU~$p_{\ge Q}$. {\sl sOSTOYANIE~$Q$:\/} VSE BUFERY ZAPOLNENY. chTENIE LENT OSTANAVLIVAETSYA V SREDNEM NA $\mu$~EDINIC VREMENI, I ZATEM MY PEREHODIM V SOSTOYANIE~$1$. \medskip mY NACHINAEM S SOSTOYANIYA~$0$. eTA MODELX SITUACII SOOTVETSTVUET MARKOVSKOMU PROCESSU (SM.~UPR.~2.3.4.2-26), KOTORYJ MOZHNO PROANALIZIROVATX S POMOSHCHXYU PROIZVODYASHCHIH FUNKCIJ SLEDUYUSHCHIM INTERESNYM SPOSOBOM. pUSTX $z$---PROIZVOLXNYJ PARAMETR, I PREDPOLOZHIM, CHTO KAZHDYJ RAZ, KOGDA MY RESHILI CHITATX S LENTY, DELAEM |TO S VEROYATNOSTXYU~$z$, A S VEROYATNOSTXYU~$1-z$ ZAVERSHAEM ALGORITM. pUSTX $g_Q(z)=\sum_{n\ge0} a_n^{(Q)}z^n(1-z)$ BUDET SREDNIM CHISLOM POYAVLENIJ V |TOM PROCESSE SOSTOYANIYA~$Q$; OTSYUDA SLEDUET, CHTO $a_n^{(Q)}$---|TO SREDNEE CHISLO POYAVLENIJ SOSTOYANIYA~$Q$, ESLI BYLO PROCHITANO ROVNO $n$~BLOKOV. tOGDA $n+a_n\mu$---SREDNEE SUMMARNOE VREMYA, ZATRACHENNOE NA VVOD I VYCHISLENIYA. eSLI BY IMELOSX POLNOE SOVMESHCHENIE, KAK V ALGORITME S $(2P+2)$~BUFERAMI, TO SUMMARNOE VREMYA VKLYUCHALO BY TOLXKO $n$~EDINIC, TAK CHTO $a_n\mu$~PREDSTAVLYAET VREMYA ZADERZHKI CHTENIYA. pUSTX $A_{ij}$---VEROYATNOSTX TOGO, CHTO MY PEREHODIM IZ SOSTOYANIYA~$i$ V SOSTOYANIE~$j$ V |TOM PROCESSE PRI~$0\le i$, $j\le Q+1$, GDE $Q+1$---NOVOE SOSTOYANIE "OSTANOVKI". nAPRIMER, DLYA $Q=1$, $2$, $3$ MATRICY~$A$ BUDUT SLEDUYUSHCHIMI: %%407 $$ \eqalign{ Q&=1:\pmatrix{ p_{\ge1}z & p_0z & 1-z\cr 1 & 0 & 0\cr 0 & 0 & 0\cr },\cr Q&=2:\pmatrix{ p_{\ge1}z & p_0z & 0 & 1-z\cr p_{\ge2}z & p_1z & p_0z& 1-z\cr 0 & 1 & 0 & 0 \cr 0 & 0 & 0 & 0\cr },\cr Q&=3:\pmatrix{ p_{\ge1}z & p_0z & 0 & 0 & 1-z\cr p_{\ge2}z & p_1z & p_0z& 0 & 1-z\cr p_{\ge3}z & p_2z & p_1z& p_0z & 1-z\cr 0 & 0 & 1 & 0 & 0\cr 0 & 0 & 0& 0 & 0 \cr }.\cr } $$ iZ UPR.~2.3.4.2-26b IMEEM, CHTO $g_Q(z) =\hbox{ ALGEBRAICHESKOE DOPOLNENIE $Q_0$} (I-A)/\det (I-A)$. tAK, NAPRIMER, ESLI $Q=1$, IMEEM $$ \eqalign{ g_1(z)&=\det\pmatrix{ 0 & -p_0z & z-1\cr 1 & 0 & 0 \cr 0 & 0 & 1\cr }/ \det\pmatrix{ 1-p_{\ge1}z & -p_0z & z-1\cr -1 & 1 & 0\cr 0& 0 & 1\cr }=\cr &={p_0z\over 1-p_1z-p_0z}={p_0z\over1-z}=\sum_{n\ge0} np_0z^n(1-z),\cr } $$ TAK CHTO $a_n^{(1)}=np_0$. eTO, KONECHNO, OCHEVIDNO ZARANEE, TAK KAK PRI $Q=1$ ZADACHA OCHENX PROSTA. aNALOGICHNOE VYCHISLENIE DLYA $Q=2$ (SM.~UPR.~14) DAET MENEE OCHEVIDNUYU FORMULU: $$ a_n^{(2)}={p_0^2n\over 1-p_1}-{p_0^2(1-p_1^n)\over(1-p_1)^2}. \eqno(10) $$ v OBSHCHEM SLUCHAE MOZHNO POKAZATX, CHTO $a_n^{(Q)}$ IMEET VID~$\alpha^{(Q)}n+O(1)$ PRI $n\to\infty$, GDE KONSTANTU~$\alpha^{(Q)}$ NE SLISHKOM TRUDNO VYCHISLITX. (sM. UPR.~15.) kAK OKAZYVAETSYA, $\alpha^{(3)}=p_0^3/((1-p_1)^2-p_0p_2)$. iSHODYA IZ PRIRODY SLIYANIYA, DOVOLXNO RAZUMNO PREDPOLOZHITX, CHTO $\mu=1/P$ I CHTO VEROYATNOSTI~$p_k$ SOOTVETSTVUYUT BINOMIALXNOMU RASPREDELENIYU $$ p_k=\perm{P}{k}\perm{1}{P}^k{\left({P-1\over P}\right)\hbox to 0pt{.\hss}}^{P-k} $$ nAPRIMER, ESLI $P=5$, TO $p_0= .32768$, $p_1=.4096$, $p_2= .2048$, $p_3=.0512$, $p_4=.0064$ I~$p_5=.00032$; SLEDOVATELXNO, $\alpha^{(1)}=0.328$, $\alpha^{(2)}=0.182$ I~$\alpha^{(3)}=0.127$. dRUGIMI SLOVAMI, ESLI MY ISPOLXZUEM $5+3$~VVODNYH BUFEROV VMESTO~$5+5$, TO MOZHNO OZHIDATX DOPOLNITELXNOGO VREMENI ZADERZHKI CHTENIYA PORYADKA~$0.127/5\approx 2.5\%$. %% 409 kONECHNO, |TA MODELX---TOLXKO OCHENX GRUBOE PRIBLIZHENIE. mY ZNAEM, CHTO PRI $Q=P$ VOOBSHCHE NET VREMENI ZADERZHKI, NO ESLI SUDITX PO MODELI, TO ESTX. dOPOLNITELXNOE VREMYA ZADERZHKI CHTENIYA DLYA MENXSHIH~$Q$ POCHTI TOCHNO URAVNOVESHIVAET VYIGRYSH V NAKLADNYH RASHODAH, POLUCHAEMYJ OT ISPOLXZOVANIYA BOLEE KRUPNYH BLOKOV, TAK CHTO PROSTAYA SHEMA S $Q=P$ KAZHETSYA OPRAVDANNOJ. \excercises \ex[13] vYVEDITE FORMULU DLYA TOCHNOGO CHISLA LITER NA LENTE, ESLI KAZHDYJ BLOK SODERZHIT $n$~LITER. sCHITAJTE, CHTO LENTA MOGLA BY VMESTITX ROVNO 23000000 LITER, ESLI BY NE BYLO MEZHBLOCHNYH PROMEZHUTKOV. \ex[15] oB®YASNITE, POCHEMU PERVYJ BUFER FAJLA~$2$ V STROKE~$6$ RIS.~84 SOVSEM PUST. \ex[20] bUDET LI ALGORITM~F RABOTATX DOLZHNYM OBRAZOM, ESLI VMESTO $2P$~BUFEROV VVODA IMEETSYA TOLXKO $2P-1$? eSLI DA, DOKAZHITE |TO, ESLI NET--- PRIVEDITE PRIMER, KOGDA ALGORITM TERPIT NEUDACHU. \ex[20] kAK IZMENITX ALGORITM~F, CHTOBY ON RABOTAL TAKZHE I PRI~$P=1$? \rex[21] eSLI V RAZLICHNYH FAJLAH IMEYUTSYA RAVNYE KLYUCHI, NEOBHODIMO V PROCESSE PROGNOZIROVANIYA DEJSTVOVATX OCHENX AKKURATNO. oB®YASNITE, POCHEMU, I POKAZHITE, KAK IZBEZHATX TRUDNOSTEJ, ESLI BOLEE STROGO OPREDELITX OPERACII SLIYANIYA I PROGNOZIROVANIYA V ALGORITME~F. \ex[22] kAKIE IZMENENIYA SLEDUET SDELATX V ALGORITME~5.4.3s, CHTOBY PREOBRAZOVATX EGO V ALGORITM KASKADNOGO SLIYANIYA \emph{S SOVMESHCHENIEM PEREMOTKI} NA $T+1$~LENTAH? \rex [26] nACHALXNOE RASPREDELENIE V PRIMERE~7 SHEMY~a POROZHDAET $$ (A_1D_1)^{11}\quad D_1(A_1D_1)^{10}\quad D_1(A_1D_1)^9\quad D_1(A_1D_1)^7 $$ NA LENTAH~1--4, GDE $(A_1D_1)^7$ OZNACHAET $A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1A_1D_1$. pOKAZHITE, KAK VSTAVITX DOPOLNITELXNYE OTREZKI~$A_0$ I~$D_0$ NAILUCHSHIM IZ VOZMOZHNYH SPOSOBOV (V TOM SMYSLE, CHTO OBSHCHEE CHISLO OBRABATYVAEMYH VO VREMYA SLIYANIYA NACHALXNYH OTREZKOV BUDET MINIMALXNYM), CHTOBY PRIVESTI RASPREDELENIE K $$ A(DA)^{14}\quad (DA)^{28}\quad (DA)^{26}\quad (DA)^{22}. $$ [\emph{uKAZANIE.} chTOBY SOHRANITX CHETNOSTX, NEOBHODIMO VSTAVLYATX~$A_0$ I~$D_0$ V VIDE SOSEDNIH PAR. chISLA SLIYANIYA DLYA KAZHDOGO NACHALXNOGO OTREZKA MOGUT BYTX PODSCHITANY, KAK V UPR~5.4.4-5; ZDESX POYAVLYAETSYA NEKOTOROE UPROSHCHENIE, TAK KAK SOSEDNIE OTREZKI VSEGDA IMEYUT SOSEDNIE CHISLA SLIYANIYA.] \ex[20] iZ SHEMY~a VIDNO, CHTO BOLXSHINSTVO SHEM NACHALXNOGO RASPREDELENIYA OTREZKOV (ZA ISKLYUCHENIEM NACHALXNOGO RASPREDELENIYA DLYA KASKADNOGO SLIYANIYA) IMEET TENDENCIYU POMESHCHATX POSLEDOVATELXNYE OTREZKI NA RAZLICHNYE LENTY. eSLI BY POSLEDOVATELXNYE OTREZKI POPALI NA ODNU LENTU, TO MY MOGLI BY S|KONOMITX STARTSTOPNOE VREMYA; MOZHNO LI PO|TOMU SCHITATX HOROSHEJ MYSLX IZMENITX ALGORITMY RASPREDELENIYA TAK, CHTOBY ONI REZHE PEREKLYUCHALI LENTY? \rex[22] oCENITE, SKOLXKO VREMENI ZANYAL BY MNOGOFAZNYJ ALGORITM S OBRATNYM CHTENIEM IZ SHEMY~a, ESLI BY MY ISPOLXZOVALI DLYA SORTIROVKI VSE $T=6$ LENT, A NE $T=5$, KAK V PRIMERE~7. bYLO LI RAZUMNO IZBEGATX ISPOLXZOVANIYA VVODNOJ LENTY? \ex[m23] iSPOLXZUYA ANALIZ, PROVEDENNYJ V P.~5.4.2 I~5.4.3, POKAZHITE, CHTO DLINA KAZHDOJ PEREMOTKI VO VREMYA STANDARTNOGO MNOGOFAZNOGO SLIYANIYA S SHESTXYU LENTAMI ILI KASKADNOGO SLIYANIYA REDKO PREVYSHAET 54\% FAJLA (ISKLYUCHAYA NACHALXNUYU I KONECHNUYU PEREMOTKI, KOTORYE OHVATYVAYUT VESX FAJL). %%410 \ex[23] iZMENIV PODHODYASHCHIE |LEMENTY TABL.~1, OCENITE, SKOLXKO VREMENI ZANYALI BY PERVYE DEVYATX PRIMEROV SHEMY~a, ESLI BY MY IMELI DVUHSKOROSTIUYU PEREMOTKU (BYSTRUYU I MEDLENNUYU) sCHITAJTE, CHTO $p=1$, ESLI LENTA ZAPOLNENA MENXSHE CHEM NA ODNU CHETVERTX, A DLYA BOLEE ZAPOLNENNOJ LENTY VREMYA PEREMOTKI RAVNO PRIBLIZITELXNO PYATI SEKUNDAM PLYUS TO VREMYA, KOTOROE POLUCHILOSX BY PRI $\rho=1/5$ iZMENITE PRIMER~8 TAK, CHTOBY ON ISPOLXZOVAL KASKADNOE SLIYANIE S KOPIROVANIEM, POSKOLXKU PEREMETKA I PRYAMOE CHTENIE V |TOM SLUCHAE MEDLENNEE KOPIROVANIYA [\emph{uKAZANIE:} ISPOLXZUJTE REZULXTAT UPR. 10 ] \ex[40] rASSMOTRIM RAZBIENIE SHESTI LENT NA TRI PARY LENT, GDE KAZHDAYA PARA IGRAET ROLX ODNOJ LENTY V MNOGOFAZNOM SLIYANII S~$T=3$ oDNA LENTA KAZHDOJ PARY BUDET SODERZHATX BLOKI~$1$, $3$, $5$,~\dots, A DRUGAYA---BLOKI~$2$, $4$, $6$,~\dots, TAKIM SPOSOBOM MY, PO SUSHCHESTVU, DOBIVAEMSYA TOGO, CHTOBY VO VSE VREMYA SLIYANIYA DVE VVODNYE I DVE VYVODNYE LENTY OSTAVALISX AKTIVNYMI, PRICHEM |FFEKTIVNAYA SKOROSTX SLIYANIYA UDVAIVAETSYA \item{(a)} nAJDITE PODHODYASHCHIJ SPOSOB RASPROSTRANITX ALGORITM~F NA |TOT SLUCHAJ. \item{(b)} oCENITE OBSHCHEE VREMYA VYPOLNENIYA, KOTOROE POLUCHILOSX BY, ESLI BY |TOT METOD BYL ISPOLXZOVAN DLYA SORTIROVKI 100000~ZAPISEJ PO 100~LITER, RASSMOTREV SLUCHAJ KAK PRYAMOGO, TAK I OBRATNOGO CHTENIYA. \ex[20] mOZHET LI OSCILLIRUYUSHCHAYA SORTIROVKA S PYATXYU LENTAMI, V TOM VIDE KAK ONA OPREDELENA V ALGORITME 5.4.5v, ISPOLXZOVATXSYA DLYA SORTIROVKI CHETYREH POLNYH BOBIN ISHODNYH DANNYH DO MOMENTA OKONCHATELXNOGO SLIYANIYA? \ex[m19] vYVEDITE (10). \ex[vm29] dOKAZHITE, CHTO $g_Q(z)=h_Q(z)/(1-z)$, GDE $h_Q(z)$~YAVLYAETSYA RACIONALXNOJ FUNKCIEJ~$z$, NE IMEYUSHCHEJ OSOBENNOSTEJ VNUTRI EDINICHNOGO KRUGA; SLEDOVATELXNO, $a_n^{(Q)}=h_Q(1)n+O(1)$ PRI $n\to\infty$. v CHASTNOSTI, POKAZHITE, CHTO $$ h_3(1)=\det\pmatrix{ 0 & -p_0 & 0 & 0 \cr 0 & 1-p_1 & -p_0 & 0 \cr 0 & -p_2 & 1-p_1 & -p_0 \cr 1 & 0 & 0 & 0 \cr } /\det\pmatrix{ 1 & -p_0 & 0 & 0 \cr 1 & 1-p_1 & -p_0 & 0 \cr 1 & -p_2 & 1-p_1 & -p_0\cr 0 & 0 & -1 & 1 \cr }. $$ \ex[M46] pROANALIZIRUJTE SLIYANIE S $P+Q$~BUFERAMI BOLEE TSHCHATELXNO, CHEM |TO BYLO SDELANO V TEKSTE, ISPOLXZUYA BOLEE TOCHNUYU MODELX. \ex[41] pROVEDITE DETALXNOE IZUCHENIE ZADACHI SORTIROVKI 100000~ZAPISEJ YAO 100~LITER, NARISUJTE SHEMY, PODOBNYE SHEME~a, V PREDPOLOZHENII, CHTO IMEETSYA~3, 4 ILI~5 LENT \subsubchap{*vNESHNYAYA PORAZRYADNAYA SORTIROVKA} %5.4.7 v PREDYDUSHCHIH PUNKTAH MY RASSMOTRELI PROCESS LENTOCHNOJ SORTIROVKI SLIYANIEM; NO SUSHCHESTVUET I DRUGOJ SPOSOB SORTIROVKI NA LENTAH, OSNOVANNYJ NA PRINCIPE PORAZRYADNOJ SORTIROVKI, ISPOLXZUEMOJ V MEHANICHESKIH SORTIROVALXNYH MASHINAH DLYA PERFOKART (SR. S P.~5.2.5). eTOT METOD INOGDA NAZYVAYUT RASPREDELYAYUSHCHEJ SORTIROVKOJ, POKOLONNOJ SORTIROVKOJ, KARMANNOJ SORTIROVKOJ, CIFROVOJ SORTIROVKOJ, SORTIROVKOJ RAZDELENIEM I T. D. oN, KAK OKAZYVAETSYA, PO SUSHCHESTVU, \emph{PROTIVOPOLOZHEN} SLIYANIYU! pREDPOLOZHIM, NAPRIMER, CHTO V NASHEM RASPORYAZHENII IMEYUTSYA CHETYRE LENTY, A KLYUCHEJ MOZHET BYTX TOLXKO VOSEMX: $0$, $1$, $2$, $3$, %%411 $4$, $5$, $6$, $7$. eSLI ISHODNYE DANNYE NAHODYATSYA NA LENTE~$T1$, TO NACHNEM S PEREPISI VSEH CHETNYH KLYUCHEJ NA~$T3$ I VSEH NECHETNYH NA~$T4$: \ctable{ \hfill#&&\bskip\hfill$#$\hfill\bskip\cr & T1 & T2 & T3 & T4 \cr dANO & \{0, 1, 2, 3, 4, 5, 6, 7\} & - & - & - \cr pROHOD 1& - & - & \{0, 2, 4, 6\} & \{1, 3, 5, 7\}\cr \noalign{ \noindent tEPERX PEREMATYVAEM LENTY I CHITAEM~$T3$, A ZATEM ~$T4$, POMESHCHAYA $\{0, 1, 4, 5\}$ NA~$T1$ I~$\{2, 3, 6, 7\}$ NA~$T2$: } pROHOD 2. & \{0,4\} \{1,5\} & \{2,6\} \{3,7\} & - &- \cr \noalign{ \noindent(sTROKA~$\{0, 4\}\{1, 5\}$ OBOZNACHAET FAJL, SODERZHASHCHIJ ZAPISI TOLXKO S KLYUCHAMI~$0$ I~$4$, ZA KOTORYMI SLEDUYUT ZAPISI TOLXKO S KLYUCHAMI~$1$ I~$5$. zAMETIM, CHTO~$T1$ TEPERX SODERZHIT TE KLYUCHI, SREDNIJ DVOICHNYJ RAZRYAD KOTORYH SODERZHIT~$0$.) pOSLE ESHCHE ODNOJ PEREMOTKI I RASPREDELENIYA KLYUCHEJ~$0$, $1$, $2$, $3$ NA~$T3$ I KLYUCHEJ~$4$, $5$, $6$, $7$ NA~$T4$ MY IMEEM } pROHOD~3 & - & & \{0\}\{1\}\{2\}\{3\} & \{4\} \{5\} \{6\} \{7\} \cr } tEPERX KOPIROVANIE~$T4$ V KONEC~$T3$ ZAVERSHAET RABOTU. v OBSHCHEM SLUCHAE DLYA KLYUCHEJ V DIAPAZONE OT~$0$ DO~$2^k-1$ MOZHNO OTSORTIROVATX FAJL ANALOGICHNYM OBRAZOM, ISPOLXZOVAV $k$~PROHODOV, ZA KOTORYMI SLEDUET FAZA OKONCHATELXNOJ "SBORKI", KOPIRUYUSHCHAYA PRIMERNO POLOVINU DANNYH S ODNOJ LENTY NA DRUGUYU. iMEYA SHESTX LENT, MY MOZHEM ANALOGICHNYM OBRAZOM ISPOLXZOVATX PREDSTAVLENIYA PO OSNOVANIYU~$3$ DLYA SORTIROVKI KLYUCHEJ OT~$0$ DO~$3^k-1$ ZA $k$~PROHODOV. iSPOLXZUYUTSYA TAKZHE METODY S CHASTICHNYMI PROHODAMI. pREDPOLOZHIM, NAPRIMER, CHTO DOPUSKAETSYA DESYATX KLYUCHEJ $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, I RASSMOTRIM SLEDUYUSHCHUYU PROCEDURU, PRINADLEZHASHCHUYU r.~l.~eSHENHERSTU [{\sl Theory of Switching,\/} {\bf 7} (Harvard Univ. Comp. Laboratory: May, 1954), I.1--I.76]: \ctable{ \hfill# &\bskip\hfill$#$\hfill\bskip &\bskip\hfill$#$\hfill\bskip &\bskip\hfill$#$\hfill\bskip &\bskip\hfill$#$\hfill\bskip &\bskip#\hfill\cr & T1 & T2 & T3 & T4 \cr dANO & \{0, 1,~\ldots, 9\} & - & - & - \cr pROHOD~1.& - & \{0, 2, 4, 7\} & \{1, 5, 6\} & \{3, 8, 9\} & $1.0$~PROHOD \cr pROHOD~2.& \{0\} & - & \{1, 5, 6\}\{2,7\} & \{3,8,9\}\{4\} &$0.4$~PROHODA\cr pROHOD~3.& \{0\}\{1\}\{2\} & \{6\}\{7\} & - & \{3,8,9\}\{4\}\{5\}& $0.5$~PROHODA\cr pROHOD~4. & \{0\}\{1\}\{2\}\{3\} & \{6\}\{7\}\{8\} & \{9\} &\{4\}\{5\}& $0.3$~PROHODA\cr sBORKA & \{0\}\{1\}\{2\}\{3\}\{4\}\ldots\{9\} & & & & $0.6$~PROHODA\cr & & & & & $\overline{\hbox{$2.8$ PROHODA}}$\cr } %%412 eSLI KAZHDOE ZNACHENIE KLYUCHA VSTRECHAETSYA PRIMERNO V ODNOJ DESYATOJ SLUCHAEV, TO |TA PROCEDURA DLYA SORTIROVKI DESYATI KLYUCHEJ ZATRACHIVAET TOLXKO $2.8$~PROHODA, V TO VREMYA KAK PERVYJ PRIMER TREBUET $3.5$~PROHODA DLYA SORTIROVKI VSEGO VOSXMI KLYUCHEJ. tAKIM OBRAZOM, MY VIDIM, CHTO ISKUSNAYA SHEMA RASPREDELENIYA MOZHET VYZVATX ZNACHITELXNOE RAZLICHIE DLYA PORAZRYADNOJ SORTIROVKI TOCHNO TAK ZHE, KAK DLYA SLIYANIYA. sHEMY RASPREDELENIYA PREDYDUSHCHIH PRIMEROV PREDSTAVIM, KAK I OBYCHNO, DREVOVIDNYMI STRUKTURAMI: \picture{RIS. NA STR. 412} kRUGLYE VNUTRENNIE UZLY |TIH DEREVXEV ZANUMEROVANY~$1$, $2$, $3$,~\dots V SOOTVETSTVII S SHAGAMI PROCESSA~$1$, $2$, $3$,~\dots. iMENA LENT~$A$, $B$, $C$, $D$ (VMESTO $T1$, $T2$, $T3$, $T4$) POMESHCHENY RYADOM S REBRAMI DEREVA, CHTOBY UKAZATX, KUDA POPADAYUT ZAPISI. kVADRATNYE VNESHNIE UZLY IZOBRAZHAYUT CHASTI FAJLA, SODERZHASHCHIE TOLXKO ODIN KLYUCH, I |TOT KLYUCH IZOBRAZHEN ZHIRNYM SHRIFTOM POD SOOTVETSTVUYUSHCHIM UZLOM. rEBRA NAD KVADRATNYMI UZLAMI VSE POMECHENY IMENEM VYVODNOJ LENTY ($C$ V PERVOM PRIMERE, $A$ VO VTOROM). tAKIM OBRAZOM, SHAG~3 PRIMERA~1 SOSTOIT IZ CHTENIYA S LENTY~$D$ I ZAPISI KLYUCHEJ~$1$ I~$5$ NA LENTU~$A$ I KLYUCHEJ~$3$ I~$7$ NA LENTU~$B$. nETRUDNO VIDETX, CHTO CHISLO VYPOLNYAEMYH PROHODOV RAVNO \emph{DLINE VNESHNEGO PUTI} DEREVA, DELENNOJ NA CHISLO VNESHNIH UZLOV, ESLI MY PRINIMAEM, CHTO VSE KLYUCHI RAVNOVEROYATNY. v SILU POSLEDOVATELXNOJ PRIRODY LENTY I DISCIPLINY "PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA", KOTOROJ PODCHINYAETSYA PRYAMOE CHTENIE, NELXZYA VZYATX ZA OSNOVU SHEMY RASPREDELENIYA \emph{LYUBOE} POMECHENNOE DEREVO. v DEREVE PRIMERA~1 DANNYE ZAPISYVAYUTSYA NA LENTU~$A$ NA SHAGE~2 I SHAGE~3; DANNYE, ZAPISANNYE V TECHENIE SHAGA~2, NEOBHODIMO ISPOLXZOVATX RANXSHE DANNYH, ZAPISANNYH V TECHENIE SHAGA~3. v OBSHCHEM SLUCHAE, ESLI MY ZAPISYVAEM NA LENTU V TECHENIE SHAGOV~$i$ I~$j$, GDE $i < j$, PERVYMI SLEDUET %%413 ISPOLXZOVATX DANNYE, ZAPISANNYE V TECHENIE SHAGA~$i$; ESLI DEREVO SODERZHIT DVE VETVI VIDA \picture{RIS. STR. 413} TO DOLZHNO VYPOLNYATXSYA USLOVIE $k