%% 428
\input style
\subsubchap{dISKI I BARABANY}
dO SIH POR MY RASSMATRIVALI LENTY KAK EDINSTVENNOE SREDSTVO DLYA VNESHNEJ
SORTIROVKI, ODNAKO NEREDKO V NASHEM RASPORYAZHENII OKAZYVAYUTSYA I DRUGIE
TIPY USTROJSTV MASSOVOJ PAMYATI S BOLEE GIBKIMI VOZMOZHNOSTYAMI. hOTYA TAKIE
ZAPOMINAYUSHCHIE .USTROJSTVA "BOLXSHOGO OB�EMA" ILI "ZAPOMINAYUSHCHIE USTROJSTVA S
PRYAMYM DOSTUPOM" VESXMA MNOGOOBRAZNY, MOZHNO VYDELITX SLEDUYUSHCHIE OBSHCHIE SVOJSTVA:
\medskip
\item{i)} dLYA DOSTUPA K LYUBOJ OPREDELENNOJ CHASTI HRANIMOJ INFORMACII NE
TREBUETSYA OCHENX MNOGO VREMENI.

\item{ii)} bLOKI, SODERZHASHCHIE POSLEDOVATELXNYE SLOVA, MOGUT
BYSTRO PEREDAVATXSYA MEZHDU VNUTRENNEJ (OPERATIVNOJ) I VNESHNEJ PAMYATXYU.
\medskip
\noindent mAGNITNAYA LENTA UDOVLETVORYAET (ii), NO NE (i), POSKOLXKU
PEREHOD LENTY OT ODNOGO KONCA K DRUGOMU ZANIMAET MNOGO VREMENI. nEKOTORYE
USTROJSTVA UDOVLETVORYAYUT (i), NO NE (ii); PRIMEROM MOZHET SLUZHITX PAMYATX
BOLXSHOGO OB�EMA NA FERRITOVYH SERDECHNIKAH,
\picture{rIS. 89. pAKET DISKOV}
V KOTOROJ VREMYA DOSTUPA K KAZHDOMU SLOVU PRIMERNO V DESYATX RAZ PREVYSHAET
VREMYA DOSTUPA K VNUTRENNEJ PAMYATI.

kAZHDOE VNESHNEE ZAPOMINAYUSHCHEE USTROJSTVO IMEET SVOI HARAKTERNYE
OSOBENNOSTI, KOTORYE SLEDUET TSHCHATELXNO IZUCHITX, PREZHDE CHEM PISATX DLYA NEGO
BOLXSHIE PROGRAMMY; ODNAKO TEHNOLOGIYA MENYAETSYA TAK BYSTRO, CHTO ZDESX NE
UDASTSYA SKOLXKO-NIBUDX PODROBNO OBSUDITX VSE SUSHCHESTVUYUSHCHIE RAZNOVIDNOSTI
OBORUDOVANIYA. pO|TOMU MY RASSMOTRIM LISHX NEKOTORYE TIPICHNYE ZAPOMINAYUSHCHIE
USTROJSTVA I NA .NIH PROILLYUSTRIRUEM PRODUKTIVNYE PODHODY K ZADACHE SORTIROVKI.

oDNIM IZ NAIBOLEE RASPROSTRANENNYH TIPOV VNESHNIH ZAPOMINAYUSHCHIH USTROJSTV,
UDOVLETVORYAYUSHCHIH (i) I (ii), YAVLYAETSYA DISKOVYJ
%% 429
FAJL ILI MODULX S PAKETOM DISKOV (RIS. 89). dANNYE HRANYATSYA NA
NESKOLXKIH BYSTRO VRASHCHAYUSHCHIHSYA KRUGLYH DISKAH, POKRYTYH MAGNITNYM
MATERIALOM; DLYA ZAPISI ILI VYBORKI INFORMACII ISPOLXZUETSYA DERZHATELX
GOLOVOK V VIDE GREBESHKA. SODERZHASHCHIJ ODNU ILI NESKOLXKO "GOLOVOK
CHTENIYA/ZAPISI" DLYA KAZHDOJ POVERHNOSTI DISKA. kAZHDAYA POVERHNOSTX DELITSYA NA
KONCENTRICHESKIE KOLXCA, NAZYVAEMYE \emph{DOROZHKAMI} ILI \emph{TREKAMI},
TAK CHTO ZA VREMYA ODNOGO OBOROTA DISKA POD GOLOVKAMI CHTENIYA/ZAPISI PROHODIT
CELAYA DOROZHKA. dERZHATELX GOLOVOK MOZHET PEREMESHCHATXSYA V DVUH
NAPRAVLENIYAH---VNUTRX ILI NARUZHU, PEREDVIGAYA GOLOVKI CHTENIYA/ZAPISI OT
DOROZHKI K DOROZHKE, NO |TO DVIZHENIE TREBUET VREMENI. mNOZHESTVO DOROZHEK,
KOTORYE MOGUT BYTX PROCHITANY ILI ZAPISANY BEZ PEREMESHCHENIYA DERZHATELYA
GOLOVOK, NAZYVAETSYA \emph{CILINDROM}. nAPRIMER, NA RIS.~89 POKAZAN
DISKOVYJ FAJL, KOTORYJ IMEET PO ODNOJ GOLOVKE CHTENIYA/ZAPISI NA KAZHDUYU
POVERHNOSTX; PUNKTIRNYMI LINIYAMI OBOZNACHEN ODIN IZ CILINDROV, SOSTOYASHCHIJ
IZ VSEH DOROZHEK, PROSMATRIVAEMYH V NASTOYASHCHIJ MOMENT GOLOVKAMI.

