Sunday, July 12, 2015

Հեշավորում (թարգմանության փորձ)

Թարգմանված է Նիկլաուս Վիրտի «Ալգորիթմներ
և տվյալների կառուցվածքներ» գրքից։

5 Բանալիների բաշխում (Հեշավորում)

5.1 Ներածություն

Չորրորդ գլխում քննարկվող սկզբունքային հարցը հետևյալն էր․ եթե տրված է բանալիով (key) բնութագրվող տարրերի բազմություն (բանալու վրա սահմանված է նաև կարգի հարաբերություն), ապա ինչպե՞ս կազմակերպել այդ բազմությունը, որպեսզի տրված բանալիով տարրին դիպելու համար պահանջվի նվազագույն ջանք։ Պարզ է, որ կոմպյուտերի հոշողության մեջ գտնվող որևէ տարրին դիմելու համար պետք է ունենալ նրա հասցեն։ Հետևաբար, նշված խնդիրը բերվում է K բանալիները A հասցեներին արտապատկերող H ֆունկցիայի սահմանմանը։

H: K → A

Չորրորդ գլխում այդ արտապատկերումը իրականացվում էր զանազան տվյալների կառուցվածքների վրա հիմնված ցուցակներում և ծառերում որոնման տարբեր ալգորիթմներով։ Այստեղ ներկայացնում ենք ըստ էութան պարզ և շատ դեպքերում արդյունավետ ևս մի եղանակ։ Այնուհետև կքննարկենք նաև այդ եղանակի որոշ թերություններ։

Այս մոտցման մեջ տվյալները կազմակերպվում են զանգվածի տեսքով։ Այս դեպքում H֊ը բանալիները զանգվածի ինդեքսներին բաշխող արտապատկերում է, որտեղից էլ հենց առաջացել է այս մեթոդի համար օգտագործվող բանալիների բաշխում անվանումը։ Պետք է նշել, որ այս դեպքում կարիք չունենք հիշողության դինամիկ առանձնացնող գործողությունների․ զանգվածը մեկն է հիմնարար, ստատիկ կառուցվածքներից։ ?? Բանալիների բաշխման մեթոդը հաճախ օգտագործվում է այն խնդիրներում, որտեղ մոտավորապես նույն հաջողությամբ կարելի է օգտագործել նաև ծառաձև կառուցվածքները։

Բանալիների բաշխման եղանակն օգտագործելիս հիմնական դժվարությունն այն է, որ թույլատրելի բանալիների բազմությունն էապես ավելի մեծ է, քան հիշողության մատչելի հասցեները (զանգվածի ինդեքսները)։ Որպես բանալի վերցնենք, օրինակ, մինչև 16 նիշ պարունակող անունները, որոնք հազարավոր մարդկանց մեջ նույնականացնում են առանձին անհատների։ Այսինքն, գոյություն ունեն 26^16 հնարավոր բանալիներ, որոնք պետք է արտապատկերել 10^3 հնարավոր ինդեքսների։ Ակնհայտ է, որ այս դեպքում H֊ը շատը֊մեկին ֆունկցիա է։ Եթե տրված է k բանալին, ապա որոնման գործողության առաջին քայլը h=H(k) ինդեքսի հաշվարկումն է, իսկ երկրորդ, ակնհայտորեն պարտադիր, քայլը ստուգելն է, թե արդյո՞ք k բանալիով տարրը համապատասխանում է T զանգվածի (աղյուսակի) h ինդեքսով տարրին, այսինքն, ստուգել T[H(k)].key = k հավասարությունը։ Անմիջապես հանդիպում ենք հետևյալ երկու հարցերին․

  1. Ինչպիսի՞ն պետք է լինի H ֆունկցիան։
  2. Ի՞նչ անել, եթե H ֆունկցիան չի կարողացել հաշվել որոնելի տարրի դիրքը։

Երկրորդ հարցի պատասխանը կայանում է նրանում, որ պետք է ունենալ մի մեթոդ, որը վերադարձնում է այլընտրանաքային դիրք, ասենք h', եթե այդ նոր դիրքն էլ նորից չի պարունակում որոնելի տարրը, ապա վերադարձնում է h'' դիրքը, և այդպես շարունակ։ ?? Եթե հաշվարկված դիրքում գտնվում է որոնելի տարրից տարբերվող մի այլ տարր, ապա այդ իրավիճակը կոչվում է կիլիզիա (collision), իսկ այլընտրանքային դիրքի հաշվարկը՝ կոլիզիայի լուծում։ Ստորև կքննարկենք բանալիների բաշխման ֆունկցիայի ընտրությունը և կոլիզիայի լուծման եղանակները։

5.2 Հեշավորող ֆունկցիայի ընտրությունը

Լավ բաշխման ֆունկցիայի համար կարևոր նախապայմանն է, որ այն կարողանա բանալիների բազմությունը հնարավորինս հավասարաչափ բաշխել ինդեքսների արժեքների ամբողջ միջակայքին։ Այս պայմանից բացի բաշխման համար այլ սահմանափակումներ չկա, սակայն իրականում ցանկալի է, որ այն նման լինի պատահական բաշխման։ Այսպիսի առանձնահատկությունը բանալիների բաշխման մեթոդին տվել է թերևս ոչ֊գիտական մի անվանում՝ հեշավորում (hashing), այսինքն՝ արգումենտի կտրտում, վերածում ինչ֊որ «խյուսի»։ ?? H֊ն էլ կոչվում է հեշավորող ֆունկցիա (հեշ֊ֆունկցիա)։ Պարզ է, որ H֊ը պետք է լինի էֆեկտիվ հաշվարկվող, այսինքն՝ բաղկացած լինի շատ քիչ թվով թվաբանական գործողություններից։

Դիցուք կարող ենք օգտագործել ORD(k) ֆունկցիան, որը վերադարձնում է k բանալու հերթական համարը՝ կարգաթիվը, բոլոր հնարավոր բանալիների բազմության մեջ։ Ենթադրենք նաև, որ զնգվածի i ինդեքսը տարածվում է 0֊ից մինչև N-1, որտեղ N֊ը զանգվածի տարրերի քանակն է։ Այս դեպքում ընտրությունն ակնհայտ է․

