\input style \chapnotrue\chapno=5\subchno=4\subsubchno=5 \subsubchap{pRAKTICHESKIE ASPEKTY SLIYANIYA NA LENTAH} % 5.4.6 zDESX VSPLYVAYUT RAZNYE MELOCHI. pOSLE TOGO KAK MY OBSUDILI RAZLICHNYE SEMEJSTVA SHEM SLIYANIYA, SAMOE VREMYA POSMOTRETX, KAK ONI OTOBRAZHAYUTSYA NA REALXNYE KONFIGURACII evm I MAGNITNYH LENT, I SRAVNITX RAZUMNYM OBRAZOM |TI SHEMY. iZUCHENIE VNUTRENNEJ SORTIROVKI POKAZALO, CHTO NEVOZMOZHNO ADEKVATNO OCENITX |FFEKTIVNOSTX METODA SORTIROVKI, PROSTO PODSCHITYVAYA CHISLO VYPOLNYAEMYH IM SRAVNENIJ; PODOBNO |TOMU, MY NE MOZHEM PRAVILXNO OCENITX METOD VNESHNEJ SORTIROVKI, PROSTO VYYASNYAYA CHISLO VYPOLNYAEMYH IM PROHODOV PO DANNYM. v |TOM PUNKTE MY RASSMOTRIM HARAKTERISTIKI TIPICHNYH LENTOCHNYH USTROJSTV I IH VLIYANIE NA NACHALXNOE RASPREDELENIE I SLIYANIE. v CHASTNOSTI, IZUCHIM NESKOLXKO SHEM RASPREDELENIYA BUFEROV I IH VOZDEJSTVIE NA VREMYA SCHETA. bUDET TAKZHE VKRATCE RASSMOTRENA KONSTRUKCIYA PROGRAMM-GENERATOROV SORTIROVKI. \section kAK RABOTAET LENTA. v HARAKTERISTIKAH LENTOCHNYH USTROJSTV, PROIZVODIMYH RAZNYMI IZGOTOVITELYAMI, IMEYUTSYA ZNACHITELXNYE RAZLICHIYA. oPREDELIM DLYA UDOBSTVA GIPOTETICHESKOE LENTOCHNOE USTROJSTVO~\MIXT, DOSTATOCHNO TIPICHNOE DLYA OBORUDOVANIYA TOGO VREMENI, KOGDA BYLA NAPISANA |TA KNIGA. iZUCHIV, KAK POSTROITX ALGORITM SORTIROVKI DLYA LENT~\MIXT, VY LUCHSHE POJMETE, KAK OBRASHCHATXSYA S DRUGIMI KONKRETNYMI LENTOCHNYMI USTROJSTVAMI. \MIXT{} CHITAET ILI ZAPISYVAET 800~LITER NA DYUJM LENTY SO SKOROSTXYU 75~DYUJMOV V SEKUNDU. eTO OZNACHAET, CHTO ODNA LITERA CHITAETSYA ILI ZAPISYVAETSYA V TECHENIE~1/60~MS, T.~E.~$16{2\over3}$~MKS, ESLI LENTA NAHODITSYA V AKTIVNOM SOSTOYANII. [rEALXNYE LENTOPROTYAZHNYE USTROJSTVA, SHIROKO RASPROSTRANENNYE V NASTOYASHCHEE VREMYA, IMEYUT PLOTNOSTX V DIAPAZONE OT~200 DO~1600 LITER NA DYUJM I SKOROSTX V DIAPAZONE OT~$37{1\over2}$ DO~$150$~DYUJMOV V SEKUNDU, TAK CHTO IH |FFEKTIVNAYA SKOROSTX V SRAVNENII S \MIXT{} IZMENYAETSYA V DIAPAZONE OT~$1\over8$ DO~4. s PRAKTICHESKOJ TOCHKI ZRENIYA BOLXSHOJ OB®EM SORTIROVKI VYPOLNYAETSYA V KOMMERCHESKIH SISTEMAH NA OTNOSITELXNO NEBOLXSHOM I NEDOROGOM OBORUDOVANII, KOTOROE MEDLENNEE, CHEM RASSMATRIVAEMOE ZDESX. s DRUGOJ STORONY, LENTOPROTYAZHNYE USTROJSTVA VSKORE MOGUT REZKO IZMENITXSYA, CHTO SDELAET NASTOYASHCHIE PREDPOLOZHENIYA USTAREVSHIMI. nASHA OSNOVNAYA CELX SOSTOIT NE V POLUCHENII KONKRETNYH OTVETOV, A V TOM, CHTOBY NAUCHITXSYA RAZUMNO SOCHETATX TEORIYU S PRAKTIKOJ.] oDNO IZ VAZHNYH SOOBRAZHENIJ, KOTOROE NADO IMETX V VIDU, SOSTOIT V TOM, CHTO LENTY IMEYUT KONECHNUYU DLINU. kAZHDAYA BOBINA %%379 SODERZHIT 2400~FUTOV LENTY ILI MENXSHE; SLEDOVATELXNO, NA ODNOJ BOBINE LENTY \MIXT{} ESTX MESTO DLYA SAMOE BOLXSHEE PRIMERNO $23\,000\,000$~LITER, I, CHTOBY PROCHESTX IH VSE, TREBUETSYA OKOLO $23\,000\,000/3\,600\,000\approx 6.4$~MIN. eSLI TREBUETSYA SORTIROVATX BOLXSHIJ FAJL, TO OBYCHNO LUCHSHE VSEGO SORTIROVATX ZA ODIN RAZ ODNU POLNUYU BOBINU I ZATEM SLITX OTDELXNYE OTSORTIROVANNYE BOBINY S CELXYU IZBEZHATX IZBYTOCHNOJ RABOTY PO USTANOVKE LENT. eTO OZNACHAET, CHTO CHISLO NACHALXNYH OTREZKOV~$S$, REALXNO PRISUTSTVUYUSHCHIH V SHEMAH SLIYANIYA, KOTORYE MY IZUCHALI, NIKOGDA NE BUDET OCHENX BOLXSHIM. mY NIKOGDA NE STOLKNEMSYA SO \picture{rIS.~79. mAGNITNAYA LENTA S BLOKAMI PEREMENNOJ DLINY.} SLUCHAEM~$S>5000$ DAZHE PRI OCHENX MALENXKOJ VNUTRENNEJ PAMYATI, PROIZVODYASHCHEJ NACHALXNYE OTREZKI DLINOJ TOLXKO V 5000~LITER. sLEDOVATELXNO, FORMULY, DAYUSHCHIE ASIMPTOTICHESKUYU |FFEKTIVNOSTX ALGORITMOV PRI~$S\to\infty$, IMEYUT GLAVNYM OBRAZOM AKADEMICHESKIJ INTERES. dANNYE HRANYATSYA NA LENTE V VIDE \emph{BLOKOV} (RIS.~79), I KAZHDAYA INSTRUKCIYA CHTENIYA/ZAPISI PEREDAET ODIN BLOK. bLOKI CHASTO NAZYVAYUTSYA "ZAPISYAMI", NO MY BUDEM IZBEGATX |TOGO TERMINA, CHTOBY NE PUTATX EGO S "ZAPISYAMI" FAJLA, KOTORYE UCHASTVUYUT V SORTIROVKE. dLYA MNOGIH RANNIH PROGRAMM SORTIROVKI, NAPISANNYH V 50-H GODAH, |TO RAZLICHIE BYLO NEOBYAZATELXNYM, TAK KAK V ODNOM BLOKE HRANILASX ODNA ZAPISX; NO MY UVIDIM, CHTO OB®EDINENIE NESKOLXKIH ZAPISEJ V ODNOM BLOKE NA LENTE OBYCHNO DAET OPREDELENNYE PREIMUSHCHESTVA. sOSEDNIE BLOKI RAZDELYAYUTSYA \emph{MEZHBLOCHNYMI PROMEZHUTKAMI} DLINOJ PO 480~LITER, CHTO POZVOLYAET LENTE OSTANOVITXSYA ILI RAZOGNATXSYA MEZHDU OTDELXNYMI KOMANDAMI CHTENIYA ILI ZAPISI. mEZHBLOCHNYE PROMEZHUTKI PRIVODYAT K UMENXSHENIYU CHISLA LITER NA ODNOJ BOBINE, LENTY, ZAVISYASHCHEMU OT CHISLA LITER V ODNOM BLOKE (RIS.~80); V TOJ ZHE STEPENI UMENXSHAETSYA KOLICHESTVO LITER, PEREDAVAEMYH ZA SEKUNDU, TAK KAK LENTA DVIZHETSYA S POSTOYANNOJ SKOROSTXYU. mNOGIE "USTAREVSHIE" MODELI evm IMEYUT FIKSIROVANNYE I VESXMA MALYE RAZMERY BLOKA. nAPRIMER, \MIX, KAK ONA OPISANA V GL.~1, VSEGDA CHITAET I PISHET BLOKI PO 100~SLOV, TAKIM OBRAZOM, |TO SOSTAVLYAET PRIMERNO 500~LITER NA BLOK I 480~LITER NA %%380 PROMEZHUTOK, T.~E.\ POCHTI POLOVINA LENTY PROPADAET! sEJCHAS BOLXSHAYA CHASTX MASHIN DOPUSKAYUT PEREMENNYJ RAZMER BLOKA, I PO|TOMU NIZHE MY OBSUDIM PROBLEMU VYBORA PODHODYASHCHEGO RAZMERA BLOKA. \picture{rIS.~80. chISLO LITER NA ODNOJ BOBINE LENTY \MIXT{} KAK FUNKCIYA OT RAZMERA BLOKA.} v KONCE OPERACII CHTENIYA ILI ZAPISI LENTA PROHODIT S POLNOJ SKOROSTXYU OKOLO 66~PERVYH LITER MEZHBLOCHNOGO PROMEZHUTKA. eSLI V |TO VREMYA BUDET INICIIROVANA SLEDUYUSHCHAYA OPERACIYA DLYA |TOJ ZHE LENTY, TO DVIZHENIE LENTY PRODOLZHITSYA BEZ PERERYVA. nO ESLI SLEDUYUSHCHAYA OPERACIYA NE NACHNETSYA DOSTATOCHNO BYSTRO, \picture{ rIS.~81. kAK VYCHISLITX VREMYA STARTSTOPNOJ ZADERZHKI. (oNO DOBAVLYAETSYA KO VREMENI, ISPOLXZUEMOMU PRI CHTENII ILI ZAPISI BLOKOV I PROMEZHUTKOV.) } TO LENTA OSTANOVITSYA I K TOMU ZHE POTREBUETSYA NEKOTOROE VREMYA, CHTOBY RAZOGNATX EE DO POLNOJ SKOROSTI V SLEDUYUSHCHEJ OPERACII. sUMMARNAYA STARTSTOPNAYA ZADERZHKA SOSTAVLYAET 5~MS, 2~DLYA OSTANOVKI I~3 DLYA RAZGONA (RIS.~81). tAKIM OBRAZOM, ESLI MY NE %%381 PODDERZHIVAEM NEPRERYVNOGO, BEZOSTANOVOCHNOGO DVIZHENIYA LENTY S POLNOJ SKOROSTXYU, TO |FFEKT VO VREMENI SCHETA BUDET, V SUSHCHNOSTI, TAKOJ ZHE, KAK ESLI BY V MEZHBLOCHNOM PROMEZHUTKE BYLO 780~LITER VMESTO~480. rASSMOTRIM TEPERX OPERACIYU \emph{PEREMOTKI.} k SOZHALENIYU, OBYCHNO TRUDNO TOCHNO OHARAKTERIZOVATX VREMYA, TREBUEMOE DLYA PEREMOTKI LENTY NA ZADANNOE CHISLO LITER~$n$. nA NEKOTORYH MASHINAH IMEETSYA "BYSTRAYA PEREMOTKA", KOTORAYA PRIMENYAETSYA, TOLXKO ESLI $n$~PREVYSHAET CHISLO PORYADKA 5~MILLIONOV; DLYA MENXSHIH ZNACHENIJ~$n$ PEREMOTKA PROISHODIT S NORMALXNOJ SKOROSTXYU CHTENIYA/ZAPISI. \picture{ rIS.~82. pRIBLIZITELXNOE VREMYA SCHETA PRI DVUH OBYCHNO ISPOLXZUEMYH METODAH PEREMOTKI. } nA DRUGIH MASHINAH IMEETSYA SPECIALXNYJ MOTOR, ISPOLXZUEMYJ VO VSEH OPERACIYAH PEREMOTKI; ON POSTEPENNO USKORYAET BOBINU LENTY DO OPREDELENNOGO CHISLA OBOROTOV V MINUTU, A ZATEM TORMOZIT EE, KOGDA PODHODIT VREMYA OSTANOVKI; DEJSTVITELXNAYA SKOROSTX LENTY V |TOM SLUCHAE ZAVISIT OT ZAPOLNENNOSTI BOBINY. mY PRIMEM DLYA PROSTOTY, CHTO \MIXT{} TREBUET $\max (30, n/150)$~MS DLYA PEREMOTKI NA $n$~LITERNYH POZICIJ (VKLYUCHAYA PROMEZHUTKI), T.~E.\ PRIMERNO DVE PYATYH TOGO, CHTO TREBUETSYA DLYA IH CHTENIYA/ZAPISI. eTO DOSTATOCHNO HOROSHEE PRIBLIZHENIE K POVEDENIYU MNOGIH REALXNYH USTROJSTV, GDE OTNOSHENIE VREMENI CHTENIYA/ZAPISI KO VREMENI PEREMOTKI OBYCHNO ZAKLYUCHENO MEZHDU~2 I~3, NO ONO NE DAET ADEKVATNOJ MODELI |FFEKTA KOMBINIROVANNOJ NORMALXNOJ I BYSTROJ PEREMOTKI, IMEYUSHCHEJSYA NA MNOGIH DRUGIH MASHINAH (RIS.~82). pRI PERVONACHALXNOJ USTANOVKE I/ILI PEREMOTKE K NACHALU LENTA, POMESHCHAETSYA V TOCHKU ZAGRUZKI, I DLYA LYUBOJ OPERACII CHTENIYA ILI ZAPISI, NACHINAYUSHCHEJSYA IZ |TOGO POLOZHENIYA, TREBUETSYA DOPOLNITELXNO 110~MS. eSLI LENTA NE NAHODITSYA V TOCHKE ZAGRUZKI, ONA MOZHET BYTX PROCHITANA V OBRATNOM NAPRAVLENII; 32~MS %%382 DOBAVLYAETSYA KO VREMENI LYUBOJ OBRATNOJ OPERACII, SLEDUYUSHCHEJ ZA PRYAMOJ, ILI LYUBOJ PRYAMOJ OPERACII, SLEDUYUSHCHEJ ZA OBRATNOJ. nAKONEC, SLEDUET RASSMOTRETX VOZMOZHNOSTX ODNOVREMENNOGO VVODA I VYVODA. chASTO PO |KONOMICHESKIM PRICHINAM NESKOLXKO LENTOCHNYH USTROJSTV PRISOEDINYAYUTSYA K ODNOMU \emph{LENTOCHNOMU KONTROLLERU} (USTROJSTVU UPRAVLENIYA LENTAMI), KOTORYJ MOZHET ODNOVREMENNO RABOTATX TOLXKO S ODNOJ ILI DVUMYA LENTAMI, POSKOLXKU CHISLO LINIJ PEREDACHI DANNYH MEZHDU NIM I evm OGRANICHENNO. iNOGDA KONTROLLERY NE SPOSOBNY RABOTATX BOLEE CHEM S ODNOJ LENTOJ ODNOVREMENNO. oDNAKO CHASTO ONI MOGUT CHITATX ODNU LENTU VO VREMYA ZAPISI DRUGOJ. nESKOLXKO REZHE VSTRECHAYUTSYA KONTROLLERY, KOTORYE MOGUT CHITATX ODNOVREMENNO S DVUH USTROJSTV, I AVTOR NIKOGDA NE VIDEL KONTROLLERA, KOTORYJ MOG BY PISATX NA DVA USTROJSTVA ODNOVREMENNO. pEREMOTKA---|TO OSOBYJ SLUCHAJ: CHEREZ 30~MS POSLE NACHALA PEREMOTKI LENTOCHNOE USTROJSTVO \MIXT{} "OTKLYUCHAETSYA" OT SVOEGO KONTROLLERA, KOTORYJ POSLE |TOGO SPOSOBEN VYPOLNYATX OPERACII S DRUGIMI USTROJSTVAMI. tAKIM OBRAZOM, OCHENX BOLXSHOE CHISLO LENTOCHNYH USTROJSTV MOGUT ODNOVREMENNO OSUSHCHESTVLYATX PEREMOTKU. pOCHTI VSE MASHINY DOPUSKAYUT VYPOLNENIE VVODA/VYVODA PARALLELXNO S VYCHISLENIYAMI, HOTYA MNOGIE evm, KOGDA PROISHODIT VVOD/VYVOD, RABOTAYUT NA~20--40\% MEDLENNEE IZ-ZA "RAZDELENIYA CIKLOV PAMYATI". \section sNOVA O SLIYANII. oBRATIMSYA VNOVX K PROCESSU $P\hbox{-PUTEVOGO}$ SLIYANIYA S UPOROM NA FUNKCIONIROVANIE USTROJSTV VVODA I VYVODA. bUDEM SCHITATX, CHTO DLYA VVODNYH I VYVODNOGO FAJLOV ISPOLXZUETSYA $P+1$~LENTOCHNYH USTROJSTV. nASHA CELX---MAKSIMALXNO SOVMESTITX OPERACII VVODA/VYVODA DRUG S DRUGOM I SO SCHETOM PO PROGRAMME TAK, CHTOBY MINIMIZIROVATX OBSHCHEE VREMYA SLIYANIYA. pOUCHITELXNO RASSMOTRETX SLEDUYUSHCHIJ CHASTNYJ SLUCHAJ, V KOTOROM NA VOZMOZHNUYU STEPENX ODNOVREMENNOSTI NALOZHENY SERXEZNYE OGRANICHENIYA. pREDPOLOZHIM, CHTO {\medskip\narrower \item{a)}~MOZHNO ZAPISYVATX NE BOLEE CHEM NA ODNU LENTU ODNOVREMENNO; \item{b)}~MOZHNO CHITATX NE BOLEE CHEM S ODNOJ LENTY ODNOVREMENNO; \item{c)}~CHTENIE, ZAPISX I VYCHISLENIYA MOGUT PROISHODITX ODNOVREMENNO, TOLXKO ESLI OPERACII CHTENIYA I ZAPISI BYLI NACHATY ODNOVREMENNO. \medskip} \noindent oKAZYVAETSYA, CHTO DAZHE PRI TAKIH OGRANICHENIYAH DOSTATOCHNO IMETX $2P$~BUFEROV VVODA I 2~BUFERA VYVODA, CHTOBY PODDERZHIVATX, V SUSHCHNOSTI, MAKSIMALXNUYU SKOROSTX DVIZHENIYA LENT, ESLI TOLXKO MY IMEEM DELO NE S OCHENX MEDLENNOJ evm. zAMETIM, CHTO~(a) NE YAVLYAETSYA NA SAMOM DELE OGRANICHENIEM, TAK KAK IMEETSYA TOLXKO ODNA VYVODNAYA LENTA. kROME TOGO, OB®EM VVODA RAVEN %%383 OB®EMU VYVODA, TAK CHTO CHITAETSYA V SREDNEM TOLXKO ODNA LENTA V LYUBOJ DANNYJ MOMENT VREMENI; ESLI USLOVIE~(b) NE VYPOLNYAETSYA, TO OBYAZATELXNO DOLZHNY BYTX PERIODY, KOGDA VOOBSHCHE NE PROISHODIT VVODA. sLEDOVATELXNO, DLYA TOGO CHTOBY MINIMIZIROVATX VREMYA SLIYANIYA, DOSTATOCHNO PODDERZHIVATX VYVODNUYU LENTU V SOSTOYANII RABOTY. vAZHNYJ METOD, NAZYVAEMYJ PREDSKAZANIEM ILI \emph{PROGNOZIROVANIEM} (forecasting), DAET ZHELAEMYJ |FFEKT. vO VREMYA VYPOLNENIYA $P\hbox{-PUTEVOGO}$ SLIYANIYA OBYCHNO IMEETSYA~$P$ "TEKUSHCHIH BUFEROV VVODA", KOTORYE ISPOLXZUYUTSYA KAK ISTOCHNIKI DANNYH; NEKOTORYE IZ NIH ZAPOLNENY BOLXSHE DRUGIH V ZAVISIMOSTI OT TOGO, KAKAYA CHASTX DANNYH V NIH UZHE PROSMOTRENA. eSLI VSE ONI OPUSTOSHATSYA PRIMERNO V ODNO I TO ZHE VREMYA, TO, PREZHDE CHEM PRODOLZHITX RABOTU, NAM PRIDETSYA VYPOLNITX MNOGO CHTENIJ, ESLI TOLXKO MY NE PREDPRIMEM NUZHNYH MER ZARANEE. k SCHASTXYU, VSEGDA MOZHNO SKAZATX, KAKOJ BUFER PERVYM STANET PUSTYM, PROSTA POSMOTREV NA \emph{POSLEDNYUYU} ZAPISX V KAZHDOM BUFERE. bUFER, POSLEDNYAYA ZAPISX KOTOROGO IMEET NAIMENXSHIJ KLYUCH, OBYAZATELXNO BUDET PERVYM PUSTYM BUFEROM NEZAVISIMO OT ZNACHENIJ KAKIH-LIBO DRUGIH KLYUCHEJ, TAK CHTO MY VSEGDA ZNAEM, KAKOJ FAJL POSLUZHIT PRICHINOJ NASHEJ SLEDUYUSHCHEJ KOMANDY VVODA. aLGORITM~F RASKRYVAET |TOT PRINCIP V DETALYAH. \alg F.(pROGNOZIROVANIE S PLAVAYUSHCHIMI BUFERAMI.) eTOT ALGORITM UPRAVLYAET BUFERIZACIEJ VO VREMYA $P\hbox{-PUTEVOGO}$ SLIYANIYA DLINNYH VVODNYH FAJLOV PRI~$P\ge 2$. dOPUSTIM, CHTO VVODNYE LENTY I FAJLY ZANUMEROVANY~1, 2,~\dots, $P$. v ALGORITME ISPOLXZUYUTSYA $2P$~BUFEROV VVODA~$|I|[1]$,~\dots, $|I|[2P]$, DVA BUFERA VYVODA~$|O|[0]$ I~$|O|[1]$ I SLEDUYUSHCHIE VSPOMOGATELXNYE MASSIVY: \descrtable{ $|A|[j]$, $1\le j \le 2P$: & $0$ ESLI V BUFER~$|I|[j]$ MOZHNO VVODITX DANNYE; \hfill\penalty -10000 $1$ V PROTIVNOM SLUCHAE. \cr $|B|[i]$, $1\le i \le P$: & bUFER, SODERZHASHCHIJ POSLEDNIJ PROCHITANNYJ BLOK IZ FAJLA~$i$.\cr $|C|[i]$, $1\le i \le P$: & bUFER, ISPOLXZUEMYJ V NASTOYASHCHIJ MOMENT DLYA VVODA IZ FAJLA~$i$.\cr $|L|[i]$, $1\le i \le P$: & pOSLEDNIJ KLYUCH, PROCHITANNYJ IZ FAJLA~$i$.\cr $|S|[j]$, $1\le j \le 2P$: & bUFER, KOTORYJ SLEDUET ISPOLXZOVATX, KOGDA $|I|[j]$~OPUSTOSHITSYA. \cr } v OPISYVAEMOM VIDE ALGORITM NIKOGDA NE OSTANOVITSYA; PODHODYASHCHIJ SPOSOB EGO "VYKLYUCHENIYA" OBSUZHDAETSYA NIZHE. \st[nACHALXNAYA USTANOVKA.] pROCHITATX PERVYJ BLOK S LENTY~$i$ V BUFER~$|I|[i]$, USTANOVITX~$|A|[i]\asg 1$, $|A|[P+i] \asg 0$, $|B|[i]\asg i$, $|C|[i]\asg i$ I USTANOVITX~$|L|[i]$ RAVNYM KLYUCHU POSLEDNEJ ZAPISI V~$|I|[i]$ PRI~$1\le i \le P$. zATEM NAJTI~$m$, TAKOE, %% 384 CHTO~$L(m)=\min \set{|L|[1],~\ldots, |L|[P]}$, I USTANOVITX~$t\asg 0$, $k\asg P+1$. nACHATX CHITATX S LENTY OT V BUFER~$|I|[k]$. \st[sLIYANIE.] sLIVATX ZAPISI IZ BUFEROV~$|I|[|C|[1]]$,~\dots, $|I|[|C|[P]]$ V~$|O|[t]$, POKA BUFER~$|O|[t]$ NE ZAPOLNITSYA. eSLI VO VREMYA |TOGO PROCESSA KAKOJ-NIBUDX BUFER VVODA, SKAZHEM~$|I|[|C|[i]]$, STANET PUSTYM, A~$|O|[t]$ ESHCHE NE ZAPOLNEN, TO USTANOVITX~$|A|[|C|[i]]\asg 0$, $|C|[i]\asg |S|[|C|[i]]$ I PRODOLZHATX SLIYANIE. \st[vVOD/VYVOD ZAVERSHEN.] zhDATX, POKA NE ZAVERSHITSYA PREDYDUSHCHAYA OPERACIYA CHTENIYA (ILI CHTENIYA/ZAPISI). zATEM USTANOVITX~$|A|[k]\asg 1$, $|S|[|B|[m]]\asg k$, $|B|[m]\asg k$ I USTANOVITX~$|L|[m]$ RAVNYM KLYUCHU POSLEDNEJ ZAPISI V~$|I|[k]$. \st[pROGNOZIROVANIE.] nAJTI~$m$, TAKOE, CHTO~$|L|[m]=\min\set{|L|[1], ~\ldots, |L|[P]}$, I NAJTI~$k$, TAKOE, CHTO~$|A|[k]=0$. \st[chTENIE/ZAPISX.] nACHATX CHITATX S LENTY~$m$ V BUFER~$|I|[k]$ I PISATX IZ BUFERA~$|O|[t]$ NA VYVODNUYU LENTU, ZATEM POLOZHITX~$t\asg 1-t$ I VERNUTXSYA K~\stp{2}. \algend \picture{rIS.~83. pROGNOZIROVANIE S PLAVAYUSHCHIMI BUFERAMI.} pRIMER NA RIS.~84 POKAZYVAET, KAK RABOTAET METOD PROGNOZIROVANIYA PRI~$P=2$ V PREDPOLOZHENII, CHTO KAZHDYJ BLOK NA LENTE SODERZHIT TOLXKO DVE ZAPISI. zDESX PREDSTAVLENO SODERZHIMOE BUFEROV VVODA VO VSE MOMENTY, KOGDA MY DOSTIGAEM NACHALA SHAGA~F2. aLGORITM~F, V SUSHCHNOSTI, OBRAZUET $P$~\emph{OCHEREDEJ BUFEROV,} GDE $|C|[i]$~UKAZYVAET NA NACHALO $i\hbox{-J}$~OCHEREDI, $|B|[i]$---NA EE KONEC, $|S|[j]$~UKAZYVAET NA PREEMNIKA BUFERA~$I[j]$; |TIM UKAZANIYAM NA RIS.~84 SOOTVETSTVUYUT STRELKI. sTROKA~1 OTRAZHAET SOSTOYANIE DEL POSLE NACHALXNOJ USTANOVKI. dLYA KAZHDOGO VVODNOGO FAJLA ESTX ODIN BUFER, I ESHCHE ODIN BLOK CHITAETSYA IZ FAJLA~1 (TAK KAK~$03<05$). sTROKA~2 POKAZYVAET POLOZHENIE VESHCHEJ POSLE TOGO, KAK SLIT PERVYJ BLOK: MY VYVODIM BLOK, SODERZHASHCHIJ "\boxit{\hbox{$01\ 02$}}", %%385 I VVODIM SLEDUYUSHCHIJ BLOK IZ FAJLA~2 (TAK KAK~$05<09$). zAMETIM, CHTO V STROKE~3 TRI IZ CHETYREH BUFEROV VVODA, PO SUTI DELA, PREDOSTAVLENY FAJLU~2, TAK KAK MY CHITAEM IZ |TOGO FAJLA I V EGO OCHEREDI UZHE ESTX POLNYJ BUFER I CHASTICHNO ZAPOLNENNYJ BUFER. eTOT MEHANIZM "PLAVAYUSHCHIH BUFEROV" YAVLYAETSYA VAZHNOJ CHERTOJ ALGORITMA~F, TAK KAK MY NE SMOGLI BY PRODOLZHITX RABOTU V STROKE~4, ESLI BY V STROKE~3 VYBRALI DLYA VVODA FAJL~1 VMESTO FAJLA~2. \picture{rIS.~84. oCHEREDI BUFEROV V SOOTVETSTVII S ALGORITMOM~F.} chTOBY DOKAZATX PRAVILXNOSTX ALGORITMA~F, MY DOLZHNY USTANOVITX DVA FAKTA: {\medskip\narrower \item{i)}~VSEGDA IMEETSYA SVOBODNYJ BUFER (T.~E.\ MY VSEGDA MOZHEM NAJTI~$k$ NA SHAGE~F4); \item{ii)}~ESLI BUFER VVODA ISCHERPYVAETSYA VO VREMYA SLIYANIYA, TO EGO PREEMNIK UZHE PRISUTSTVUET V PAMYATI (T.~E.\ $|S|[|C|[i]$ V SHAGE~F2 IMEET OSMYSLENNOE ZNACHENIE). \medskip} \noindent dOPUSTIM, CHTO (i)~NE IMEET MESTA, T.~E.\ VSE BUFERY ZANYATY V NEKOTORYJ MOMENT, KOGDA MY DOSTIGAEM SHAGA~F4. kAZHDYJ RAZ, KOGDA MY PRIHODIM K |TOMU SHAGU, SUMMARNYJ OB®EM NEOBRABOTANNYH DANNYH VO VSEH BUFERAH SOSTAVLYAET ROVNO $P$~EMKOSTEJ BUFERA, T.~E.\ DANNYH ROVNO STOLXKO, CHTOBY, PEREMESTIV IH, ZAPOLNITX $P$~BUFEROV, IBO DANNYE VVODYATSYA I VYVODYATSYA S ODINAKOVOJ SKOROSTXYU. nEKOTORYE BUFERY ZAPOLNENY LISHX CHASTICHNO, ODNAKO DLYA KAZHDOGO FAJLA CHASTICHNO ZAPOLNEN SAMOE BOLXSHEE ODIN BUFER, TAK CHTO VSEGO TAKIH BUFEROV NE BOLEE~$P$. pO PREDPOLOZHENIYU VSE $2P$~BUFEROV ZANYATY, TAK CHTO PO MENXSHEJ MERE~$P$ IZ NIH %% 386 DOLZHNY BYTX ZAPOLNENY CELIKOM. eTO MOZHET SLUCHITXSYA, TOLXKO ESLI $P$~BUFEROV POLNY I $P$~PUSTY, INACHE MY BY IMELI SLISHKOM MNOGO DANNYH. nO SAMOE BOLXSHEE ODIN BUFER MOZHET BYTX ODNOVREMENNO PUST I ZANYAT; SLEDOVATELXNO, (i)~Ne MOZHET NE VYPOLNYATXSYA. dOPUSTIM, CHTO~(ii) NE IMEET MESTA, T.~E.\ DLYA NEKOTOROGO FAJLA V PAMYATI NET NEOBRABOTANNYH ZAPISEJ, NO TEKUSHCHIJ BUFER VYVODA ESHCHE NE POLON. sOGLASNO PRINCIPU PROGNOZIROVANIYA, NUZHNO IMETX NE BOLEE ODNOGO BLOKA DANNYH DLYA VSEH OSTALXNYH FAJLOV, TAK KAK MY NE CHITAEM BLOK IZ FAJLA, ESLI |TOT BLOK NE POTREBUETSYA PREZHDE, CHEM BUDUT ISCHERPANY BUFERY KAKOGO-NIBUDX DRUGOGO FAJLA. tAKIM OBRAZOM, OBSHCHEE CHISLO NEOBRABOTANNYH ZAPISEJ SOSTAVLYAET SAMOE BOLXSHEE $P-1$~BLOKOV; DOBAVLENIE NEPOLNOGO BUFERA VYVODA DAET MENEE $P$~BUFERNYH EMKOSTEJ DANNYH V PAMYATI; POLUCHILI PROTIVORECHIE. eTI RASSUZHDENIYA USTANAVLIVAYUT SPRAVEDLIVOSTX ALGORITMA~F; ONI TAKZHE POKAZYVAYUT, CHTO VOZMOZHNY PATOLOGICHESKIE OBSTOYATELXSTVA, PRI KOTORYH ALGORITM EDVA-EDVA IZBEGAET KRUSHENIYA. nAMI ZDESX NE UPOMYANUTA NEKAYA VAZHNAYA TONKOSTX, KASAYUSHCHAYASYA VOZMOZHNOGO RAVENSTVA KLYUCHEJ; |TO OBSUZHDAETSYA V UPR.~5. oDIN IZ SPOSOBOV IZYASHCHNO ZAVERSHITX ALGORITM~F SOSTOIT V TOM, CHTOBY PRISVOITX~$|L|[m]$ ZNACHENIE~$\infty$ NA SHAGE~F3, ESLI TOLXKO CHTO PROCHITANNYJ BLOK BYL POSLEDNIM V OTREZKE. (kONEC OTREZKA VSEGDA UKAZYVAETSYA NEKOTORYM OSOBYE OBRAZOM.) pOSLE TOGO KAK BUDUT PROCHITANY VSE DANNYE VO VSEH FAJLAH, MY V KONCE KONCOV OBNARUZHIM NA SHAGE~F4, CHTO VSE~$L$ RAVNY~$\infty$; TOGDA OBYCHNO MOZHNO NACHATX CHTENIE PERVYH BLOKOV SLEDUYUSHCHIH OTREZKOV V KAZHDOM FAJLE, VYPOLNYAYA NACHALXNUYU USTANOVKU DLYA SLEDUYUSHCHEJ FAZY SLIYANIYA PO MERE VYVODA POSLEDNIH $P+1$~BLOKOV. tAKIM OBRAZOM, MOZHNO PODDERZHIVATX POLNUYU SKOROSTX RABOTY VYVODNOJ LENTY, CHITAYA V LYUBOE VREMYA NE BOLEE ODNOJ LENTY. iSKLYUCHENIE IZ |TOGO PRAVILA VSTRECHAETSYA NA SHAGE~F1, GDE BYLO BY POLEZNO CHITATX SRAZU NESKOLXKO LENT, CHTOBY OBESPECHITX VOZMOZHNOSTX NACHATX RABOTU; NO OBYCHNO SHAG~F1 MOZHNO USTROITX TAK, CHTOBY ON SOVMESHCHALSYA S PREDYDUSHCHEJ CHASTXYU VYCHISLENIJ. iDEYA PROSMOTRA POSLEDNEJ ZAPISI KAZHDOGO BLOKA S CELXYU PREDSKAZANIYA, KAKOJ BUFER PERVYM STANET PUSTYM, BYLA VYSKAZANA V 1953~G.\ f.~e.~gOLXBERTON. sAM METOD VPERVYE BYL OPUBLIKOVAN e.~X.~fR|NDOM [{\sl JACM,\/} {\bf 3} (1956), 144--145, 165]. eGO DOVOLXNO SLOZHNYJ ALGORITM ISPOLXZOVAL $3P$~BUFEROV VVODA, I KAZHDOMU FAJLU VVODA PREDNAZNACHALOSX PO TRI BUFERA; ALGORITM~F ULUCHSHAET POLOZHENIE, ISPOLXZUYA "PLAVAYUSHCHIE BUFERY" I POZVOLYAYA LYUBOMU ODNOMU FAJLU POTREBOVATX SRAZU DAZHE $P+1$~BUFEROV VVODA, HOTYA VSEGO TREBUETSYA NE BOLEE $2P$~BUFEROV. sLIYANIE S MENEE CHEM $2P$~BUFERAMI OBSUZHDAETSYA V KONCE |TOGO PUNKTA. nEKOTORYE evm IMEYUT VOZMOZHNOSTX "CHTENIYA VRAZBROS---ZAPISI %%387 SO SBORKOJ", CHTO POZVOLYAET OSUSHCHESTVLYATX VVOD/VYVOD IZ NEPOSLEDOVATELXNYH YACHEEK PAMYATI; ISPOLXZOVANIE TAKOJ VOZMOZHNOSTI VYHODIT ZA RAMKI |TOJ KNIGI. \section sRAVNITELXNOE POVEDENIE SHEM SLIYANIYA. iSPOLXZUEM TEPERX NASHI ZNANIYA O LENTAH I SLIYANII, CHTOBY SRAVNITX |FFEKTIVNOSTX RAZLICHNYH SHEM SLIYANIYA, IZUCHENNYH NAMI V P.~5.4.2--5.4.5. bUDET VESXMA POUCHITELXNO RAZRABOTATX DETALI KAZHDOGO METODA V PRIMENENII K KONKRETNOMU "BESPRISTRASTNOMU" PRIMERU. rASSMOTRIM PO|TOMU ZADACHU SORTIROVKI FAJLA, KAZHDAYA ZAPISX KOTOROGO SODERZHIT 100~LITER, PRICHEM V PAMYATI DLYA ZAPISI DANNYH DOSTUPNO 100000~LITERNYH POZICIJ (NE SCHITAYA MESTA DLYA PROGRAMMY, EE VSPOMOGATELXNYH PEREMENNYH I SRAVNITELXNO NEBOLXSHOGO PROSTRANSTVA, NEOBHODIMOGO DLYA SSYLOK V DEREVE VYBORA). iSHODNYE DANNYE RASPOLOZHENY NA LENTE V SLUCHAJNOM PORYADKE BLOKAMI PO 5000~LITER KAZHDYJ, I REZULXTAT DOLZHEN POLUCHITXSYA V TOM ZHE FORMATE. dLYA RABOTY IMEETSYA PYATX RABOCHIH LENT V DOBAVLENIE K USTROJSTVU, NA KOTOROM NAHODITSYA VVODNAYA LENTA. oBSHCHEE CHISLO SORTIRUEMYH ZAPISEJ~100000, NO |TA INFORMACIYA ALGORITMU SORTIROVKI ZARANEE NE IZVESTNA. v SHEMU~A (ZDESX I DALEE SM.~VKLADKU) SVEDENY TE DEJSTVIYA, KOTORYE PROISHODYAT, KOGDA K NASHIM DANNYM PRIMENYAETSYA DESYATX RAZLICHNYH SHEM SLIYANIYA. oBRATIVSHISX K |TOJ VAZHNOJ ILLYUSTRACII, OCHENX POLEZNO VOOBRAZITX, CHTO VY NABLYUDAETE ZA TEM, KAK PROISHODIT REALXNAYA SORTIROVKA: MEDLENNO PROSMATRIVAJTE KAZHDUYU STROKU SLEVA NAPRAVO, MYSLENNO PREDSTAVLYAYA SEBE SHESTX LENT, OSUSHCHESTVLYAYUSHCHIH CHTENIE, ZAPISX, PEREMOTKU I/ILI OBRATNOE CHTENIE, KAK UKAZANO NA DIAGRAMME. v TECHENIE $P\hbox{-PUTEVOGO}$ SLIYANIYA VVODNYE LENTY BUDUT NAHODITXSYA V DVIZHENII V $P$~RAZ REZHE, CHEM VYVODNAYA LENTA. zAMETIM, CHTO V SHEME~A PREDPOLAGAETSYA, CHTO, KOGDA PERVONACHALXNAYA VVODNAYA LENTA POLNOSTXYU PROCHITANA (I PEREMOTANA, CHTOBY EE UBRATX), UMELYJ OPERATOR SNIMAET EE I ZAMENYAET RABOCHEJ LENTOJ ZA 30~S. v PRIMERAH~2, 3 I~4 |TO I ESTX "VREMYA KRITICHESKOGO PUTI", KOGDA evm V BEZDEJSTVII OZHIDAET OPERATORA. nO V OSTALXNYH PRIMERAH OPERACIYA SNYATIYA I USTANOVKI LENT SOVMESHCHENA S DRUGOJ RABOTOJ. (nA SHEME~A PO GORIZONTALI UKAZANO VREMYA V MIN.) \def\example #1. #2.{{\bf pRIMER~#1. #2.}} \example 1. sBALANSIROVANNOE SLIYANIE S PRYAMYM CHTENIEM. nAPOMNIM OPISANIE ZADACHI: ZAPISI IMEYUT DLINU V 100~LITER, VNUTRENNEJ PAMYATI DOSTATOCHNO DLYA ODNOVREMENNOGO HRANENIYA 1000~ZAPISEJ I KAZHDYJ BLOK VVODNOJ LENTY SODERZHIT 5000~LITER (50~ZAPISEJ). vSEGO IMEETSYA $100\,000$~ZAPISEJ (T.~E.\ $10\,000\,000$~LITER, ILI 2000~BLOKOV). %% 388 mY NICHEM NE SVYAZANY V VYBORE RAZMERA BLOKOV DLYA PROMEZHUTOCHNYH FAJLOV. shESTILENTOCHNOE SBALANSIROVANNOE SLIYANIE ISPOLXZUET TREHPUTEVOE SLIYANIE, TAK CHTO TEHNIKA ALGORITMA F TREBUET 8~BUFEROV; MOZHNO, SLEDOVATELXNO, ISPOLXZOVATX BLOKI, SODERZHASHCHIE KAZHDYJ PO $1000/8=125$~ZAPISEJ (ILI 12500~LITER). pROHOD NACHALXNOGO RASPREDELENIYA MOZHET ISPOLXZOVATX VYBOR S ZAMESHCHENIEM (P.~5.4.1), I, CHTOBY PODDERZHIVATX NEPRERYVNUYU RABOTU LENT, BUDEM ISPOLXZOVATX DVA BUFERA VVODA PO 50~ZAPISEJ KAZHDYJ, PLYUS DVA BUFERA VYVODA PO 125~ZAPISEJ KAZHDYJ. eTO OSTAVLYAET DLYA DEREVA VYBORA MESTO V 650~ZAPISEJ. bOLXSHAYA CHASTX NACHALXNYH OTREZKOV BUDET, SLEDOVATELXNO, IMETX DLINU OKOLO 1300~ZAPISEJ (10 ILI 11~BLOKOV); NA SHEME~A POLUCHILOSX 78~NACHALXNYH OTREZKOV, PRICHEM POSLEDNIJ OTREZOK KOROTKIJ. pERVYJ PROHOD SLIYANIYA, KAK POKAZANO, SLIVAET DEVYATX OTREZKOV NA LENTU~4, A NE CHEREDUET LENTY~4, 5 I~6. eTO DAET VOZMOZHNOSTX VYPOLNYATX POLEZNUYU RABOTU V TO VREMYA, KOGDA OPERATOR VYCHISLITELXNOJ MASHINY USTANAVLIVAET RABOCHUYU LENTU NA USTROJSTVO~6; TAK KAK OBSHCHEE CHISLO OTREZKOV~$S$ IZVESTNO SRAZU POSLE ZAVERSHENIYA NACHALXNOGO RASPREDELENIYA, TO ALGORITM ZNAET, CHTO NA LENTU~4 DOLZHNO BYTX SLITO $\ceil{S/9}$~OTREZKOV, ZATEM $\ceil{(S-3)/9}$---NA LENTU~5, ZATEM $\ceil{(S-6)/9}$---NA LENTU~6. vSYA PROCEDURA SORTIROVKI V |TOM PRIMERE MOZHET BYTX SLEDUYUSHCHIM OBRAZOM IZOBRAZHENA S ISPOLXZOVANIEM OBOZNACHENIJ, VVEDENNYH V P.~5.4.2: $$\def\emp{\hbox{---}} \matrix{ 1^{26} & 1^{26} & 1^{26} & \emp & \emp & \emp \cr \emp & \emp & \emp & 3^9 & 3^9 & 3^8 \cr 9^3 & 9^3 & 9^26^1 & \emp & \emp & \emp \cr \emp & \emp & \emp & 27^1 & 27^1 & 24^1 \cr 78^1 & \emp & \emp & \emp & \emp & \emp \cr } $$ \example 2. mNOGOFAZNOE SLIYANIE S PRYAMYM CHTENIEM. vTOROJ PRIMER NA SHEME~A ILLYUSTRIRUET MNOGOFAZNOE SLIYANIE V SOOTVETSTVII S ALGORITMOM~5.4.2D. v |TOM SLUCHAE MY VYPOLNYAEM PYATIPUTEVOE SLIYANIE, PO|TOMU PAMYATX RAZBITA NA 12~BUFEROV PO 83~ZAPISI KAZHDYJ. v TECHENIE PERVONACHALXNOGO VYBORA S ZAMESHCHENIEM MU IMEEM DVA BUFERA VVODA V 50~ZAPISEJ I DVA BUFERA VYVODA V 83~ZAPISI, CHTO OSTAVLYAET 734~ZAPISI V DEREVE; TAKIM OBRAZOM, NACHALXNYE OTREZKI V |TOT RAZ BUDUT IMETX DLINU OKOLO 1468~ZAPISEJ (17 ILI 18~BLOKOV). v DANNOJ SITUACII POLUCHENO $S=70$~NACHALXNYH OTREZKOV, PRICHEM DLINY DVUH POSLEDNIH V DEJSTVITELXNOSTI RAVNY TOLXKO CHETYREM BLOKAM I ODNOMU BLOKU SOOTVETSTVENNO. sHEMU SLIYANIYA MOZHNO IZOBRAZITX TAK: %%389 $$\def\emp{\hbox{---}} \matrix{ 0^{13}1^{18} & 0^{13}1^{17} & 0^{13}1^{15} & 0^{12}1^{12} & 0^81^1 & \emp \cr 1^{15} & 1^{14} & 1^{12} & 1^8 & \emp & 0^8 1^4 2^1 5^3 \cr 1^7 & 1^6 & 1^4 & \emp & 4^8 & 1^4 2^1 5^3 \cr 1^3 & 1^2 & \emp & 8^4 & 4^4 & 2^1 5^3 \cr 1^1 & \emp & 16^1 19^1 & 8^2 & 4^2 & 5^2 \cr \emp & 34^1 & 19^1 & 8^1 & 4^1 & 5^1 \cr 70^1 & \emp & \emp & \emp & \emp & \emp \cr } $$ uDIVITELXNO, CHTO MNOGOFAZNOE SLIYANIE ZANIMAET NA 25~S \emph{BOLXSHE} VREMENI, CHEM ZNACHITELXNO BOLEE PROSTOE SBALANSIROVANNOE SLIYANIE! eTO OB®YASNYAETSYA DVUMYA OSNOVNYMI PRICHINAMI: \enumerate \li eTOT SLUCHAJ OSOBENNO UDACHEN DLYA SBALANSIROVANNOGO SLIYANIYA, TAK KAK~$S=78$ OCHENX BLIZKO K TOCHNOJ STEPENI~3. eSLI BY BYLO POLUCHENO 82~NACHALXNYH OTREZKA, TO SBALANSIROVANNOE SLIYANIE ZANYALO BY ESHCHE ODIN PROHOD. \li pRI MNOGOFAZNOM SLIYANII TERYAETSYA 30~c VO VREMYA ZAMENY VVODNOJ LENTY I V CELOM SVYSHE 5~MIN PROHODIT V OZHIDANII ZAVERSHENIYA OPERACIJ PEREMOTKI. v PROTIVOPOLOZHNOSTX |TOMU SBALANSIROVANNOE SLIYANIE TREBOVALO SRAVNITELXNO NEBOLXSHOGO VREMENI PEREMOTKI. vO VTOROJ FAZE MNOGOFAZNOGO SLIYANIYA S|KONOMLENO 13~S, TAK KAK 8~FIKTIVNYH OTREZKOV NA LENTE~6 MOZHNO SCHITATX PRISUTSTVUYUSHCHIMI DAZHE VO VREMYA PEREMOTKI |TOJ LENTY, NO DALXSHE NE PROISHODIT NIKAKOGO SOVMESHCHENIYA PEREMOTKI. tAKIM OBRAZOM, MNOGOFAZNYJ METOD PROIGRYVAET, NESMOTRYA NA TO, CHTO ON TREBUET ZNACHITELXNO MENXSHEGO VREMENI CHTENIYA/ZAPISI. \enumend \example 3. kASKADNOE SLIYANIE S PRYAMYM CHTENIEM. eTOT SLUCHAJ ANALOGICHEN PREDYDUSHCHEMU, TOLXKO ISPOLXZUET ALGORITM~5.4.3s. sLIYANIE IZOBRAZHAETSYA TAK: $$\def\emp{\hbox{---}} \matrix{ 1^{14} & 1^{15} & 1^{12} & 1^{14} & 1^{15} & \emp \cr 1^5 & 1^9 & \emp & 1^{14} & 1^{15} & 1^3 2^3 3^6 \cr 5^1 6^3 & 5^3 & 5^3 6^2 & \emp & 1^1 & 2^2 \cr \emp & 12^1 & 6^1 & 18^1 & 18^1 & 16^1 \cr 70^1 & \emp & \emp & \emp & \emp & \emp\cr } $$ (pROSMATRIVAYA SHEMU~A, NE ZABYVAJTE PREDSTAVLYATX KAZHDYJ PRIMER V DEJSTVII.) \example 4. mNOGOFAZNOE SLIYANIE S RASSHCHEPLENIEM LENT. eTA PROCEDURA, OPISANNAYA V KONCE P.~5.4.2, POZVOLYAET SOVMESTITX BOLXSHUYU CHASTX VREMENI PEREMOTKI. oNA ISPOLXZUET CHETYREHPUTEVOE SLIYANIE, TAK CHTO MY DELIM PAMYATX NA DESYATX BUFEROV PO 100~ZAPISEJ; V DEREVE VYBORA IMEETSYA 700~ZAPISEJ, I V REZULXTATE %%390 OKAZYVAETSYA, CHTO OBRAZOVANO 72~NACHALXNYH OTREZKA. pOSLEDNIJ OTREZOK VNOVX OCHENX KOROTKIJ. iSPOLXZOVANA SHEMA RASPREDELENIYA, ANALOGICHNAYA ALGORITMU~5.4.2D, ZA NEJ SLEDUET PROSTOJ, NO DO NEKOTOROJ STEPENI SPECIALXNYJ METOD RAZMESHCHENIYA FIKTIVNYH OTREZKOV: $$\def\emp{\hbox{---}} \matrix{ 1^{21} & 1^{19} & 1^{15} & 1^8 & \emp & 0^2 1^9 \cr 0^2 1^{17} & 0^2 1^{15} & 0^2 1^{11} & 0^2 1^4 & \emp & 0^2 1^9 4^4 \cr 1^{13} & 1^{11} & 1^7 & \emp & 0^2 4^4 & 0^2 1^9 4^4 \cr 1^{10} & 1^8 & 1^4 & \emp & 0^2 4^4 3^2 4^1 & 1^8 4^4 \cr 1^6 & 1^4 & \emp & 4^4 & 0^2 4^4 3^2 4^1 & 1^4 4^4 \cr 1^5 & 1^3 & \emp & 4^4 3^1 & 0^1 4^4 3^2 4^1 & 1^3 4^4 \cr 1^2 & \emp & 3^1 7^2 & 4^4 3^1 & 4^2 3^2 4^1 & 4^4 \cr 1^1 & \emp & 3^1 7^2 13^1 & 4^3 3^1 & 4^1 3^2 4^1 & 4^3 \cr \emp & 13^1 & 3^1 7^2 13^1 & 4^2 3^1 & 3^2 4^1 & 4^2 \cr \emp & 13^1 14^1 & 7^2 13^1 & 4^1 3^1 & 3^1 4^1 & 4^1 \cr 18^1 & 13^1 14^1 & 7^1 13^1 & 3^1 & 4^1 & \emp \cr 18^1 & 14^1 & 13^1 & \emp & \emp & 27^1 \cr \emp & \emp & \emp & 72^1 & \emp & \emp \cr } $$ sREDI VSEH PRIMEROV NA SHEME~A, KOTORYE NE CHITAYUT V OBRATNOM NAPRAVLENII, V |TOM, KAK OKAZYVAETSYA, NAILUCHSHEE VREMYA VYPOLNENIYA. tAK KAK $S$~NIKOGDA NE BYVAET OCHENX BOLXSHIM, MOZHNO RAZRABOTATX BOLEE SLOZHNYJ ALGORITM, KOTORYJ RAZMESHCHAET FIKTIVNYE OTREZKI ESHCHE LUCHSHE (SM.~UPR.~5.4.2-26). \example 5. kASKADNOE SLIYANIE S SOVMESHCHENIEM PEREMOTOK. eTA PROCEDURA RABOTAET POCHTI TAK ZHE BYSTRO, KAK PREDYDUSHCHAYA, HOTYA UPRAVLYAYUSHCHIJ EYU ALGORITM BOLEE PROST. mY ISPOLXZUEM DLYA NACHALXNOGO RASPREDELENIYA METOD KASKADNOJ SORTIROVKI, KAK V ALGORITME~5.4.3C, NO S~$T=5$, A NE~$T=6$. zATEM ISPOLXZOVANIE LENT V KAZHDOJ FAZE KAZHDOGO "KASKADA" CHEREDUETSYA TAKIM OBRAZOM, CHTO MY OBYCHNO NE PISHEM NA LENTU, POKA ONA POCHTI NAVERNYAKA NE OKAZHETSYA PEREMOTANNOJ. kOROCHE GOVORYA, SHEMA TAKOVA: $$\def\emp{\hbox{---}} \matrix{ 1^{21} & 1^{22} & 1^{19} & 1^{10} & \emp & \emp \cr 1^4 & 1^7 & \emp & \emp & 1^2 2^2 3^5 & 4^{10} \cr 7^2 & \emp & 8^3 & 7^2 8^2& \emp & 4^1 \cr \emp & 26^1 & \emp & 8^1 & 22^1 & 16^1 \cr 72^1 & \emp & \emp & \emp & \emp & \emp \cr } $$ \example 6. sBALANSIROVANNOE SLIYANIE S OBRATNYM CHTENIEM. eTOT PRIMER POHOZH NA PRIMER~1, NO VSE PEREMOTKI USTRANENY: %% 391 $$\def\emp{\hbox{---}} \matrix{ A_1^{26} & A_1^{26} & A_1^{26} & \emp & \emp & \emp \cr \emp & \emp & \emp & D_3^9 & D_3^9 & D_3^8 \cr A_9^3 & A_9^3 & A_9^2 A_6^1 & \emp & \emp & \emp \cr \emp & \emp & \emp & D_{24}^1 & D_{27}^1 & D_{27}^1 \cr A_{78}^1 & \emp & \emp & \emp & \emp & \emp \cr } $$ tAK KAK V PRIMERE~1 BYLO SRAVNITELXNO MALO PEREMOTOK, TO |TA SHEMA NE NAMNOGO LUCHSHE, CHEM V SLUCHAE PRYAMOGO CHTENIYA. fAKTICHESKI ONA OKAZYVAETSYA NESKOLXKO MEDLENNEJ MNOGOFAZNOJ SHEMY S RASSHCHEPLENIEM LENT, NESMOTRYA NA UDACHNOE ZNACHENIE~$S=78$. \example 7. mNOGOFAZNOE SLIYANIE S OBRATNYM CHTENIEM. v |TOM PRIMERE ISPOLXZUETSYA TOLXKO PYATX LENT IZ SHESTI, CHTOBY USTRANITX VREMYA PEREMOTKI I SMENY VVODNOJ LENTY. tAKIM OBRAZOM, ISPOLXZUETSYA TOLXKO CHETYREHPUTEVOE SLIYANIE I TAKAYA ZHE STRUKTURA BUFEROV, KAK V PRIMERAH~4 I~5. iSPOLXZUETSYA RASPREDELENIE, ANALOGICHNOE ALGORITMU~5.4.2D, NO NAPRAVLENIE OTREZKOV CHEREDUETSYA, I LENTA~1 ZAFIKSIROVANA, KAK KONECHNAYA VYVODNAYA LENTA. pERVYM ZAPISYVAETSYA VOZRASTAYUSHCHIJ OTREZOK NA LENTU~1; ZATEM UBYVAYUSHCHIE OTREZKI NA LENTY~2, 3, 4; ZATEM VOZRASTAYUSHCHIE OTREZKI NA~2, 3, 4; ZATEM UBYVAYUSHCHIE NA~1, 2, 3 I~T.~D. vSYAKIJ RAZ, KAK MY PEREKLYUCHAEM NAPRAVLENIE, VYBOR S ZAMESHCHENIEM OBYCHNO DAET BOLEE KOROTKIJ OTREZOK, PO|TOMU OKAZALOSX OBRAZOVANO 77~NACHALXNYH OTREZKOV VMESTO~72 V PRIMERAH~4 I~5. eTA PROCEDURA V REZULXTATE DAET RASPREDELENIE $(22, 21, 19, 15)$~OTREZKOV, A BLIZHAJSHEE TOCHNOE RASPREDELENIE---$(29, 56, 52, 44)$. uPRAZHNENIE~5.4.4-5 POKAZYVAET, KAK POSTROITX STROKI CHISEL SLIYANIYA, KOTORYE MOGUT BYTX ISPOLXZOVANY DLYA RAZMESHCHENIYA FIKTIVNYH OTREZKOV "OPTIMALXNYM" OBRAZOM; TAKAYA PROCEDURA VOZMOZHNA NA PRAKTIKE, POSKOLXKU KONECHNOSTX BOBINY GARANTIRUET, CHTO $S$~NIKOGDA NE BUDET SLISHKOM BOLXSHIM. pO|TOMU PRIMER NA SHEME~A BYL POSTROEN S ISPOLXZOVANIEM TAKOGO METODA RAZMESHCHENIYA FIKTIVNYH OTREZKOV (SM.~UPR.~7). oN OKAZALSYA SAMYM BYSTRYM IZ VSEH PREDSTAVLENNYH PRIMEROV. \example 8. kASKADNOE SLIYANIE S OBRATNYM CHTENIEM. kAK I V PRIMERE~7, ZDESX UCHASTVUET TOLXKO PYATX LENT. eTA PROCEDURA SLEDUET ALGORITMU~5.4.3C, ISPOLXZUYA PEREMOTKU I PRYAMOE CHTENIE, CHTOBY IZBEZHATX ODNOPUTEVOGO SLIYANIYA (TAK KAK PEREMOTKA BOLEE CHEM V DVA RAZA BYSTREE CHTENIYA NA USTROJSTVAH \MIXT). rASPREDELENIE, SLEDOVATELXNO, TO ZHE, CHTO I V PRIMERE~6. iSPOLXZUYA SIMVOL~$\downarrow$ DLYA OBOZNACHENIYA PEREMOTKI, IZOBRAZIM |TU SHEMU TAK: %%392 $$\def\emp{\hbox{---}}\def\da{\downarrow} \matrix{ A_1^{21} & A_1^{22} & A_1^{19} & A_1^{10} & \emp\cr A_1^4\da & A_1^7\da & \emp & \hbox{}_1^2 D_2^2 D_3^5 & D_4^{10} \cr A_8 A_7^2 & A_5^2 & A_9^4 & \emp & D_4^1\da \cr \emp & D_{17} & A_9\da & D_{25} & D_{21} \cr } $$ \example 9. oSCILLIRUYUSHCHAYA SORTIROVKA S OBRATNYM CHTENIEM. oSCILLIRUYUSHCHAYA SORTIROVKA S~$T=5$ (ALGORITM~5.4.5B) MOZHET ISPOLXZOVATX RASPREDELENIE BUFEROV, KAK V PRIMERAH~4, 5, 7 I~8, TAK KAK ONA VYPOLNYAET CHETYREHPUTEVOE SLIYANIE. oDNAKO VYBOR S ZAMESHCHENIEM DEJSTVUET ZDESX INACHE, POSKOLXKU NEPOSREDSTVENNO PERED VHODOM V KAZHDUYU FAZU SLIYANIYA VYVODITSYA OTREZOK DLINY~700 (A NE PRIMERNO~1400), CHTOBY OCHISTITX VNUTRENNYUYU PAMYATX. sLEDOVATELXNO, ZDESX POROZHDAETSYA 85~OTREZKOV VMESTO~72. nEKOTORYE KLYUCHEVYE SHAGI |TOGO PROCESSA TAKOVY: $$\def\emp{\hbox{---}} \matrix{ \emp & A_1 & A_1 A_1 & A_1 A_1 & A_1 A_1 \cr D_4 & \emp & A_1 & A_1 & A_1 \cr \multispan{5}\dotfill\cr D_4 D_4 & D_4 D_4 & D_4 D_4 & D_4 & \emp \cr D_4 & D_4 & D_4 & \emp & A_{16} \cr \multispan{5}\dotfill\cr D_4 & A_{16} D_4 D_4 & A_{16} D_4 & A_{16} D_4 A_1 & A_{16} \cr D_4 & A_{16} D_4 D_4 & A_{16} D_4 D_1 & A_{16} D_4 & A_{16} \cr \emp & A_{16} D_4 & A_{16} D_4 & A_{16} & A_{16} A_{13} \cr \emp & A_{16} D_4 & A_{16} & A_{16} A_4 & A_{16} A_{13} \cr \emp & A_{16} & A_{16} A_4 & A_{16} A_4 & A_{16} A_{13} \cr D_{37} & \emp & A_{16}\downarrow & A_{16}\downarrow & A_{16}\downarrow \cr \emp & A_{85} & \emp & \emp & \emp \cr } $$ \example 10. oSCILLIRUYUSHCHAYA SORTIROVKA S PRYAMYM CHTENIEM. v POSLEDNEM PRIMERE VYBOR S ZAMESHCHENIEM NE ISPOLXZUETSYA, TAK KAK VSE NACHALXNYE OTREZKI DOLZHNY BYTX ODNOJ DLINY. sLEDOVATELXNO, BUDET PROISHODITX VNUTRENNYAYA SORTIROVKA 1000~ZAPISEJ (POLNOJ EMKOSTI PAMYATI) KAZHDYJ RAZ, KOGDA TREBUETSYA NACHALXNYJ OTREZOK; |TO DAET~$S=100$. vOT NEKOTORYE KLYUCHEVYE SHAGI PROCESSA: %%393 $$\def\emp{\hbox{---}} \matrix{ A_1 & A_1 & A_1 & A_1 & A_1 \cr \emp & \emp & \emp & \emp & A_1 A_4 \cr \multispan{5} \dotfill\cr A_1 & A_1 & A_1 & A_1 & A_1 A_4 \cr \emp & \emp & \emp & A_1 A_4 & A_1 A_4\cr \emp & \emp & \emp & A_1 A_4 & A_1 A_4 \cr \multispan{5} \dotfill\cr A_1 & A_1 A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 \cr A_1 A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 \cr A_1 A_4 A_{16} & \emp & \emp & \emp & \emp \cr \multispan{5} \dotfill\cr \emp & A_1 A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 A_{16} A_{64} \cr A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 & A_1 A_4 A_{16} A_{64} \cr A_4 A_{16} & \emp & \emp & \emp & A_1 A_4 A_{16} A_{64} \cr A_4 A_{16} & A_4 & \emp & \emp & A_1 A_4 A_{16} A_{64} \cr \emp & \emp & \emp & A_{36} & A_1 A_4 A_{16} A_{64} \cr A_{100} & \emp & \emp & \emp & \emp \cr } $$ eTA PROGRAMMA OKAZYVAETSYA SAMOJ MEDLENNOJ IZ VSEH CHASTICHNO IZ-ZA TOGO, CHTO ONA NE ISPOLXZUET VYBOR S ZAMESHCHENIEM, NO BOLXSHEJ CHASTXYU VSLEDSTVIE EE VESXMA NESKLADNOGO KONCA (DVUHPUTEVOE SLIYANIE). \section oCENKA VREMENI VYPOLNENIYA. pOSMOTRIM TEPERX, KAK VYCHISLITX PRIBLIZITELXNOE VREMYA VYPOLNENIYA METODA SORTIROVKI, ISPOLXZUYUSHCHEGO LENTY \MIXT. mOZHNO LI PREDSKAZATX REZULXTATY, IZOBRAZHENNYE NA SHEME~A, NE VYPOLNYAYA DETALXNOGO MODELIROVANIYA? oDIN SPOSOB, KOTORYJ TRADICIONNO ISPOLXZOVALSYA DLYA SRAVNENIYA RAZLICHNYH SHEM SLIYANIYA, SOSTOIT V TOM, CHTOBY NALOZHITX DRUG NA DRUGA GRAFIKI, PODOBNYE PREDSTAVLENNYM NA RIS.~70, 74 I~78. eTI GRAFIKI IZOBRAZHAYUT |FFEKTIVNOE CHISLO PROHODOV PO DANNYM KAK FUNKCIYU OT CHISLA NACHALXNYH OTREZKOV V PREDPOLOZHENII, CHTO VSE NACHALXNYE OTREZKI IMEYUT PRIMERNO RAVNUYU DLINU (RIS.~85). nO |TO \emph{NE} DAET OCHENX REALISTICHNOGO SRAVNENIYA, POTOMU CHTO, KAK MY VIDELI, RAZNYE METODY PRIVODYAT K RAZLICHNOMU CHISLU NACHALXNYH OTREZKOV; KROME TOGO, IMEYUTSYA RAZLICHNYE "NAKLADNYE RASHODY", ZAVISYASHCHIE OT OTNOSITELXNOJ CHASTOTY MEZHBLOCHNYH PROMEZHUTKOV; ZNACHITELXNOE VOZDEJSTVIE OKAZYVAET TAKZHE VREMYA PEREMOTKI. vSE |TI ZAVISYASHCHIE OT MASHINY OSOBENNOSTI DELAYUT NEVOZMOZHNYM PODGOTOVITX NA MASHINNO-NEZAVISIMOJ OSNOVE %%394 SHEMY, OSUSHCHESTVLYAYUSHCHIE ISTINNOE SRAVNENIE METODOV. s DRUGOJ STORONY, IZ RIS.~85 VSE ZHE YAVSTVUET, CHTO, ZA ISKLYUCHENIEM SBALANSIROVANNOGO SLIYANIYA, |FFEKTIVNOE CHISLO PROHODOV MOZHET BYTX DOSTATOCHNO HOROSHO APPROKSIMIROVANO PLAVNYMI KRIVYMI VIDA~$\alpha \ln S+\beta$. sLEDOVATELXNO, MY MOZHEM. NEPLOHO SRAVNIVATX METODY V LYUBOJ PRAKTICHESKOJ SITUACII, IZUCHIV FORMULY, APPROKSIMIRUYUSHCHIE VREMYA VYPOLNENIYA. kONECHNO, NASHA CELX---NAJTI FORMULY PROSTYE, NO DOSTATOCHNO REALISTICHNYE. \picture{rIS.~85. nESKOLXKO OBMANCHIVYJ SPOSOB SRAVNENIYA SHEM SLIYANIYA.} pOPYTAEMSYA TEPERX VYVESTI TAKIE FORMULY V TERMINAH SLEDUYUSHCHIH PARAMETROV: $$\descralign{ N=&CHISLO SORTIRUEMYH ZAPISEJ;\cr C=&CHISLO LITER V ZAPISI; \cr M=& CHISLO DOSTUPNYH LITERNYH POZICIJ VNUTRENNEJ PAMYATI (PREDPOLAGAEMOE KRATNYM~$C$);\cr \tau=&VREMYA V SEKUNDAH, NUZHNOE DLYA TOGO, CHTOBY PROCHITATX ILI ZAPISATX ODNU LITERU; \cr %% 395 \rho\tau=&VREMYA V SEKUNDAH DLYA PEREMOTKI ODNOJ LITERY; \cr \sigma\tau=&VREMYA V SEKUNDAH STARTSTOPNOJ ZADERZHKI; \cr \gamma=&CHISLO LITER V MEZHBLOCHNOM PROMEZHUTKE;\cr \delta=&VREMYA V SEKUNDAH, NUZHNOE OPERATORU DLYA SNYATIYA I ZAMENY VVODNOJ LENTY; \cr B_i=&CHISLO LITER V BLOKE NEOTSORTIROVANNOGO VVODA; \cr B_o=&CHISLO LITER V BLOKE OTSORTIROVANNOGO VYVODA.\cr } $$ dLYA \MIXT{} IMEEM $\tau=1/60\,000$, $\rho=2/5$, $\sigma=300$, $\gamma=480$. v PRIMERE, RASSMOTRENNOM VYSHE, $N=100\,000$, $C=100$, $M=100\,000$, $B_i=B_o=5000$, $\delta=30$. oBYCHNO IMENNO |TI HARAKTERISTIKI MASHINY I DANNYH RESHAYUSHCHIM OBRAZOM VLIYAYUT NA VREMYA SORTIROVKI (HOTYA VREMYA PEREMOTKI CHASTO ZADAETSYA BOLEE SLOZHNYM VYRAZHENIEM, CHEM PROSTO KO|FFICIENTOM~$\rho$). iMEYA UKAZANNYE PARAMETRY I SHEMU SLIYANIYA, VYCHISLIM ESHCHE NEKOTORYE VELICHINY: $$\descralign{ P=&MAKSIMALXNYJ PORYADOK SLIYANIYA V SHEME; \cr P'=&CHISLO ZAPISEJ V DEREVE VYBORA S ZAMESHCHENIEM;\cr S=&CHISLO NACHALXNYH OTREZKOV;\cr \pi=\alpha\ln S+\beta=&PRIBLIZITELXNOE SREDNEE CHISLO CHTENIJ I ZAPISEJ KAZHDOJ LITERY, NE SCHITAYA NACHALXNOGO RASPREDELENIYA I OKONCHATELXNOGO SLIYANIYA;\cr \pi'=\alpha'\ln S+\beta'=&PRIBLIZITELXNOE SREDNEE CHISLO PEREMOTOK KAZHDOJ LITERY VO VREMYA PROMEZHUTOCHNYH FAZ SLIYANIYA;\cr B=&CHISLO LITER V BLOKE V PROMEZHUTOCHNYH FAZAH SLIYANIYA;\cr \omega_i, \omega, \omega_o=&"KO|FFICIENTY NAKLADNYH RASHODOV"---|FFEKTIVNYE VREMENA, TREBUEMYE DLYA CHTENIYA ILI ZAPISI ODNOJ LITERY (S UCHETOM PROMEZHUTKOV I STARTSTOPNOGO VREMENI), DELENNYE NA VREMYA~$\tau$.\cr } $$ v PRIMERAH SHEMY~A RAZMERY BLOKOV I BUFEROV VYBRANY V SOOTVETSTVII S FORMULOJ $$ B=\floor{{M\over C(2P+2)}}C, \eqno(1) $$ TAK CHTOBY BLOKI MOGLI BYTX SAMYMI BOLXSHIMI, KAKIE VOZMOZHNY PRI USLOVII SOVMESTIMOSTI SO SHEMOJ BUFERIZACII ALGORITMA~F. (chTOBY IZBEZHATX ZABOT VO VREMYA POSLEDNEGO PROHODA, VELICHINA~$P$ DOLZHNA BYTX DOSTATOCHNO MALOJ, CHTOBY~(1) OBESPECHILO~$B\ge B_o$.) rAZMER DEREVA VO VREMYA VYBORA S ZAMESHCHENIEM BUDET, SLEDOVATELXNO, $$ P'=(M-2B_i-2B)/C. \eqno(2) $$ dLYA SLUCHAJNYH DANNYH CHISLO NACHALXNYH OTREZKOV MOZHNO OCENITX, %%396 ISPOLXZUYA REZULXTATY P.~5.4.1, FORMULOJ $$ S\approx \ceil{{N\over 2P'}+{7\over 6}}. \eqno(3) $$ pREDPOLAGAYA, CHTO~$B_i1667$~MKS, ZA KOTOROE SLEDUET VYPOLNITX |TI ITERACII. tSHCHATELXNO ZAPROGRAMMIROVAV CIKL VYBORA S ZAMESHCHENIEM, MY MOZHEM DOSTIGNUTX |TOGO NA MNOGIH (NO NE NA VSEH) MASHINAH. zAMETIM, CHTO PRI SLIYANII POLOZHENIE NESKOLXKO MENEE KRITICHESKOE: %%397 VREMYA VYCHISLENIYA DLYA ODNOJ ZAPISI POCHTI VSEGDA MENXSHE VREMENI RABOTY LENTY PRI $P\hbox{-PUTEVOM}$ SLIYANII, TAK KAK $P$ NE OCHENX VELIKO. \item{b)}~\emph{dOLZHNY, LI MY NA SAMOM DELE VYBIRATX V KACHESTVE~$B$ MAKSIMALXNO VOZMOZHNYJ RAZMER BUFERA, KAK V~(1)?} bOLXSHOJ RAZMER BUFERA SOKRASHCHAET OTNOSHENIE IZDERZHEK~$\omega$ V~(5), NO ON TAKZHE UVELICHIVAET CHISLO NACHALXNYH OTREZKOV~$S$, TAK KAK $P'$~UMENXSHAETSYA. nEPOSREDSTVENNO NE YASNO, KAKOJ FAKTOR BOLEE VAZHEN, rASSMATRIVAYA VREMYA SLIYANIYA KAK FUNKCIYU OT~$x=CP'$, MOZHNO VYRAZITX EGO V VIDE $$ \left(\theta_1\ln \left({N\over x}+{7\over 6}\right)+\theta_2\right) \left({\theta_3-x\over \theta_4-x}\right) \eqno(8) $$ DLYA NEKOTORYH PODHODYASHCHIH KONSTANT~$\theta_1$, $\theta_2$, $\theta_3$, $\theta_4$, PRICHEM~$\theta_3>\theta_4$. dIFFERENCIROVANIE PO~$x$ POKAZYVAET, CHTO ESTX NEKOTOROE~$N_0$, TAKOE, CHTO DLYA VSEH~$N\ge N_0$ NEVYGODNO UVELICHIVATX~$x$ ZA SCHET RAZMERA BUFERA. v PRIMERAH, PRIVEDENNYH NA SHEME~A, $N_0$~OKAZALOSX, GRUBO GOVORYA, RAVNYM~$10\,000$; PRI SORTIROVKE BOLEE $10\,000$~ZAPISEJ BOLXSHOJ RAZMER BUFERA PREDPOCHTITELXNEE. zAMETIM, ODNAKO, CHTO PRI SBALANSIROVANNOM SLIYANII CHISLO PROHODOV REZKO IZMENYAETSYA, KOGDA $S$~PROHODIT CHEREZ STEPENX~$P$. eSLI ZARANEE IZVESTNO PRIBLIZHENNOE ZNACHENIE~$N$, TO RAZMER BUFERA SLEDUET VYBRATX TAK, CHTOBY~$S$ S BOLXSHOJ VEROYATNOSTXYU OKAZALOSX NEMNOGO MENXSHE STEPENI~$P$. nAPRIMER, RAZMER BUFERA DLYA PERVOJ STROKI SHEMY~A BYL RAVEN~$12\,500$, TAK KAK~$S=78$. eTO BYLO VPOLNE UDOVLETVORITELXNO, NO ESLI BY $S$~OKAZALOSX RAVNYM~82, TO BYLO BY ZNACHITELXNO LUCHSHE NEMNOGO UMENXSHITX RAZMER BUFERA. \medskip} \section fORMULY DLYA DESYATI PRIMEROV. vOZVRASHCHAYASX K SHEME~A, POPYTAEMSYA DATX FORMULY, APPROKSIMIRUYUSHCHIE VREMYA RABOTY DLYA KAZHDOGO IZ DESYATI METODOV. v BOLXSHINSTVE SLUCHAEV OSNOVNAYA FORMULA $$ N C \omega_i \tau + (\pi+\rho\pi')N C \omega \tau + (1+\rho)N C \omega_o \tau \eqno (9) $$ BUDET DOSTATOCHNO HOROSHIM PRIBLIZHENIEM K SUMMARNOMU VREMENI SORTIROVKI, ESLI MY OPREDELIM CHISLO PROMEZHUTOCHNYH PROHODOV SLIYANIYA~$\pi=\alpha \ln S+\beta$ I CHISLO PROMEZHUTOCHNYH PROHODOV PEREMOTKI~$\pi'=\alpha' \ln S+\beta$. iNOGDA NEOBHODIMO VNESTI V~(9) NEKOTORUYU POPRAVKU; SPECIFIKA KAZHDOGO METODA UCHITYVAETSYA SLEDUYUSHCHIM OBRAZOM: \example 1. sBALANSIROVANNOE SLIYANIE S PRYAMYM CHTENIEM. fORMULY $$ \pi=\ceil{\ln S/ \ln P}-1, \quad \pi'=\ceil{\ln S / \ln P}/P $$ MOGUT BYTX ISPOLXZOVANY DLYA $P\hbox{-PUTEVOGO}$ SLIYANIYA S $2P$~LENTAMI. %%398 \example 2. mNOGOFAZNOE SLIYANIE S PRYAMYM CHTENIEM. mOZHNO POLOZHITX~$\pi'\approx\pi$, TAK KAK ZA KAZHDOJ FAZOJ OBYCHNO SLEDUET PEREMOTKA PRIBLIZITELXNO TAKOJ ZHE DLINY, KAK PREDSHESTVUYUSHCHEE SLIYANIE. iZ TABL.~5.4.2-1 POLUCHAEM V SLUCHAE SHESTI LENT ZNACHENIYA~$\alpha=0.795$, $\beta=0.846-2$. (vELICHINA "$-2$" VOZNIKAET IZ-ZA TOGO, CHTO |LEMENTY TABLICY VKLYUCHAYUT NARYADU S PROMEZHUTOCHNYMI PROHODAMI TAKZHE NACHALXNYJ I KONECHNYJ.) k~(9) NUZHNO DOBAVITX VREMYA PEREMOTKI VVODNOJ LENTY POSLE NACHALXNOGO RASPREDELENIYA, A IMENNO~$\rho N C \omega_i \tau +\delta$. \example 3. kASKADNOE SLIYANIE S PRYAMYM CHTENIEM. tABLICA~5.4.3-1 PRIVODIT K ZNACHENIYAM~$\alpha=0.773$, $\beta=0.808-2$. vREMYA PEREMOTKI SRAVNITELXNO TRUDNO OCENITX; VOZMOZHNO, PREDPOLOZHENIE~$\pi'=\pi$ DOSTATOCHNO TOCHNO. kAK I V PRIMERE~2, MY DOLZHNY DOBAVITX K~(9) VREMYA NACHALXNOJ PEREMOTKI. \example 4. mNOGOFAZNOE SLIYANIE S RASSHCHEPLENIEM LENT. iZ TABL.~5.4.2-5 POLUCHAEM~$\alpha=0.752$, $\beta=1.024-2$. vREMYA PEREMOTKI POCHTI VSE SOVMESHCHAETSYA, ZA ISKLYUCHENIEM PEREMOTKI POSLE NACHALXNOJ USTANOVKI~$(\rho N C \omega_i \tau + \delta)$ I DVUH FAZ VBLIZI KONCA (36\% OT~$2\rho N C \omega \tau$). mY MOZHEM TAKZHE VYCHESTX~$0.18$ IZ~$\beta$, TAK KAK PERVAYA POLOVINA FAZY SOVMESHCHAETSYA S NACHALXNOJ PEREMOTKOJ. \example 5. kASKADNOE SLIYANIE S SOVMESHCHENIEM PEREMOTKI. zDESX, ISPOLXZUYA TABL.~5.4.3-1 DLYA~$T=5$, POLUCHAEM~$\alpha=0.897$, $\beta=0.800-2$. pOCHTI VSYA NESOVMESHCHENNAYA PEREMOTKA VSTRECHAETSYA NEPOSREDSTVENNO POSLE NACHALXNOGO RASPREDELENIYA I POSLE KAZHDOGO DVUHPUTEVOGO SLIYANIYA. pOSLE TOCHNOGO NACHALXNOGO RASPREDELENIYA SAMAYA DLINNAYA LENTA SODERZHIT PRIMERNO~$1/g$ VSEH DANNYH, GDE $g$~ESTX "OTNOSHENIE ROSTA". pOSLE KAZHDOGO DVUHPUTEVOGO SLIYANIYA OB®EM PEREMOTKI V SLUCHAE SHESTI LENT RAVEN~$d_k d_{n-k}$ (SM.~UPR.~5.4.3-5), I MOZHNO POKAZATX, CHTO V SLUCHAE $T$~LENT OB®EM PEREMOTKI POSLE DVUHPUTEVYH SLIYANIJ PRIBLIZITELXNO RAVEN $$ (2/(2T-1))(1-\cos(4\pi/(2T-1))) $$ OT VSEGO FAJLA. v NASHEM SLUCHAE~($T=5$) |TO SOSTAVLYAET ${2\over 9}(1-\cos 80^\circ)\approx 0.183$~FAJLA, I |TO PROISHODIT V $0.946\ln S+0.796-2$~SLUCHAYAH. \example 6. sBALANSIROVANNOE SLIYANIE S OBRATNYM CHTENIEM. oNO NAPOMINAET PRIMER~1, ZA ISKLYUCHENIEM TOGO, CHTO ZNACHITELXNAYA CHASTX PEREMOTKI USTRANYAETSYA. iZMENENIE NAPRAVLENIYA OT PRYAMOGO K OBRATNOMU VYZYVAET NEKOTORYE ZADERZHKI, NO ONI NE SUSHCHESTVENNY. s VEROYATNOSTXYU~$1/2$ PERED POSLEDNIM PROHODOM NUZHNA BUDET PEREMOTKA, PO|TOMU MOZHNO VZYATX~$\pi'=1/(2P)$. \example 7. mNOGOFAZNOE SLIYANIE S OBRATNYM CHTENIEM. tAK KAK V |TOM SLUCHAE VYBOR S ZAMESHCHENIEM POROZHDAET OTREZKI, MENYAYUSHCHIE NAPRAVLENIE PRIMERNO KAZHDYE $P$~RAZ, TO SLEDUET ZAMENITX~(3) DRUGOJ FORMULOJ DLYA~$S$. dOSTATOCHNO HOROSHIM PRIBLIZHENIEM (SM.~UPR.~5.4.1-24) BUDET~$S=\ceil{N(3+1/P)6P'}+1$. vSE VREMYA PEREMOTKI USTRANYAETSYA, I TABL.~5.4.2-1 DAET~$\alpha=0.863$, $\beta=0.921-2$. \example 8. kASKADNOE SLIYANIE S OBRATNYM CHTENIEM. iZ TABL.~5.4.3-1 IMEEM~$\alpha=0.897$, $\beta=0.800-2$. vREMYA PEREMOTKI PO |TOJ TABLICE MOZHNO OCENITX KAK UDVOENNUYU RAZNOSTX ["PROHODY S KOPIROVANIEM" MINUS "PROHODY BEZ KOPIROVANIYA"] PLYUS~$1/(2P)$ V TOM SLUCHAE, ESLI PERED OKONCHATELXNYM SLIYANIEM NEOBHODIMA PEREMOTKA DLYA POLUCHENIYA VOZRASTAYUSHCHEGO PORYADKA. \example 9. oSCILLIRUYUSHCHAYA SORTIROVKA S OBRATNYM CHTENIEM. v |TOM SLUCHAE VYBOR S ZAMESHCHENIEM DOLZHEN MNOGO RAZ NACHINATXSYA I OSTANAVLIVATXSYA; ZA ODIN RAZ RASPREDELYAETSYA SERIYA OT~$P-1$ DO~$2P-1$ OTREZKOV (V SREDNEM~$P$); SREDNYAYA DLINA OTREZKOV, SLEDOVATELXNO, OKAZYVAETSYA PRIBLIZITELXNO RAVNOJ~$P'(2P-4/3)/P$, I MOZHNO OCENITX~$S=\ceil{N/((2-4/(3P))P')}+1$. nEKOTOROE VREMYA RASHODUETSYA NA PEREKLYUCHENIE OT SLIYANIYA K RASPREDELENIYU I OBRATNO; |TO PRIBLIZITELXNO VREMYA, TREBUEMOE, CHTOBY PROCHITATX S VVODNOJ LENTY $P'$~ZAPISEJ, %% 399 A IMENNO~$P' C \omega_i \tau$, I |TO PROISHODIT PRIMERNO $S/P$~RAZ. vREMYA PEREMOTKI I VREMYA SLIYANIYA MOZHNO OCENITX, KAK V PRIMERE~6. \example 10. oSCILLIRUYUSHCHAYA SORTIROVKA S PRYAMYM CHTENIEM. eTOT METOD NELEGKO PROANALIZIROVATX, POSKOLXKU OKONCHATELXNAYA FAZA "CHISTKI", VYPOLNYAEMAYA POSLE ISCHERPANIYA VVODA, NE TAK |FFEKTIVNA, KAK PREDYDUSHCHIE. pRENEBREGAYA |TIM TRUDNYM ASPEKTOM I PROSTO SCHITAYA, CHTO ESTX ODIN DOPOLNITELXNYJ PROHOD, MOZHNO OCENITX VREMYA SLIYANIYA, POLAGAYA~$\alpha=1/\ln P$, $\beta=0$ I~$\pi'=\pi/P$. rASPREDELENIE OTREZKOV V |TOM SLUCHAE NESKOLXKO INOE, TAK KAK NE ISPOLXZUETSYA VYBOR S ZAMESHCHENIEM; MY USTANAVLIVAEM~$P'=M/C$ I~$S=\ceil{N/P'}$. pRILOZHIV USILIYA, MOZHNO SOVMESTITX VYCHISLENIE, CHTENIE I ZAPISX VO VREMYA RASPREDELENIYA, VVODYA DOPOLNITELXNYJ KO|FFICIENT NAKLADNYH RASHODOV OKOLO~$(M+2B)/M$. vREMYA PEREKLYUCHENII REZHIMOV, UPOMYANUTOE V PRIMERE~9, V NASTOYASHCHEM SLUCHAE NE NUZHNO, TAK KAK ONO SOVMESHCHAETSYA S PEREMOTKOJ. iTAK, OCENKOJ VREMENI SORTIROVKI BUDET~(9) PLYUS~$2B N C \omega_i \tau /M$. \htable{tABLICA~1}% {sVODNAYA TABLICA OCENOK VREMENI SORTIROVKI}% {\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&\hfil$#$\bskip&$#$\bskip\hfil&\hfil$#$\bskip&\hfil$#$\bskip\cr \hbox{pRIMER} & P & B & P' & S & \omega & \alpha & \beta & \alpha' & \beta' & (9) & \hbox{dOBAVKA K~(9)} & \hbox{oCENKA ITOGA} & \hbox{rEALXNYJ ITOG} \cr \noalign{\hrule} 1 & 3 & 12500 & 650 & 79& 1.062& 0.910& -1.000& 0.303& 0.000& 1064& & 1064 & 1076 \cr 2 & 5 & 8300 & 734 & 70& 1.094& 0.795& -1.136& 0.795& -1.136& 1010& \rho N C \omega_i \tau + \delta & 1113 & 1103 \cr 3 & 5 & 8300 & 734 & 70& 1.094& 0.773& -1.192& 0.773& -1.192& 972& \rho N C \omega_i \tau + \delta & 1075 & 1127 \cr 4 & 4 & 10000 & 700 & 73& 1.078& 0.752& -0.994& 0.000& 0.720& 844& \rho N C \omega_i \tau + \delta & 947 & 966 \cr 5 & 4 & 10000 & 700 & 73& 1.078& 0.897& -1.200& 0.173& 0.129& 972& & 972 & 992 \cr 6 & 3 & 12500 & 650 & 79& 1.062& 0.910& -1.000& 0.000& 0.167& 981& & 981 & 980 \cr 7 & 4 & 10000 & 700 & 79& 1.078& 0.863& -1.079& 0.000& 0.000& 922& & 922 & 907 \cr 8 & 4 & 10000 & 700 & 73& 1.078& 0.897& -1.200& 0.098& 0.117& 952& & 952 & 949 \cr 9 & 4 & 10000 & 700 & 87& 1.078& 0.721& -1.000& 0.000& 0.125& 846& P'S C \omega_i \tau /P & 874 & 928 \cr 10& 4 & 10000 & \hfill-\hfill & 100& 1.078& 0.721& 0.000& 0.180& 0.000& 1095& 2BNC\omega_i\tau/M & 1131 & 1158 \cr \noalign{\hrule} } tABL.~1 POKAZYVAET, CHTO OCENKI V |TIH PRIMERAH NE SLISHKOM PLOHI, HOTYA V NESKOLXKIH SLUCHAYAH RASHOZHDENIE SOSTAVLYAET PORYADKA 50~S. fORMULY V PRIMERAH~2 I~3 POKAZYVAYUT, CHTO KASKADNOE SLIYANIE DOLZHNO BYTX PREDPOCHTITELXNEJ MNOGOFAZNOGO NA SHESTI LENTAH, TEM NE MENEE NA PRAKTIKE MNOGOFAZNOE SLIYANIE LUCHSHE! pRICHINA |TOGO KROETSYA V TOM, CHTO GRAFIKI, PODOBNYE IZOBRAZHENNYM NA RIS.~85 (GDE POKAZAN SLUCHAJ PYATI LENT), BLIZHE K PRYAMYM LINIYAM DLYA MNOGOFAZNOGO ALGORITMA; KASKADNYJ METOD PREVOSHODIT MNOGOFAZNYJ NA SHESTI LENTAH DLYA~$14\le S \le 15$ I~$43\le S \le 55$ VBLIZI "TOCHNYH" KASKADNYH CHISEL~15 I~55, NO MNOGOFAZNOE RASPREDELENIE PO ALGORITMU~5.4.2D LUCHSHE ILI |KVIVALENTNO DLYA VSEH OSTALXNYH~$S\le 100$. kASKADNYJ METOD PREDPOCHTITELXNEE MNOGOFAZNOGO PRI~$S\to\infty$, NO FAKTICHESKI~$S$ NE PRIBLIZHAETSYA K~$\infty$. zANIZHENNAYA OCENKA V PRIMERE~9 OBUSLOVLENA ANALOGICHNYMI OBSTOYATELXSTVAMI; MNOGOFAZNAYA SORTIROVKA LUCHSHE OSCILLIRUYUSHCHEJ, NESMOTRYA NA TO CHTO ASIMPTOTICHESKAYA TEORIYA GOVORIT NAM, CHTO DLYA BOLXSHIH~$S$ OSCILLIRUYUSHCHAYA SORTIROVKA BUDET NAILUCHSHEJ. \section nESKOLXKO DOPOLNITELXNYH ZAMECHANIJ. sEJCHAS SAMOE VREMYA SDELATX NESKOLXKO BOLEE ILI MENEE SLUCHAJNYH NABLYUDENIJ OTNOSITELXNO LENTOCHNOGO SLIYANIYA: %%400 \bye