chTOBY SDELATX NASHI RASSUZHDENIYA BOLEE KONKRETNYMI, RASSMOTRIM
GIPOTETICHESKOE DISKOVOE USTROJSTVO |MIXTEC|, DLYA KOTOROGO
$$
\eqalign{
\hbox{1 DOROZHKA}& =\hbox{5000 LITER,}\cr
\hbox{1 CILINDR}& =\hbox{20 DOROZHEK,}\cr
\hbox{1 DISKOVOE USTROJSTVO}&= \hbox{200 CILINDROV.}\cr
}
$$
tAKOE DISKOVOE USTROJSTVO SODERZHIT 20 MILLIONOV LITER, T. E. CHUTX MENXSHE
TOGO OB�EMA DANNYH, KOTORYJ MOZHNO ZAPISATX NA ODNU MAGNITNUYU LENTU. nA
NEKOTORYH MASHINAH DOROZHKI VBLIZI CENTRA SODERZHAT MENXSHE LITER, CHEM DOROZHKI
BLIZHE K KRAYU. oT |TOGO PROGRAMMIROVANIE ZNACHITELXNO USLOZHNYAETSYA, NO
|MIXTEC|, K SCHASTXYU, NE SOZDAET TAKIH PROBLEM.

vREMYA, NEOBHODIMOE DLYA CHTENIYA ILI ZAPISI NA DISKOVYJ FAJL, PREDSTAVLYAET,
PO SUSHCHESTVU, SUMMU TREH VELICHIN:
\itemize
\li vREMYA POISKA (VREMYA, ZATRACHIVAEMOE NA PEREMESHCHENIE DERZHATELYA GOLOVOK
K NUZHNOMU CILINDRU).
\li vREMYA OZHIDANIYA (ZADERZHKA, SVYAZANNAYA S VRASHCHENIEM DISKA, POKA GOLOVKA
CHTENIYA/ZAPISI NE DOSTIGNET NUZHNOGO MESTA).
\li vREMYA PEREDACHI (ZADERZHKA, SVYAZANNAYA S VRASHCHENIEM DISKA, POKA DANNYE
PROHODYAT POD GOLOVKAMI).
\itemend

nA USTROJSTVAH |MIXTEC| VREMYA POISKA DLYA PEREHODA OT CILINDRA $i$ K
CILINDRU $j$ RAVNO $25+{1\over2}\vert i-j \vert$ MS. eSLI $i$ I
$j$---SLUCHAJNO VYBRANNYE CELYE CHISLA MEZHDU 1 I 200, TO SREDNEE ZNACHENIE
%%430
$\vert i-j\vert$ RAVNO $2 \left( {201\atop 3}\right)/200^2\approx 66.7$,
T. E. SREDNEE VREMYA POISKA
SOSTAVLYAET PRIBLIZITELXNO 60~MS. dISKI |MIXTEC| SOVERSHAYUT ODIN OBOROT ZA
25 MS, TAK CHTO VREMYA OZHIDANIYA RAVNO V SREDNEM 12.5 MS. vREMYA PEREDACHI $n$
LITER ESTX
$(n/5000)\times25\hbox{ MS}=5n\hbox{ MKS}$.
(eTO PRIMERNO V $3{1\over3}$ RAZA BYSTREE, CHEM SKOROSTX PEREDACHI DLYA LENT
|MIXT|, ISPOLXZOVANNYH V PRIMERAH P.~5.4.6.)

tAKIM OBRAZOM, OSNOVNYE RAZLICHIYA MEZHDU DISKAMI |MIXTEC| I LENTAMI |MIXT|,
KASAYUSHCHIESYA SORTIROVKI, SLEDUYUSHCHIE:
\medskip
\item{a)} nA LENTAH VOZMOZHEN TOLXKO POSLEDOVATELXNYJ DOSTUP K DANNYM.

\item{b)} oTDELXNAYA OPERACIYA S DISKOM, KAK PRAVILO, SOPRYAZHENA SO
ZNACHITELXNO BOLXSHIMI NAKLADNYMI RASHODAMI (VREMYA POISKA + VREMYA OZHIDANIYA
V SRAVNENII SO STARTSTOPNYM VREMENEM).
\item{c)} sKOROSTX PEREDACHI U DISKA BOLXSHE.
\medskip

iSPOLXZUYA DLYA LENT RAZUMNYE SHEMY SLIYANIYA, MY MOGLI DO NEKOTOROJ STEPENI
SKOMPENSIROVATX NEDOSTATOK (a). tEPERX U NAS INAYA CELX---NAM NUZHNO NAJTI
TAKIE RACIONALXNYE ALGORITMY SORTIROVKI NA DISKAH, V KOTORYH
KOMPENSIRUETSYA NEDOSTATOK (b).
\qsection kAK SOKRATITX VREMYA OZHIDANIYA? rASSMOTRIM .SNACHALA
ZADACHU MINIMIZACII ZADERZHEK, VYZYVAEMYH TEM, CHTO V TOT MOMENT, KOGDA MY
HOTIM NACHATX KOMANDU VVODA/VYVODA, DISK NE VSEGDA NAHODITSYA V PODHODYASHCHEJ
POZICII. nELXZYA ZASTAVITX DISK VRASHCHATXSYA BYSTREE, NO VSE-TAKI MOZHNO
PRIBEGNUTX K RAZNYM ULOVKAM, KOTORYE UMENXSHAT ILI DAZHE POLNOSTXYU
USTRANYAT VREMYA OZHIDANIYA. nESOMNENNO, POMOZHET DOBAVLENIE ESHCHE NESKOLXKIH
DERZHATELEJ GOLOVOK, NO |TO VESXMA DOROGOSTOYASHCHAYA MODIFIKACIYA OBORUDOVANIYA.
 vOT NESKOLXKO "PROGRAMMISTSKIH" IDEJ.