H(k) = ORD(k) MOD N

Այս ֆունկցիան ապահովում է բանալիների հավասարաչափ բաշխումն ինդեքսների ամբողջ միջակայքում և հենց դրա համար էլ օգտագործվում է շատ հեշ֊ֆունկցիաներում։ Այն նաև շատ արդյունավետ հաշվարկվում է, եթե N֊ը երկուսի աստիճան է։ Սակայն եթե բանալին տառերի հաջորդականություն է, ապա հենց այսպիսի ֆունկցիայից պետք է խուսափել։ Բանն այն է, որ այս դեպքում բոլոր բանալիների՝ հույն հավանականությամբ հանդիպելու ենթադրությունը սխալ է։ Իրականում բառերը, որոնք տարբերվում են միայն մի քանի տառերով, մեծ հավանականությամբ կարող են արտապատկերվել դույն ինդեքսին, որն էլ կստեղծի խիստ անհավասարաչափ բաշխում։ Այս պատճառով էլ գործնականում խորհուրդ է տրվում N֊ը վերցնել մի որևէ պարզ թիվ [5-2]։ Որպես հետևանք արդեն հարկ է լինում օգտագործել լրիվ բաժանման գործողություն, որը հնարավոր չէ փոխարինել երկուական թվանշանների կրճատումով։ Սակայն ժամանակակից կոմպյուտերներում սա դժվար խնդիր չէ, քանի որ դրանցում առկա է ներդրված բաժանման գործողություն։ ??

Հաճախ օգտագործվում են բանալու որևէ հատվածի երկուական ներկայացման վրա կիրառվող տրամաբանական գործողություններից կառուցված հեշավորող ֆունկցիաներ (այդպիսի գործողություններից է, օրինակ, «բացառող կամ»-ը)։ ?? Որոշ կոմպյուտերների վրա այս գործողությունները կարող են կատարվել ավելի արագ, քան բաժանումը, բայց հաճախ դրանք բերում են ինդեքսերի միջակայքում բանալիների զարմանալի անհավասարաչափ բաշխման։ Այդ պատճառով էլ ձեռնպահ կմնանք այդպիսի մեթոդների հետագա քննարկումից։

5.3 Կոլիզիաների լուծումը

Եթե պարզվում է, որ աղյուսակի՝ տրված բանալուն համապատասխանեցված տարրը որոնելին չէ, ապա տեղի ունի կոլիզիա, այսինքն՝ երկու տարբեր տարրերի բանալիներ արտապատկերվում են նույն ինդեքսին։ Այս դեպքում անհրաժեշտ է երկրորդ փորձը՝ տրված բանալուց խիստ որոշակի եղանակով ստացվող ինդեքսի օգտագործմամբ։ ?? Գոյություն ունեն երկրորդային ինդեքսների հաշվարկման մի քանի մեթոդներ։ Ակնհայտ եղանակ է՝ կապակցված ցուցակում հավաքել նույն H(k) առաջնային ինդեքս ունեցող տարրերը։ Սա կոչվում է ուղիղ կապակցում (direct chaining)։ Այս ցուցակի տարրերը կարող են առաջնային աղյուսակում լինել կամ չլինել, երկրորդ դեպքում դրանց զբաղեցրած հիշողության տիրույթը կոչվում է գերբեռնվածության տիրույթ (overflow area)։ Այս հնարքի թերությունն այն է, որ պետք է կազմակերպել երկրորդային ցուցակների հետ աշխատանքը, ինչպես նաև աղյուսակի ամեն մի տարրը պետք է ցուցիչ (կամ ինդեքս) ունենա խնդրահարույց տարրերի ցուցակի համար։

Կոլիզիաների լուծման այլընտրանքային եղանակ է՝ ընդհանրապես հրաժարվել ցուցակներից և պարզապես դիտարկել նույն աղյուսակի մյուս տարրերը, մինչև կգտնվի տարրը կամ կգտնվի ազատ դիրք։ Վերջին դեպքում համարում ենք, որ որոնվող տարրն աղյուսակում բացակայում է։ Այս եղանակը կոչվում է բաց հասցեավորում (open addressing) [5-3]։ Բնականաբար, տրված բանալու համար երկրորդային փորձերի ինդեքսների հաջորդականությունը միշտ պետք է նույնը լինի։ Ըստ ասվածի, որոնման ալգորիթմը կարող է ունենալ հետևյալ տեսքը․

h := H(k); i := 0;
REPEAT
  IF T[h].key = k THEN տարր գտնված է
  ELSIF T[h].key = free THEN տարրն աղյուսակում չէ
  ELSE (* կոլիզիա *)
    i := i+1; h := H(k) + G(i)
  END
UNTIL գտնված կամ աղյուսակում չէ (կամ աղյուսակը լիքն է)

Կոլիզիաների լուծման տարբեր եղանակներ են առաջարկվլ գրականության մեջ։ Մորիսի (Morris) կողմից 1968-ին թեմայի ուսումնասիրությունը [5-2] բավականին աշխուժություն բերեց ոլորտ։ Ամենապարզ ձևը՝ դիտարկել աղյուսակի հերթական տարրը (համարենք աղյուսակը շրջանաձև), մինչև կգտնվի տրված բանալիով տարրը կամ կգտնվի դատարկ տեղ։ Այսպիսով, G(i) = i, իսկ հաջորդկան փորձերի համար օգտագործվող h_i ինդեքսները որոշվում են հետևյալ կերպ․

h_0 = H(k)
h_i = (h_i-1 + i) MOD N,    i = 1 ... N-1

