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%) աղյուսակ։

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

No comments:

Post a Comment