\enumerate
\li eSLI MY CHITAEM ILI ZAPISYVAEM ZA ODIN RAZ NESKOLXKO DOROZHEK ODNOGO
CILINDRA, TO TEM SAMYM USTRANYAEM VREMYA OZHIDANIYA (I VREMYA POISKA) DLYA
VSEH DOROZHEK, KROME PERVOJ. vOOBSHCHE ZACHASTUYU MOZHNO TAKIM OBRAZOM
SINHRONIZOVATX VYCHISLENIYA S VRASHCHENIEM DISKA, CHTO PRI VYPOLNENII
POSLEDOVATELXNOSTI KOMAND VVODA/VYVODA NE BUDET ZADERZHEK IZ-ZA OZHIDANIYA.

\li rASSMOTRIM ZADACHU CHTENIYA POLOVINY DOROZHKI DANNYH (RIS.~90): ESLI
KOMANDA CHTENIYA VYDAETSYA, KOGDA GOLOVKA NAHODITSYA V TOCHKE $A$, TO ZADERZHKA
NA OZHIDANIE OTSUTSTVUET, I OBSHCHEE VREMYA
CHTENIYA RAVNO VREMENI PEREDACHI, T.E. ${1\over2}\times25$ MS. eSLI
KOMANDA NACHINAETSYA, KOGDA GOLOVKA NAHODITSYA V TOCHKE $B$, TO
TREBUETSYA ${1\over 4}$ OBOROTA DLYA OZHIDANIYA I $1\over2$ DLYA PEREDACHI; V
ITOGE IMEEM
%%431
${3\over4}\times25$ MS. nAIBOLEE INTERESEN SLUCHAJ, KOGDA GOLOVKA
PERVONACHALXNO NAHODITSYA V TOCHKE $C$: IMEYA SOOTVETSTVUYUSHCHEE OBORUDOVANIE I
PROGRAMMNOE OBESPECHENIE, NAM \emph{NE} PRIDETSYA TERYATX $3\over4$ OBOROTA
NA OZHIDANIE. mOZHNO NEMEDLENNO NACHATX CHTENIE VO VTORUYU POLOVINU BUFERA
VVODA, ZATEM POSLE PAUZY V ${1\over2}\times25$ MS .MOZHNO
VOZOBNOVITX CHTENIE V PERVUYU POLOVINU BUFERA, TAK CHTO KOMANDA . BUDET
ZAVERSHENA, KOGDA MY SNOVA POPADEM V TOCHKU $C$. pOSTUPAYA
\picture{rIS. 90. aNALIZ VREMENI OZHIDANIYA PRI CHTENII POLOVINY DOROZHKI}
TAKIM OBRAZOM, MOZHNO GARANTIROVATX, CHTO OBSHCHEE VREMYA NA
OZHIDANIE+PEREDACHU NIKOGDA NE PREVZOJDET VREMENI ODNOGO OBOROTA NEZAVISIMO OT
NACHALXNOGO POLOZHENIYA DISKA. sREDNEE VREMYA OZHIDANIYA UMENXSHAETSYA |TOJ
SHEMOJ S POLOVINY OBOROTA DO ${1\over2}(1-x^2)$
OBOROTA, ESLI CHITAETSYA ILI ZAPISYVAETSYA DOLYA $x$ DOROZHKI ($0<x\le 1$).
eSLI CHITAETSYA ILI ZAPISYVAETSYA CELAYA DOROZHKA ($x=1$), TO |TOT METOD
POZVOLYAET POLNOSTXYU USTRANITX OZHIDANIE.

\section bARABANY: SLUCHAJ, KOGDA POISK NE NUZHEN. nA NEKOTORYH
USTROJSTVAH VNESHNEJ PAMYATI USTANOVLENO PO ODNOJ GOLOVKE CHTENIYA/ZAPISI
DLYA KAZHDOJ DOROZHKI, I PO|TOMU VREMYA POISKA POLNOSTXYU USTRANENO. eSLI NA
TAKOM USTROJSTVE ISPOLXZUETSYA METOD, PRODEMONSTRIROVANNYJ NA RIS.~90, TO
KAK VREMYA POISKA, TAK I VREMYA OZHIDANIYA SVEDENY K NULYU, PRI USLOVII CHTO MY
VSEGDA CHITAEM ILI ZAPISYVAEM VSYU DOROZHKU CELIKOM. v |TOJ IDEALXNOJ
SITUACII VREMYA PEREDACHI YAVLYAETSYA EDINSTVENNYM OGRANICHITELXNYM FAKTOROM.

rASSMOTRIM VNOVX PRIMER IZ P.~5.4.6, V KOTOROM SORTIRUYUTSYA 100000 ZAPISEJ
PO 100 LITER KAZHDAYA S VNUTRENNEJ PAMYATXYU V 100000 LITER. vESX OB�EM
SORTIRUEMYH DANNYH ZANIMAET POLOVINU DISKA |MIXTEC|. oBYCHNO NEVOZMOZHNO
ODNOVREMENNO CHITATX I PISATX NA ODNOM DISKOVOM USTROJSTVE; PO|TOMU
PREDPOLOZHIM, CHTO IMEYUTSYA DVA DISKA, TAK CHTO CHTENIE I ZAPISX MOZHNO SOVMESTITX.
%%432
 pOKA BUDEM SCHITATX, CHTO "DISKI"---|TO FAKTICHESKI \emph{BARABANY},
SODERZHASHCHIE 4000 DOROZHEK PO 5000 LITER KAZHDAYA, I NIKAKOGO VREMENI
POISKA NE TREBUETSYA.