Սա կոչվում է գծային փորձերի եղանակ (linear probing)։ Նրա թերությունն այն է, որ տարրերը ձգտում են կուտակվել առաջնային բանալիների շուրջը (այսինքն՝ այն բանալիների շուրջը, որոնք ավելացնելիս կոլիզիա չի առաջացել)։ Իհարկե, իդեալական դեպքում G ֆունկցիան էլ պետք է բանալիները հավասարաչափ բաշխի ազատ դիրքերի բազմության վրա։ Սակայն գործնականում բավականին դժվար է ապահովել այդ պահանջը, և այս դեպքում նախընտրում են փոխզիջումային մեթոդներ, որոնք պահանջում են բարդ հաշվարկներ, բայց ավելի լավն են քան գծային ֆունկցիան։ Դրանցից մեկում օգտագործվում է քառակուսային ֆունկցիան այնպես, որ հաջորդական փորձերի ինդեքսները որոշվում են հետևյալ կերպ․

h_0 = H(k)
h_i = (h_0-1 + i^2) MOD N,    i > 0

Նկատենք, որ հերթական ինդեքսը հաշվելիս կարելի է ազատվել քառակուսի բարձրացնելու գործողությունից, եթե h_i = i^2 և d_i = 2i + 1 համար օգտագործենք հետևյալ անդրադարձ առնչությունները․

h_i+1 = h_i + d_i
d_i+1 = d_i + 2,    i >0

որտեղ h_0 = 0 և d_0 = 1։ Սա կոչվում է քառակուսային փորձերի մեթոդ (quadratic probing), և ըհդհանուր դեպքում այն շրջանցում է վերը նշված կուտակումների խնդիրը՝ գործնականում չպահանջելով լրացուցիչ հաշվարկներ։ Մի փոքր թերությունն այն է, որ հաջորդական փորձերի ժամանակ աղյուսակի ոչ բոլոր տարրերն են ստուգվում, այսինքն տարրն ավելացնելիս հնարավոր է չնկատել ազատ դիրքը, թեև աղյուսակում այդպիսիք կան։ Իրականում, եթե N-ը պարզ թիվ է, ապա քառակուսային փորձերի մեթոդով ստուգում է աղյուսակի ամենաքիչը կեսը։ Այս պնդումը կարելի է դուրս բերոլ հետևյալ կերպ։ Այն փաստը, որ i-րդ և j-րդ փորձերը բերում են այսուսակի նույն տարրին, արտահայտվում է հետևյալ հավասարությամբ․

i^2 MOD N = j^2 MOD N
(i^2 - j^2) ≡ 0 (modullo N)

Քառակուսիների տարբերությունն արտահայտելով երկու արտադրիչներով ստանում ենք․

(i + j)(i - j) ≡ 0 (modulo N)

և քանի որ i ≠ j, ապա եզրակացնում ենք, որ i և j թվերից գոնե մեկը պետք է փոքր լինի N/2-ից, որպեսզի ամբողջաթիվ c-ի համար ստանանք i + j = c * N։ Գործականում այս թերությունն էական չէ, քանի որ կոլիզիայի լուծման համար N/2 փորձեր հազվադեպ են կատարվում, այն էլ միայն այն դեպքում, երբ աղյուսակը համարյա լիքն է։

Որպես քննարկված տեխնիկայի կիրառություն բերված է 4.4.3 բաժնի խաչաձև հղումներ գեներացնող ծրագրի ձևափոխությունը։ ?? Հիմնական տարբերությունները search պրոցեդուրայում են և T գլոբալ հեշ աղյուսակի Node ցուցաչային տիպի փոխարինելում։ ?? Հեշ-ֆունկցիա H-ը հաշվարկվում է որպես աղյուսակի չափի վրա բաժանման մնացորդ (modulus)։ Կոլիզիաների լուծման համար օգտագործված է քառակուսային փորձերի մեթոդը։ Նշենք նաև, որ լավ արտադրողականության համար շատ կարևոր է աղյուսակի չափի պարզ թիվ լինելը։

Չնայած որ այս խնդրի համար հեշավորման մեթոդը բավականին արդյունավետ է, նույնիսկ ավելի արդյունավետ, քան ծառաձև կառուցվածքները, այն ունի նաև թերություններ։ Տեքստը կարդալուց և բառերն առանձնացնելուց հետո մենք, հավանաբար, կուզենանք դրանք դասավորել այբբենական կարգով։ Դա դժվար չէ, եթե օգտագործվում են ծառաձև կառուցվածքներ, քանի որ կարգավորվածությունն ընկած է ծառաձև կառուցվածքների հիմքում։ ?? Սակայն գործը դժվարանում է բանալիների բաշխում օգտագործելիս։ ?? Այստեղ է, որ բացահայտվում է «հեշավորում» բառի ամբողջ իմաստը։ Աղյուսակն արտածելու համար պետք է ոչ միայն այն կարգավորել (այդ կտորն այստեղ բաց է թողնված), այլև բացահայտ հետևել աղյուսակում ավելացվող բանալիներին՝ դրանք հավաքելով կապակցված ցուցակում։ Այդ պատճառով էլ հեշավորման ժամանակ որոնման բարձր արագությունը մասնակիորեն փոխհատուցվում է լրացուցիչ գործողություններով, որոնք հարկավոր են խաչաձև հղումների խնդիրն ամբողջությամբ լուծելու համար։

CONST N = 997; (* պարզ թիվ, աղյուսակի չափը *)
  WordLen = 32; (* բանալիների առավելագույն երկարությունը *)
  Noc = 16; (* տարրերի առավ․ քանակը մեկ բառում *)

TYPE
  Word = ARRAY WordLen OF CHAR;
  Table = POINTER TO ARRAY N OF
    RECORD key: Word; n: INTEGER;
      lno: ARRAY Noc OF INTEGER
    END;

VAR line: INTEGER;

PROCEDURE search (T: Table; VAR a: Word);
  VAR i, d: INTEGER; h: LONGINT; found: BOOLEAN;
BEGIN (* հաշվել h հեշ ինդեքսը a-ի համար; օգտագործում է line գլոբալ փոփոխականը*)
  i := 0; h := 0;
  WHILE a[i] > 0X DO h := (256*h + ORD(a[i])) MOD N; INC(i) END;
  d := 1; found := FALSE;
  REPEAT
    IF T[h].key = a THEN (* համընկնում *)
      found := TRUE; T[h].lno[T[h].n] := line;
      IF T[h].n < Noc THEN INC(T[h].n) END
    ELSIF T[h].key[0] = " " THEN (* աղյուսակի նոր տարր *)
      found := TRUE; COPY(a, T[h].key); T[h].lno[0] := line; T[h].n := 1
    ELSE (* կոլիզիա *) h := h+d; d := d+2;
      IF h >= N THEN h := h-N END;
      IF d =N THEN
        Texts.WriteString(W," Աղյուսակը գերբեռնված է"); HALT(88)
      END
    END
  UNTIL found
END search;

PROCEDURE Tabulate (T: Table); (* օգտագործվում է W գլոբալ օբյեկտը *)
  VAR i, k: INTEGER;
BEGIN
  FOR k := 0 TO N-1 DO
    IF T[k].key[0] # " " THEN
      Texts.WriteString(W, T[k].key); Texts.Write(W, TAB);
      FOR i := 0 TO T[k].n -1 DO Texts.WriteInt(W, T[k].lno[i], 4) END;
      Texts.WriteLn(W)
   END
  END
END Tabulate;

PROCEDURE CrossRef (VAR R: Texts.Reader);
  VAR i: INTEGER; ch: CHAR; w: Word;
    H: Table;
BEGIN
  NEW(H); (* ստեղծել հեշ աղյուսակը *)
  FOR i := 0 TO N-1 DO H[i].key[0] := " " END;
  line := 0;
  Texts.WriteInt(W, 0, 6); Texts.Write(W, TAB); Texts.Read(R, ch);
  WHILE ~R.eot DO
    IF ch = 0DX THEN (*line end*) Texts.WriteLn(W);
      INC(line); Texts.WriteInt(W, line, 6); Texts.Write(W, 9X); Texts.Read(R, ch)
    ELSIF ("A" <= ch) & (ch <= "Z") OR ("a" <= ch) & (ch <= "z") THEN
      i := 0;
      REPEAT
        IF i < WordLen-1 THEN w[i] := ch; INC(i) END;
        Texts.Write(W, ch); Texts.Read(R, ch)
      UNTIL (i = WordLen-1) OR ~(("A" <= ch) & (ch <= "Z")) &
            ~(("a" <= ch) & (ch <= "z")) & ~(("0" <= ch) & (ch <= "9"));
      w[i] := 0X; (*string terminator*)
      search(H, w)
    ELSE Texts.Write(W, ch); Texts.Read(R, ch)
    END;
    Texts.WriteLn(W); Texts.WriteLn(W); Tabulate(H)
  END
END CrossRef

5.4 Բանալիների բաշխման մեթոդի վերլուծությունը

Բանալիների բաշխման մեթոդի վատագույն դեպքում բանալին ավելացնելու և որոնելու արտադրողականությունը սարսափելի է։ Լրիվ հնարավոր է, որ որոնման արգումենտնը փորձերի ժամանակ անցնի բոլոր զբաղված դիրքերով՝ ոչ մի անգամ չընկնելով աղյուսակի անհրաժեշտ (կամ ազատ) դիրքի վրա։ ?? Հեշավորման տեխնիկան օգտագործելու համար պետք է բավականաչափ վստահ լինել հավանականության տեսության օրենքներին։ Մենք պարզապես ուզում ենք համոզված լինել, որ փորձերի միջին թիվը փոքր է։ Ստորև բերված հավանակային փաստարկներն ցույց են տալիս, որ այդ թիվը ոչ թե փոքր է, այլ շատ փոքր է։

Մեկ անգամ էլ ենթադրենք, որ բոլոր բանալիների հանդիպելու հավանականությունը հավասար է, իս H հեշ-ֆունկցիան դրանք հավասարաչափ բաշխում է աղյուսակի ինդեքսների միջակայքի վրա։ Ենթադրենք նաև, թե բանալին պետք է ավելացվի արդեն k հատ տարրեր պարունակող և N չափ ունեցող աղյուսակի մեջ։ Այդ դեպքում առաջին փորձից ազատ դիրքի վրա ընկնելու հավանականությունը (N-k)/N է։ Սա նաև միայն մեկ համեմատում կատարելու p_1 հավանականությունն է։ Հավանականությունը, որ պետք կլինի ճիշտ մեկ երկրորդային փորձ, հավասար է առաձին փորձում կոլիզիայի հավանականությանը՝ բազմապատկած երկրորդ փորձում ազատ դիրքի վրա ընկնելու հավանականությանը։ Այսպիսով, ստանում ենք ճիշտ i փորձեր կատարելու p_i հավանականության հաշվման հետևյալ եղանակը․

p_1 = (N-k)/N
p_2 = (k/N) × (N-k)/(N-1)
p_3 = (k/N) × (k-1)/(N-1) × (N-k)/(N-2)
..........
p_i = (k/N) × (k-1)/(N-1) × (k-2)/(N-2) × ... × (N-k)/(N-(i-1))

Այստեղից էլ աղյուսակում k+1-րդ բանալին ավելացնելու փորձերի E քանակը հավասար է․ ??

E_k+1 = __S__i: 1 ≤ i ≤ k+1 : i × pi = 1 × (N-k)/N + 2 × (k/N) × (N-k)/(N-1) + ... + (k+1) * (k/N) × (k-1)/(N-1) × (k-2)/(N-2) × ... × 1/(N-(k-1)) = (N+1) / (N-(k-1))

Քանի որ տարրն աղյուսակում ավելացնելու փորձերի քանակը հավասար է նրա որոնման փորձերի քանակին, այս արդյունքը կարելի է օգտագործել աղյուսակում պատահական բանալին գտնելու փորձերի E քանակը հաշվելու համար։ Թող նորից N-ը ցույց տա աղյուսակի տարրերի քանակը, և թող m-ը լինի աղյուսակում առկա բանալիների քանակը։ Այդ դեպքում․