kAKOJ ALGORITM SORTIROVKI SLEDUET ISPOLXZOVATX? eSTESTVENNO VYBRATX
METOD SLIYANIYA; DRUGIE METODY VNUTRENNEJ SORTIROVKI NE STOLX HOROSHI V
PRIMENENII K DISKAM, ZA ISKLYUCHENIEM. VOZMOZHNO, PORAZRYADNYH METODOV, NO
RASSUZHDENIYA V P.~5.4.7 POKAZYVAYUT, CHTO PORAZRYADNAYA SORTIROVKA OBYCHNO
HUZHE SLIYANIYA, ESLI RECHX IDET NE O KAKIH-NIBUDX CHASTNYH PRILOZHENIYAH.
(nETRUDNO VIDETX, CHTO. TEOREMA DVOJSTVENNOSTI, SFORMULIROVANNAYA V |TOM
PUNKTE, PRIMENIMA K DISKAM TOCHNO TAK ZHE, KAK I K LENTAM.)

chTOBY NACHATX SORTIROVKU SLIYANIEM, MOZHNO ISPOLXZOVATX VYBOR S ZAMESHCHENIEM S
DVUMYA BUFERAMI VVODA PO 5000 LITER I DVUMYA BUFERAMI VYVODA PO 5000 LITER,
FAKTICHESKI MOZHNO SVESTI IH K \emph{TREM} BUFERAM PO 5000 LITER, ESLI
ZAMESHCHATX ZAPISI V TEKUSHCHEM BUFERE VVODA NA ZAPISI, VYVODIMYE IZ DEREVA
VYBORA. oSTAETSYA ESHCHE 85000 LITER (850 ZAPISEJ) DLYA DEREVA VYBORA, TAK CHTO
ODIN PROHOD PO DANNYM NASHEGO PRIMERA POZVOLIT SFORMIROVATX OKOLO 60
NACHALXNYH OTREZKOV (SM. FORMULU (5.4.6--3)). eTOT PROHOD ZANIMAET LISHX
OKOLO 50~S, ESLI PREDPOLOZHITX, CHTO SKOROSTX VNUTRENNEJ OBRABOTKI
DOSTATOCHNO VYSOKA, CHTOBY USPETX ZA VVODOM/VYVODOM (KAZHDYE 500~MKS V BUFER
VYVODA DOLZHNA PEREDAVATXSYA ZAPISX). eSLI ZHE SORTIRUEMYE ISHODNYE
DANNYE NAHODYATSYA NA LENTE |MIXT|, A NE NA BARABANE, TO |TOT PROHOD
BUDET VYPOLNYATXSYA MEDLENNEE, I .VREMYA BUDET ZAVISETX OT SKOROSTI LENTY.

nETRUDNO VIDETX, CHTO V SLUCHAE DVUH BARABANOV I PRI CHTENII/ZAPISI POLNYMI
DOROZHKAMI OBSHCHEE VREMYA PEREDACHI DLYA $P$-PUTEVOGO SLIYANIYA UMENXSHAETSYA S
UVELICHENIEM $P$. k SOZHALENIYU, MY NE MOZHEM VYPOLNITX ODNO TOLXKO 60-PUTEVOE
SLIYANIE VSEH NACHALXNYH OTREZKOV, TAK KAK V PAMYATI NET MESTA DLYA 60
BUFEROV. (eSLI RAZMER BUFEROV BUDET MENXSHE 5000 LITER, TO
POYAVITSYA .NEZHELATELXNOE VREMYA OZHIDANIYA.) eSLI MY VYPOLNYAEM
$P$-PUTEVOE SLIYANIE, PEREPISYVAYA VSE DANNYE S ODNOGO BARABANA NA
DRUGOJ TAKIM OBRAZOM, CHTO CHTENIE I ZAPISX SOVMESHCHENY, TO CHISLO PROHODOV
SLIYANIYA RAVNO $\lceil \log_P 60\rceil$; SLEDOVATELXNO, MY MOZHEM ZAKONCHITX
RABOTU ZA DVA PROHODA, ESLI $8\le P \le 59$. s UMENXSHENIEM $P$
UMENXSHAETSYA OB�EM VNUTRENNIH VYCHISLENIJ, PO|TOMU VYBEREM $P=8$; ESLI BUDET
OBRAZOVANO 65 NACHALXNYH OTREZKOV, MY VYBEREM $P=9$. eSLI BUDET OBRAZOVANO
82 ILI BOLXSHE NACHALXNYH OTREZKOV, MY MOZHEM VZYATX $P=10$, NO TAK KAK
IMEETSYA MESTO TOLXKO DLYA 18 BUFEROV VVODA I DVUH BUFEROV VYVODA, TO
POYAVITSYA VOZMOZHNOSTX ZADERZHEK PRI SLIYANII (SM. ALGORITM~5.4.6F); V TAKOM
SLUCHAE, VEROYATNO, LUCHSHE VYPOLNITX DVA CHASTICHNYH PROHODA NAD NEBOLXSHOJ
DOLEJ DANNYH, SOKRATIV CHISLO NACHALXNYH OTREZKOV DO 81 ILI MENXSHE.
%%433
pRI NASHIH PREDPOLOZHENIYAH KAZHDYJ PROHOD SLIYANIYA ZAJMET OKOLO 50~S, TAK CHTO
VSYA SORTIROVKA V |TOJ IDEALXNOJ SITUACII
BUDET ZAVERSHENA ZA $2{1\over2}$~MIN (PLYUS NESKOLXKO SEKUND NA
INICIALIZACIYU I DRUGIE VSPOMOGATELXNYE DEJSTVIYA). eTO V SHESTX
RAZ BYSTREE, CHEM NAILUCHSHAYA IZ SORTIROVOK S SHESTXYU LENTAMI, RASSMOTRENNYH
V P.~5.4.6. pRICHINAMI |TOGO USKORENIYA YAVLYAYUTSYA UVELICHENNAYA SKOROSTX
PEREDACHI DANNYH MEZHDU VNESHNEJ I VNUTRENNEJ PAMYATXYU (ONA V $3{1\over2}$
RAZA VYSHE) , BOLEE VYSOKIJ PORYADOK SLIYANIYA (MY NE MOZHEM OSUSHCHESTVITX
VOSXMIPUTEVOE SLIYANIE
NA LENTAH NE IMEYA DEVYATI ILI BOLXSHEGO CHISLA LENT) I TO, CHTO VYVODNYE
DANNYE OSTAYUTSYA NA DISKE (NET NEOBHODIMOSTI V ZAKLYUCHITELXNOJ PEREMOTKE I
T. D.). eSLI TREBUETSYA, CHTOBY ISHODNYE DANNYE I OTSORTIROVANNYJ REZULXTAT
BYLI NA LENTAH |MIXT|, A BARABANY ISPOLXZUYUTSYA TOLXKO DLYA SLIYANIYA, TO
TAKAYA SORTIROVKA ZAJMET OKOLO 8.2 MIN.