E = (Sk: 1 ≤ k ≤ m : Ek) / m = (N+1) × (Sk: 1 ≤ k ≤ m : 1/(N-k+2))/m = (N+1) × (HN+1 - HN-m+1)

որտեղ H-ը հարմոնիկ ֆունկցիան է։ H-ը կարելի է մոտարկել որպես H_N = ln(N) + g, որտեղ g-ն Էյլերի հաստատունն է։ Այնուհետև, եթե m/(N+1)-ը փոխարինենք a-ով, կստանանք․

E = (ln(N+1) - ln(N-m+1))/a = ln((N+1)/(N-m+1))/a = -ln(1-a)/a

a-ն մոտավորապես աղյուսակի զբաղված և ազատ դիրքերի քանակների հարաբերությունն է, որ կոչվում է լրացվածության գործակից (load factor)։ a=0-ն նշանակում է դատարկ աղյուսակ, իսկ a= N/(N+1) ≈ 1-ը՝ լցված աղյուսակ։ Պատահական բանալին աղյուսկում ավելացնելու կամ որոնելու փորձերի E միջին քանակը Աղյուսակ 5.1-ում թվարկված է որպես լրացվածության գործակցի ֆունկցիա։

a      E
0.1    1.05
0.25   1.15
0.5    1.39
0.75   1.85
0.9    2.56
0.95   3.15
0.99   4.66

Աղյուսակ 5.1։ Փորձերի ակնկալվող թիվը որպես լրացվածության գործակցի ֆունկցիա։

Զարմանալի թվեր են ստացվել և դրանք բացատրում են բանալիների բաշխման մեթոդի բացառիկ բարձր արտադրողականությունը։ Նույնիսկ եթե աղյուսակը 90%-ով լիքն է, միջինում 2.56 փորձ է հարկավոր՝ բանալին կամ դատարկ տեղ գտնելու համար։ Հատուկ նշենք, որ այս թիվը կախված է միայն լրացվածության գործակցից և ոչ բանալիների ընդհանուր քանակից։

Բերված վերլուծությունը հիմնված է աղյուսակի ազատ դիրքերի վրա բանալիները հավասարաչափ բաշխող կոլիզիաները լուծող մեթոդի վրա։ ?? Գործնականում օգտագործվող մեթոդները տալիս են քիչ ավելի վատ արդյունք։ Գծային փորձերի մեթոդի մանրամասն վերլուծությունը փորձերի միջին թվի համար տալիս է հետևյալ արդյունքը․

E = (1 - a/2) / (1 - a)

Որոշ թվային արդյունքներ բերված են Աղյուսակ 5.2-ում [5.4].

a     E
0.1   1.06
0.25  1.17
0.5   1.50
0.75  2.50
0.9   5.50
0.95  10.50

Աղյուսակ 5.2. Ակնկալվող փորձերի քանակը գծային փորձերի համար։

Կոլիզիաների լուծման նույնիսկ ամենապարզ մեթոդի արդյունքներն այնքան լավն են, որ գոյթակղություն է առաջանում հեշավորման մեթոդն օգտագործել որպես կյանքի բոլոր դեպքերի փրկարակ միջոց։ Մասնավորապես այն պատճառով, որ նրա արտադրողականությունը գերազանցում է նույնիսկ ամենակատարյալ ծառաձև կառուցվածքներով մեթոդներինը, հենց միայն տարրը որնելու և ավելացնելու համար համեմատությունների տեսակետից։ ?? Եվ հենց այս տեսակետից է կարևոր նշել հեշավորման մի քանի թերությունները, եթե նույնիսկ դրանք ակնհայտ են անշահախնդիր վերլուծության ժամանակ։

Իհարկե, հիշողության դինամիկ կառավարում օգտագործող մեթոդների համեմատությամբ գլխավոր թերությունը աղյուսակի ֆիքսված չափն է, որը չի կարող փոխվել ըստ անհրաժեշտության։ Այդ պատճառով էլ, եթե անընդունելի է հոշողության ոչ-խնայողական օգտագործումը կամ ցածր արտադրողականությունը (կամ աղյուսակի գերբեռնվածությունը), ապա հարկավոր է մշակվող տվյալների տարրերի քանակի բավականաչափ լավ նախնական վերլուծություն։ Նույնիսկ եթե տարրերի քանակը չիշտ հայտնի է, որ հազվադեպ է պատահում, լավ արտադրողականության համար ձգտումը ստիպում է ընտրել քիչ ավելի մեծ (ասենք, 10%) աղյուսակ։

Բաշխման մեթոդների երկրորդ մեծ թերություն ակնհայտ է դառնում, երբ աղյուսակում պետք է ոչ միայն որոնել կամ ավելացնել տարրը, այլև հեռացնել այն։ Հեշ-աղյուսակից տարրերի հեռացնելը չափազանց ծանր է, եթե միայն առանձին գերբեռնվածության տիրույթում ուղիղ կամապցումը չէ օգտագործված։ Այդ պատճառով էլ արդարացի կլինի նշել, որ ծառաձև կառուցվածքների օգտագործումը դեռևս ավելի գայթակղիչ է, հույնիսկ ավելի նախընտրելի է, եթե մշակվող տվյալների ծավալն ակնկանխատեսելի է, խիստ տատանվում է իսկ երբեմն նաև պակասում է։

Sunday, July 5, 2015

1.8 Որոնում (թարգմանության փորձ)

Թարգմանված է Նիկլաուս Վիրտի «Ալգորիթմներ
և տվյալների կառուցվածքներ» գրքից։

Որոնումը կոմպյուտերային ծրագրավորման ամենից շատ հանդիպող գործողություններից է։ Այն նաև իդեալական խնդիր է զանազան տվյալների կառուցվածքները փորձարկելու համար։ ?? Գոյություն ունեն որոնման թեմայի մի քանի վարաիցիաներ, և մշակված են բազմաթիվ ալգորիթմներ։ Հետևյալ քննարկումներում ենթադրվում է, որ տվյալների հավաքածուն, որի մեջ որոնվելու է տրված տարրը, ֆիքսված է։ Կհամարենք, որ N տարրերի բազմությունը տրված է, օրինակ, զանգվածի տեսքով․