eSLI VMESTO DVUH BARABANOV IMEETSYA TOLXKO ODIN, TO VREMYA VVODA/VYVODA
UVELICHITSYA VDVOE, POSKOLXKU CHTENIE/ZAPISX PRIDETSYA VYPOLNYATX PO
OTDELXNOSTI. (nA SAMOM DELE OPERACII VVODA/VYVODA ZAJMUT V \emph{TRI RAZA}
BOLXSHE VREMENI, POSKOLXKU
ZAPISX BUDET-IDTI POVERH ISHODNYH DANNYH; V TAKIH SLUCHAYAH CELESOOBRAZNO ZA
KAZHDOJ OPERACIEJ ZAPISI VYPOLNYATX OPERACIYU KONTROLXNOGO CHTENIYA, CHTOBY NE
POTERYATX NEOBRATIMO KAKIH-NIBUDX ISHODNYH DANNYH, ESLI TOLXKO
OBORUDOVANIE NE OBESPECHIVAET AVTOMATICHESKOJ PROVERKI ZAPISANNOJ
INFORMACII.) oDNAKO CHASTX |TOGO DOPOLNITELXNOGO VREMENI MOZHNO VOZVRATITX,
POSKOLXKU MY MOZHEM ISPOLXZOVATX CHASTICHNYE PROHODY, PRI KOTORYH ODNI ZAPISI
OBRABATYVAYUTSYA CHASHCHE DRUGIH. v SLUCHAE DVUH BARABANOV TREBUETSYA, CHTOBY VSE
DANNYE OBRABATYVALISX CHETNOE ILI>NECHETNOE CHISLO RAZ, NO V SLUCHAE ODNOGO
BARABANA MOZHNO ISPOLXZOVATX BOLEE OBSHCHIE SHEMY SLIYANIYA.

mY VIDELI V P.~5.4.4, CHTO SHEMY SLIYANIYA MOZHNO IZOBRAZHATX S POMOSHCHXYU
DEREVXEV I CHTO VREMYA PEREDACHI, SOOTVETSTVUYUSHCHEE SHEME SLIYANIYA,
PROPORCIONALXNO DLINE VNESHNEGO PUTI DEREVA. v KACHESTVE SHEM |FFEKTIVNOGO
SLIYANIYA NA LENTAH MOZHNO ISPOLXZOVATX LISHX VPOLNE OPREDELENNYE DEREVXYA
("$T$-lifo" ILI "SILXNYE $T$-fifo"), POTOMU CHTO V PROCESSE SLIYANIYA
NEKOTORYE OTREZKI OKAZYVAYUTSYA "SPRYATANNYMI" V SEREDINE LENTY. nO \emph{PRI
ISPOLXZOVANII DISKOV ILI BARABANOV PRIGODNY LYUBYE DEREVXYA}, ESLI
TOLXKO STEPENI IH VNUTRENNIH UZLOV NE SLISHKOM VELIKI (T. E. SOGLASUYUTSYA
S NALICHNYM OB�EMOM VNUTRENNEJ PAMYATI).

sLEDOVATELXNO, VREMYA PEREDACHI MOZHNO MINIMIZIROVATX, ESLI VYBRATX DEREVO S
MINIMALXNOJ DLINOJ VNESHNEGO PUTI, TAKOE, KAK POLNOE $P$-ARNOE DEREVO, GDE
$P$---SAMOE BOLXSHOE, KAKOE VOZMOZHNO. pO FORMULE (5.4.4--9) DLINA VNESHNEGO
PUTI TAKOGO DEREVA
%% 434
S $S$ VNESHNIMI UZLAMI (LISTXYAMI) RAVNA
$$
qS-\lfloor(P^q-S)/(P-1)\rfloor, \qquad q=\lceil\log_P S\rceil.
\eqno(1)
$$

oSOBENNO PROSTO STROITSYA ALGORITM, KOTORYJ OSUSHCHESTVLYAET SLIYANIE V
SOOTVETSTVII SO SHEMOJ POLNOGO $P$-ARNOGO DEREVA. (sM., NAPRIMER, RIS.~91,
NA KOTOROM POKAZAN SLUCHAJ $P=3$, $S=6$.) sNACHALA MY DOBAVLYAEM, ESLI
NEOBHODIMO, "FIKTIVNYE OTREZKI", CHTOBY SDELATX $S\equiv1 \pmod{P-1}$;
ZATEM OB�EDINYAEM OTREZKI V SOOTVETSTVII S DISCIPLINOJ "PERVYM VKLYUCHAETSYA ---
\picture{rIS. 92. pOLNOE TERNARNOE DEREVO S SHESTXYU LISTXYAMI...}
PERVYM ISKLYUCHAETSYA", SLIVAYA NA KAZHDOM |TAPE $P$ SAMYH "STARYH" OTREZKOV V
NACHALE OCHEREDI V ODIN OTREZOK, POMESHCHAEMYJ V KONEC.

pOLNYE $P$-ARNYE DEREVXYA DAYUT OPTIMALXNUYU SHEMU, ESLI VSE OTREZKI IMEYUT
RAVNUYU DLINU, NO CHASTO REZULXTAT MOZHET BYTX ESHCHE LUCHSHE, ESLI NEKOTORYE
OTREZKI DLINNEE DRUGIH. oPTIMALXNUYU SHEMU DLYA |TOJ OBSHCHEJ SITUACII MOZHNO
BEZ TRUDA POSTROITX S POMOSHCHXYU METODA hAFFM|NA (UPR. 2.3.4.5--10), KOTORYJ
NA YAZYKE SLIYANIYA FORMULIRUETSYA TAK: "SNACHALA DOBAVXTE
$(1-S)\bmod(P-1)$ FIKTIVNYH OTREZKOV DLINY 0, ZATEM MNOGOKRATNO SLIVAJTE
$P$ \emph{KRATCHAJSHIH} IZ IMEYUSHCHIHSYA OTREZKOV, POKA NE OSTANETSYA
ODIN OTREZOK". eSLI VSE NACHALXNYE OTREZKI IMEYUT ODINAKOVUYU DLINU, TO |TOT
METOD SVODITSYA K OPISANNOJ VYSHE DISCIPLINE.

v NASHEM PRIMERE SO 100000, ZAPISEJ MY MOZHEM VYPOLNYATX 9-PUTEVOE SLIYANIE,
TAK KAK V PAMYATI POMESTYATSYA 18 BUFEROV VVODA I DVA BUFERA VYVODA, I V
ALGORITME 5.4.6F BUDET DOSTIGNUTO POLNOE SOVMESHCHENIE VYCHISLENIJ. pOLNOE
9-ARNOE DEREVO
S 60 LISTXYAMI SOOTVETSTVUET SHEME SLIYANIYA S $1{29\over30}$ PROHODA, ESLI.
VSE NACHALXNYE OTREZKI IMEYUT ODINAKOVUYU DLINU. oBSHCHEE VREMYA SORTIROVKI S
ODNIM BARABANOM I S ISPOLXZOVANIEM "KONTROLXNOGO CHTENIYA" POSLE KAZHDOJ
ZAPISI STANOVITSYA, TAKIM OBRAZOM, RAVNYM 7.4 MIN. uVELICHIVAYA $P$, MOZHNO
NEMNOGO UMENXSHITX |TO VREMYA, NO SITUACIYA VESXMA ZAPUTANNAYA, POSKOLXKU NE
ISKLYUCHAETSYA ZADERZHKA CHTENIYA, TAK KAK BUFERY MOGUT OKAZATXSYA SLISHKOM
POLNYMI ILI SLISHKOM PUSTYMI.

%%435
\section vLIYANIE VREMENI POISKA. pREDYDUSHCHEE OBSUZHDENIE POKAZYVAET, CHTO DLYA
BARABANOV OTNOSITELXNO LEGKO SKONSTRUIROVATX "OPTIMALXNUYU" SHEMU SLIYANIYA,
 POSKOLXKU VREMYA POISKA I VREMYA OZHIDANIYA MOZHNO SVESTI NA NET. nO ESLI
ISPOLXZUYUTSYA DISKI, TO POISK INFORMACII ZANIMAET BOLXSHE VREMENI, CHEM EE
CHTENIE. pO|TOMU VREMYA POISKA OKAZYVAET ZNACHITELXNOE VLIYANIE NA STRATEGIYU
SORTIROVKI. uMENXSHENIE PORYADKA SLIYANIYA $P$ DAET VOZMOZHNOSTX .
ISPOLXZOVATX BOLXSHIE PO RAZMERU BUFERY, TAK CHTO REZHE TREBUETSYA POISK; ZA
SCHET |TOGO CHASTO KOMPENSIRUETSYA DOPOLNITELXNOE VREMYA PEREDACHI, KOTOROE
RASTET S UMENXSHENIEM $P$.

vREMYA POISKA ZAVISIT OT RASSTOYANIYA, PROHODIMOGO DERZHATELEM GOLOVOK, I
MOZHNO POPYTATXSYA ORGANIZOVATX RABOTU TAKIM OBRAZOM, CHTOBY |TO RASSTOYANIE
BYLO MINIMALXNYM. bYTX MOZHET, RAZUMNO SNACHALA SORTIROVATX ZAPISI VNUTRI
CILINDROV. oDNAKO DOVOLXNO BOLXSHOE SLIYANIE TREBUET BOLXSHOGO KOLICHESTVA
PEREHODOV. MEZHDU CILINDRAMI (SM., NAPRIMER, UPR.~2). kROME TOGO, REZHIM
MULXTIPROGRAMMIROVANIYA V SOVREMENNYH OPERACIONNYH SISTEMAH OZNACHAET, CHTO
POLXZOVATELX LISHX V REDKIH SLUCHAYAH MOZHET PO-NASTOYASHCHEMU KONTROLIROVATX
POLOZHENIE DERZHATELYA GOLOVOK; BLESTYASHCHIE SHEMY, MINIMIZIRUYUSHCHIE POISK,
OBYCHNO RABOTAYUT TOLXKO PO VYHODNYM DNYAM! tAKIM OBRAZOM, PREDPOLOZHENIE O
TOM, CHTO KAZHDAYA KOMANDA DLYA DISKA TREBUET "SLUCHAJNOGO" POISKA, CHASTO
VPOLNE OPRAVDANO.