a : ARRAY N OF Item

Սովորաբար Item տիպը նկարագրված է որպես գրառում (record), որի դաշտերից մեկը բանալին (key) է։ Խնդիրը բերվում է այն տարրի գտնելուն, որի բանալին հավասար է x որոնման արգումենտին։ Արդյունքում ստացված i ինդեքսը, որ բավարարում է a[i].key = x պայմանին, հնարավորություն է տալիս դիմելու գտնված տարրի մյուս դաշտերին։ Քանի որ մեզ հետաքրքրում է միայն որոնման խնդիրը, և առայժմ չենք մտածում այն մյուս տվյալների մասին, որոնց համար որոնվում էր տարրը, կենթադրենք, որ Item տիպը պարունակում է միայն բանալին, այսինքն այն ինքը հենց բանալին է։

1.8.1 Գծային որոնում

Եթե որոնվող տվյալների մասին այլ լրացուցիչ տեղեկություններ տրված չեն, ապա ակնհայտ մոտեցումը զանգվածի տարրերի հաջորդական դիտարկումն է, քայլ առ քայլ մեծացնելուվ նրա այն հատվածի չափը, որտեղ որոնվող տարրը հայտնաբերված չէ։ Այս մոտեցումը կոչվում է գծային որոնում։ Որոնման ավարտի պայմանները երկուսն են․

  1. Տարրը գտնված է, այնսինքն՝ a[i] = x։
  2. Դիտարկված է ամբողջ զանգվածը և համընկնում չի հայտնաբերված։

Ստացվում է հետևյալ ալգորիթմը․

i := 0;
WHILE (i < N) & (a[i] # x) DO INC(i) END

ՈՒշադրություն դարձրեք, որ բուլյան արտահայտության մեջ ենթաարտահայտությունների կարգը կարևոր է։

Ցիկլի ինվարիանտը, այսինքն այն պայմանը, որը ճշմարիտ է ցիկլի ամեն մի իտերացիայի սկզբում և վերջում, այսպիսինն է․

(0 ≤ i < N) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Այն ցույց է տալիս, որ k֊ից փոքր բոլոր i֊երի համար համընկնումներ չեն եղել։ ՈՒշադրություն դարձնենք նաև, որ ցիկլի ամեն մի իտերացիայից առաջ և հետո i֊ի արժեքները տարբեր են։ Այնուամենայնիվ, ինվարիանտը պահպանվում է ցիկլի պայմանում։

Այս ասվածից և այն փաստից, որ որոնումն ավարտվում է միայն այն ժամանակ, երբ ցիկլի պայմանը տեղի չունի (կեղծ է), կարելի է դուրս բերել վերջնական պամանը․

((i = N) OR (a[i] = x)) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Այս պայմանը ոչ միայն մեր ցանկալի արդյունքն է, այլ դրանից նաև հետևում է, որ եթե ալգորիթմը գտել է համընկնում, ապա այն գտել է ամենքփոքր ինդեքսովը, այսինքն՝ առաջինը որոնվող տարրերից։ i = N հավասարությունը ցույց է տալիս, որ համընկնումներ չեն հայտնաբերվել։

Ցիկլի կրկնությունների ավարտը ակնհայտորեն երաշխավորված է, որովհետև ամեն մի քայլում i֊ի արժեքն աճում է, հետևաբար այն, իհարկե, վերջավոր քայլերից հետո կհասնի N֊ին։ Իրականում, եթե համընկնումներ չեն եղել, ապա դա տեղի կունենա N քայլից հետո։

Պարզ է, որ յուրաքանչյուր քայլում պահանջվում է մեծացնել ինդեքսը և հաշվել բուլյան արտահայտությունը։ Կարելի՞ է արդյոք այս խնդիրը պարզեցնել, և դրանով պարզեցնել նաև որոնման գործողությունը։ Միակ հնարավորությունը երկու կտորից բաղկացած բուլյան արտահայտությունը պարզեցնելու մեջ է։ Հետևաբար, միակ տարբերակը այնպիսի ավելի պարզ պայմանի ձևակերպումն է, որը համարժեք է մեր ունեցած բարդ պայմանին։ Դա հնարավոր է, եթե երաշխավորենք, որ համընկնում միշտ տեղի է ունենալու, որին կարելի է հասնել զանգվածի վերջում x արժեքով լրացուցիչ տարր ավելացնելով։ Այս լրացուցիչ տարրը կանվանենք պատնեշ (sentinel), որովհետև այն ինդեքսին արգելում է դուրս ելնել զանգված սահմաններից։ Այժմ a զանգվածը սահմանված է որպես․

a: ARRAY N+1 OF INTEGER

իսկ գծային որոնման ալգորիթմը, պատնեշի օգտագործմամբ, կունենա հետևյալ տեսքը․

a[N] := x; i := 0;
WHILE a[i] # x DO INC(i) END

Նույն ինվարիանտից դուրս բերված վերջնական պայմանը կլինի․

(a[i] = x) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Պարզ է, որ i = N պայմանը ցույց է տալիս համընկնումներ չեն եղել՝ բացառությամբ պատնեշի հետ համընկնելը։

1.8.2 Որոնում կիսման եղանակով (բինար որոնում)

Լրիվ ակնհայտ է, որ այլևս հնարավորություն չկա արագացնելու որոնման գործողությունև, եթե միայն որոնվող տարրերի մասին տրված չեն լրացուցիչ տեղեկություններ։ Հայտնի է, որ որոնումը կարելի է ավելի արդյունավետ դարձնել, եթե տվյալները կարգավորված են։ Պատկերացրեք, օրինակ, մի հեռախոսագիրք, որում անունները այբբենական կարգով դասավորված չեն։ Դա լրիվ անպետք բան է։ Մենք կներկայացնենք ալգորիթմ՝ հիմնված a զանգվածում տարրերի կարգավորված լինելու փաստի վրա, այսինքն՝ հաշվի առնելով հետևյալ պայմանը․

Ak: 1 ≤ k < N: a[k-1] ≤ a[k]

Հիմնական գաղափարն է՝ վերցնել մի պատահական տարր, օրինակ, a[m] և այն համեմատել x որոնման արգումենտի հետ։ Եթե այն հավասար է x֊ին, ապա որոնումն ավարտվում է, եթե այն փոքր է x֊ից, ապա m֊ից փոքր կամ հավասար ինդեքս ունեցող բոլոր տարրերը կարելի է բացառել հետագա որոնումից, և եթե այն մեծ է x֊ից, ապա կարելի է բացառել m֊ից մեծ և հավասար ինդեքս ունեցող տարրերը։ Ասվածից հանգում ենք կիսման եղանակով որոնման ալգորիթմին։ Այն օգտագործում է L և R ինդեքսային փոփոխականները, որոնք ցույց են տալիս զանգվածի այն հատվածի ձախ և աջ սահմանները, որոնցում դեռ կարող է հայտնաբերվել որոնվող տարրը։

L := 0; R := N - 1;
m := L֊ի և R֊ի միջև ընկած որևէ տարր;
WHILE (L <= R) & (a[m] # x) DO
  IF a[m] < x THEN
    L := m + 1
  ELSE
    R := m - 1
  END;
  m := L֊ի և R֊ի միջև ընկած որևէ տարր
END

ՈՒշադրություն դարձրեք այս ալգորիթմի և նախորդ բաժնում նկարագրված գծային որոնման ալգորիթմի հիմնական կառուցվածքային նմանությանը․ այստեղ i ինդեքսի դերկ կատարում է L, m, R եռյակը։ Այդ նմանությունը բացատրելու, և, այնուհետև, ցիկլի կոռեկտության մեջ ավելի լավ համոզվելու համար, մենք ձեռնպահ մնացինք փոքրիկ օպտիմիզացիայից, որը կբացառեր m֊ի երկու նույնական վերագրումները։

Ցիկլի ինվարիանտը, այսինքն՝ ամեմ մի քայլից առաջ ու հետո տեղի ունեցող պայմանը, հետևյալն է․

(Ak: 0 ≤ k < L: a[k] < x) & (Ak: R < k < N: a[k] > x)

որից դուրս է բերված հետևյալ արդյունքը․

((L > R) OR (a[m] = x)) & (Ak: 0 ≤ k < L: a[k] < x) & (Ak: R < k < N: a[k] > x)

որից էլ հետևում է․

((L > R) & (Ak: 0 ≤ k < N: a[k] ≠ x)) OR (a[m] = x)

m ինդեքսի ընտրությունը բոլորովին կամայական է այն իմաստով, որ ալգորիթմի կոռեկտությունը դրանից կախված չէ։ Բայց m֊ի ընտրությունն ազդում է ալգորիթմի արդյունավետության վրա։ Պարզ է, որ մեր նպատակն է ցիկլի ամեն մի քայլում հետագա որոնումից բացառել որքան հնարավոր է շատ տարրեր՝ անկախ համեմատման արդյունքից։ Լավագույն լուծումը կենտրոնական տարրի ընտրությունն է, որովհետև ամեն մի քայլում այն բացառում է զանգվածի տարրերի կեսը։ Արդյունքում քայլերի առավելագույն քանակը հավասար է log2 N, կլորացված վերև՝ մինչև ամենամոտիկ ամբողջ թիվը։ Այսպիսով, այս ալգորիթմը էականորեն շահեկան է գծային որոնման ալգորիթմից, որում համեմատությունների սպասվող քանակը N/2 է։

Արդյունավետությունը կարելի է մի քիչ լավացնել, տեղերով փոխելով ցիկլի մարմնի IF պայմանները։ Հավասարությունը պետք է ստուգել երկրորդ հերթին, որովհետև այն հանդիպում է միայն մեկ անգամ և բերում է ցիկլի ավարտին։ Բայց ավելի կարևոր է այն հարցը, թե արդյոք, ինչպես գծային որոնման դեպքում, հնարավո՞ր է գտնել ցիլի ավարտը որոշող ավելի պարզ պայման։ Իսկապես մենք գտնում ենք այդպիսի արագ ալգորիթմ, հենց որ հրաժարվում ենք որոնման ցիկլը տարրերի համընկնումով ավարտելու միամիտ ցանկությունից։ Առաջին հայացքից սա տարօրինակ է թվում, բայց ավելի ուշադիր ուսումնասիրությամբ բացահայտվում է, որ ամեն մի քայլում արդյունավետության շահն ավելին է, քան մի քանի լրացուցիչ տարրերի համեմատումից ստացված կորուստները։ Հիշենք, որ քայլերի առավելագույն քանակը log N է։

Արագ լուծումը հիմնված է հետևյալ ինվերիանտի վրա․

(Ak: 0 ≤ k < L: a[k] < x) & (Ak: R ≤ k < N: a[k] ≥ x)

և որոնումը շարունակովում է այնքան ժամանակ, քանի դեռ երկու հատվածները չեն ծածկել ամբողջ զանգվածը։

L := 0; R := 0;
WHILE L < R DO
  m := (L + R) DIV 2;
  IF a[m] < x THEN L := m + 1 ELSE R := m END
END

Ավարտի պայմանն է L ≥ R։ Բայց հասանելի՞ է արդյոք այն։ Այս պնդումն ապացուցելու համար պետք է ցույց տանք, որ բոլոր դեպքերում R - L տարբերությունը նվազում է ամեն մի քայլից հետո։ L < R տեղի ունի յուրաքանչյուր քայլ սկզբում։ m թվաբանական միջինի կամար ճշմարիտ է L ≤ m < R։ Հետևաբար, տարբերությունն իրոք նվազում է L֊ին m+1 վերգրելով (Լ-ը մեծացնելով), կամ R֊ին m վերագրելով (R֊ը նվազեցնելով), և ցիկլի կրկնությունն ավարտվում է L = R պայմանով։

Այնուամենայնիվ, մեր ինվարիանտը և L = R պայմանը դեռևս համընկնում չեն նշանակում։ Իհարկե, եթե R = N, ապա համընկնում չկա։ Այլապես պետք է հաշվի առնենք, որ a[R] տարրը երբեք չի համեմատվել։ Հետևաբար, մի լրացուցիչ a[R] = x հավասարության ստուգումն անհրաժեշտ է։ Ի տարբերություն առաջին լուծման, այս ալգորիթմը, ինչպես և գծային որոնումը, գտնում է ամենափոքր ինդեքսով համընկնող տարրը։

1.8.3 Որոնում աղյուսակում

Զանգվածում որոնումը երբեմն անվանում են նաև որոնում աղյուսակում, հատկապես եթե բանալիները բաղադրյալ օբյեկտներ են, ինչպես օրինակ թվերի կամ նիշերի զանգվածը։ Վերջինս հոնդիպում է ավելի հաճախ․ նիշերի զնգվածներն անվանում են տողեր կամ բառեր։ Սահմանենք String տիպը հետևյալ կերպ․

String = ARRAY M OF CHAR

իսկ x և y տողերի միջև կարգը սահանենք հետևյալ կերպ․

(x = y) ≡ (Aj: 0 ≤ j < M : x[j] = y[j])

(x < y) ≡ Ei: 0 ≤ i < N : ((Aj: 0 ≤ j < i : x[j] = y[j]) & (x[i] < y[i]))

Ակնհայտ է, որ համընկնումը հաստատելու համար, պետք է համոզվենք, որ համեմատվող տողերի բոլոր նիշերը համընկնում են։ Բաղադրյալ օպերանդների այսպիսի համեմատումը բերվում է օպերանդներում չհամընկնող մասերի հայտնաբերմանը, այսինքն՝ անհավասարության որոնման։ Եթե գոյություն չունի չհամընկնող մասեր, ապա հավասարությունը հաստատված է։ Ենթադրենք բառերի երկարությունը բավականաչափ փոքր է, ասենք 30֊ից փոքր, այդ դեպքում կօգտագործենք գծային որոնումը։

Շատ գործնական կիրառություններում ցանկալի է ընդունել, որ տողն ունի փոփոխական երկարություն։ Սա ենթադրում է, որ յուրաքանչյուր տողի հետ պահվում է նաև իր երկարությունը։ Օգտագործելով վերը սահմանված String տիպը, այդ երկարությունը չպետք է գերազանցի M առավելագույն արժեքը։ Այս սխեման բավականաչափ ճկուն է և ընդունելի է շատ դեպքերում, ինչպես նաև ազատում է դինամիկ հիշողության հետ աշխատելու դժվարություններից։ Լայնորեն օգտագործվում են տողի երկարությունը ներկայացնելու երկու ներկայացումներ․

  1. Երկարությունը բացահայտ նշվում է տողի վերջում մի հատուկ նիշ կցելով, որը այլ տեղերում չի հանդիպում։ Սովորաբար դա 0X չարտածվող արժեքն է։ (Հետագա կիրառություններում կարևոր է, որ այդ հատուկ նիշը նիշերի բազմության ամենափոքր տարրն է։)
  2. Երկարությունը բացահայտ նշվում է զանգվածի առաջին տարրում, այսինքն տողն ունի հետևյալ տեսքը․
s = s[0], s[1], s[2], ..., s[N-1]

որտեղ s[1]...s[N-1] տողի նիշերն ենմ և s[0] = CHR(N)։ Այս եղանակի առավելությունն այն է, որ երկարությունն ուղղակի մատչելի է, իսկ թերությունն այն է, որ տողի երկարությունը սահմանափակված է նիշերի բազմության հզորությամբ, այն է՝ 256 նիշ՝ ASCII կոդավորման դեպքում։

Ստորև բերված որոնման ալգորիթմում նախապատվությունը կտանք առաջին սխեմային։ Այդ դեպքում տողերի համեմատումն ընդունում է հետևյալ տեսքը․

i := 0;
WHILE (x[i] # 0X) & (x[i] = y[i]) DO i := i + 1 END

Այստեղ եզրափակող նիշը կատարում է պատնեշի դերը։ Ցիկլի ինվարիանտն է․

Aj: 0 ≤ j < i : x[j] = y[j] ≠ 0X

Իսկ վերջնական պայմանն ունի հետևյալ տեսքը․

((x[i] = 0X) OR (x[i] ≠ y[i])) & (Aj: 0 ≤ j < i : x[j] = y[j] ≠ 0X)

Այս պայմանը հաստատում է x և y տողերի հավասարությունը, երբ x[i] = y[i], և հաստատում է x < y պայմանը, եթե x[i] < y[i]։

Հիմա արդեն պատրաստ ենք վերադառնալու աղյուսակում որոնման խնդրին։ Այն պահանջվում է ներդրված որոնումներ, ավելի ճիշտ՝ որոնում աղյուսակի տարրերով, իսկ ամեն մի տարրի համար՝ կոմպոնենտների համեմատումների հաջորդականություն։ Օրինակ, թող որ T աղյուսակը և x որոնման արգումենտը սահմանված են այսպես․

T: ARRAY N OF String;
x: String

Ենթադրելով որ N֊ը բավականաչափ մեծ է և աղյուսակի տարրերը կարգավորված են այբբենական կարգով, կօգտագործենք որոնման կիսման մեթոդը։ Օգտագործելով բինար որոնման և տողերի համեմատման վերը մշակված ալգորիթմները, ստանում ենք ծրագրի հետևյալ հատվածը։

i := -1;
L := 0; R := N;
WHILE L < R DO
  m := (L + R) DIV 2;
  i := 0;
  WHILE (x[i] # 0X) & (T[m,i] = x[i]) DO i := i + 1 END;
  IF T[m,i] < x[i] THEN L := m + 1 ELSE R := m END
END;
IF R < N THEN
  i := 0;
  WHILE (x[i] # 0X) & (T[R,i] = x[i]) DO i := i + 1 END
END
(* (R < N) & (T[R,i] = x[i]) պայմանը որոշում է համընկնումը *)