nASHA CELX V TOM I SOSTOIT, CHTOBY NAJTI TAKOE DEREVO (T. E. SHEMU SLIYANIYA),
KOTOROE OBESPECHIVAET NAILUCHSHIJ BALANS MEZHDU VREMENEM POISKA I VREMENEM
PEREDACHI; DLYA |TOJ CELI NAM NUZHEN NEKOTORYJ SPOSOB, POZVOLYAYUSHCHIJ OCENITX
DOSTOINSTVA LYUBOGO KONKRETNOGO DEREVA PO OTNOSHENIYU K KONKRETNOJ
KONFIGURACII OBORUDOVANIYA. rASSMOTRIM, NAPRIMER, DEREVO NA RIS.~92;
MY HOTIM OCENITX, SKOLXKO VREMENI ZAJMET VYPOLNENIE'SOOTVETSTVUYUSHCHEGO
SLIYANIYA, CHTOBY MOZHNO BYLO SRAVNITX |TO DEREVO S DRUGIMI.

v POSLEDUYUSHCHIH RASSUZHDENIYAH MY SDELAEM NEKOTORYE PROSTYE PREDPOLOZHENIYA
OTNOSITELXNO SLIYANIYA NA DISKAH, CHTOBY PROILLYUSTRIROVATX NEKOTORYE OBSHCHIE
IDEI. pREDPOLOZHIM, CHTO (1) NA CHTENIE ILI ZAPISX $n$ LITER TREBUETSYA
$72.5+0.005n$~MS; (2) POD RABOCHEE PROSTRANSTVO OTVODITSYA 100000 LITER
VNUTRENNEJ PAMYATI; (3) DLYA PERESYLKI ODNOJ LITERY IZ BUFERA VVODA V
BUFER VYVODA ZATRACHIVAETSYA V SREDNEM $0.004$~MS NA VYCHISLENIE; (4)
\emph{NET SOVMESHCHENIYA} CHTENIYA, ZAPISI I VYCHISLENIJ; (5) RAZMER BUFERA,
 ISPOLXZUEMOGO DLYA VYVODA, NE OBYAZATELXNO DOLZHEN BYTX RAVEN RAZMERU BUFERA,
 ISPOLXZUEMOGO DLYA CHTENIYA DANNYH NA SLEDUYUSHCHEM PROHODE. aNALIZ ZADACHI
SORTIROVKI PRI |TIH PROSTYH PREDPOLOZHENIYAH BUDET POLEZEN DLYA PONIMANIYA
BOLEE SLOZHNYH SITUACIJ.

eSLI VYPOLNYAETSYA $P$-PUTEVOE SLIYANIE, TO MY MOZHEM RAZDELITX
%% 436
VNUTRENNYUYU RABOCHUYU PAMYATX NA $P+1$ BUFERNYH OBLASTEJ: $P$---DLYA VVODA I
1---DLYA VYVODA; V KAZHDOM BUFERE PO $B=100000/(P+1)$ LITER. pREDPOLOZHIM, CHTO
PREDNAZNACHENNYE DLYA SLIYANIYA FAJLY SODERZHALI V SUMME $L$ LITER; TOGDA MY
VYPOLNIM PRIBLIZITELXNO $L/B$ OPERACIJ VYVODA I PRIMERNO STOLXKO ZHE
OPERACIJ VVODA;
SLEDOVATELXNO, OBSHCHEE VREMYA SLIYANIYA PRI TAKIH PREDPOLOZHENIYAH BUDET RAVNO
(V MILLISEKUNDAH) PRIBLIZITELXNO
$$
2\left(72.5{L\over B}+0.005L\right)+0.004L=(0.00145P+0.011545)L.
\eqno(2)
$$

iNYMI SLOVAMI, $P$-PUTEVOE SLIYANIE $L$ LITER ZANIMAET PRIMERNO
$(\alpha P+\beta)L$ EDINIC VREMENI, GDE $\alpha$ I~$\beta$---NEKOTORYE
KONSTANTY,
ZAVISYASHCHIE OT VREMENI POISKA, VREMENI OZHIDANIYA, VREMENI VYCHISLENIJ I
RAZMERA PAMYATI. eTA FORMULA PRIVODIT K INTERESNOMU SPOSOBU POSTROENIYA
HOROSHIH SHEM SLIYANIYA DLYA
\picture{rIS. 92. dEREVO S DLINOJ VNESHNEGO PUTI 16 ...}
DISKOV. rASSMOTRIM, NAPRIMER, RIS.~92 I BUDEM SCHITATX, CHTO VSE NACHALXNYE
.OTREZKI (IZOBRAZHENNYE KVADRATNYMI "LISTXYAMI") IMEYUT DLINU $L_0$.. tOGDA
KAZHDOE SLIYANIE V UZLAH 9 I~10 ZANIMAET $(2\alpha+\beta)(2L_0)$ EDINIC
VREMENI, SLIYANIE V UZLE 11 ZANIMAET $(3\alpha+\beta)(4L_0)$ EDINIC I
OKONCHATELXNOE SLIYANIE V UZLE 12 ZANIMAET $(4\alpha+\beta)(8L_0)$ EDINIC.
oBSHCHEE VREMYA SLIYANIYA, SLEDOVATELXNO, SOSTAVLYAET $(52\alpha + 16\beta)L_0$
EDINIC. kO|FFICIENT "16" NAM HOROSHO IZVESTEN: |TO PROSTO DLINA VNESHNEGO
PUTI DEREVA. kO|FFICIENT "52" PRI $\alpha$ SOOTVETSTVUET NOVOMU PONYATIYU,
KOTOROE MY MOZHEM NAZVATX \dfn{DLINOJ STEPENNOGO PUTI DEREVA}; ONA RAVNA
SUMME, VZYATOJ PO VSEM LISTXYAM, STEPENEJ VNUTRENNIH UZLOV, LEZHASHCHIH NA
PUTI OT LISTA K KORNYU. nAPRIMER, NA RIS.~92 DLINA STEPENNOGO PUTI RAVNA
$(2+4)+(2+4)+(3+4)+(2+3+4)+(2+3+4)+(3+4)+(4)+(4)=52$.

eSLI $\cJ$---LYUBOE DEREVO, TO PUSTX $D(\cJ)$, $E(\cJ)$
OBOZNACHAYUT SOOTVETSTVENNO DLINU STEPENNOGO PUTI I DLINU VNESHNEGO
PUTI |TOGO DEREVA. aNALIZ SVODITSYA K SLEDUYUSHCHEJ TEOREME:

%% 437
\proclaim tEOREMA H. eSLI VREMYA, TREBUEMOE DLYA VYPOLNENIYA
$P$-PUTEVOGO SLIYANIYA $L$ LITER, IMEET VID $(\alpha P+\beta)L$ I ESLI
TREBUETSYA SLITX $S$ OTREZKOV RAVNOJ DLINY, TO NAILUCHSHAYA SHEMA SLIYANIYA
SOOTVETSTVUET DEREVU $\cJ$, DLYA KOTOROGO $\alpha D (\cJ)+\beta E(\cJ)$
MINIMALXNO SREDI VSEH DEREVXEV S $S$ LISTXYAMI.

\noindent (eTA TEOREMA NEYAVNO SODERZHALASX V NEOPUBLIKOVANNOJ STATXE,
 KOTORUYU dZHORDZH a. hABB|RD PREDSTAVIL NA NACIONALXNUYU KONFERENCIYU ACM V
1963 G.)

pUSTX $\alpha$ I $\beta$---FIKSIROVANNYE KONSTANTY; BUDEM GOVORITX, CHTO
DEREVO \dfn{OPTIMALXNO}, ESLI ONO IMEET MINIMALXNOE ZNACHENIE $\alpha
D(\cJ)+\beta E (\cJ)$ SREDI VSEH DEREVXEV $\cJ$ S TEM ZHE CHISLOM
LISTXEV. nETRUDNO VIDETX, CHTO \emph{VSE PODDEREVXYA OPTIMALXNOGO DEREVA
TAKZHE OPTIMALXNY}. pO|TOMU MY MOZHEM STROITX OPTIMALXNYE DEREVXYA S $n$
LISTXYAMI, OB�EDINYAYA OPTIMALXNYE DEREVXYA, U KOTORYH MENXSHE CHEM $n$ LISTXEV.

\proclaim tEOREMA K. pUSTX POSLEDOVATELXNOSTX CHISEL $A_m(n)$ OPREDELENA
PRI $1\le m\le n$ PRAVILAMI
$$
\eqalignno{
A_1(1)&=0; & (3) \cr
A_m(n)&=\min_{1\le k\le n/m} (A_1(k)+A_{m-1}(n-k)
\rem{PRI $2\le m\le n$;} & (4) \cr
A_1(n)&=\min_{2\le m\le n} ((\alpha mn+\beta n+A_m(n))
\rem{PRI $n\ge 2$.} & (5)\cr
}
$$
tOGDA  $A_1(n)$ ESTX MINIMALXNOE ZNACHENIE
$\alpha D (\cJ) +\beta E(\cJ)$ SREDI VSEH DEREVXEV $\cJ$ S $n$ LISTXYAMI.

\proof iZ SOOTNOSHENIYA (4) SLEDUET, CHTO $A_m(n)$ ESTX MINIMALXNOE ZNACHENIE
$A_1(n_1)+\cdots+A_1(n_m)$ PO VSEM POLOZHITELXNYM CHISLAM
$n_1$, \dots, $n_m$, TAKIM, CHTO
$n_1+\cdots+n_m=n$. tREBUEMYJ REZULXTAT POLUCHAETSYA TEPERX INDUKCIEJ
PO~$n$.
\proofend

rEKURRENTNYE SOOTNOSHENIYA (3), (4), (5) MOZHNO ISPOLXZOVATX TAKZHE DLYA
POSTROENIYA SAMIH OPTIMALXNYH DEREVXEV. pUSTX $k_m(n)$---ZNACHENIE, DLYA
KOTOROGO DOSTIGAETSYA MINIMUM V OPREDELENII $A_m(P)$. tOGDA MOZHNO
POSTROITX OPTIMALXNOE DEREVO S $n$ LISTXYAMI, OB�EDINYAYA $m=k_1(n)$
PODDEREVXEV V KORNE; PODDEREVXYA YAVLYAYUTSYA OPTIMALXNYMI DEREVXYAMI S $k_m(n)$,
 $k_{m-1}(n-k_m(n))$, $k_{m-2}(n-k_m(n)-k_{m-1}(n-k_m(n)))$, \dots
LISTXYAMI SOOTVETSTVENNO.

eTA KONSTRUKCIYA PRI $\alpha=\beta=1$ PROILLYUSTRIROVANA V KACHESTVE PRIMERA
V TABL.~1. kOMPAKTNYE OPISANIYA SOOTVETSTVUYUSHCHIH OPTIMALXNYH DEREVXEV
IMEYUTSYA V PRAVOJ CHASTI TABLICY; |LEMENT "4:9:9" DLYA $n=22$, NAPRIMER,
OZNACHAET, CHTO OPTIMALXNOE DEREVO $\cJ_22$ S 22 LISTXYAMI MOZHNO POLUCHITX V
REZULXTATE OB�EDINENIYA $\cJ_4$, $\cJ_9$ I~$\cJ_9$ (RIS.~93). oPTIMALXNYE
DEREVXYA NE EDINSTVENNY;
NAPRIMER, |LEMENT 5:8:9 BYL BY STOLX ZHE HOROSHIM, KAK I 4:9:9.
%% 438
\bye
