В. Савченко - Анализ алиасов, страница 5

Äëÿ âñåõ ïðàêòè÷åñêè âñòðå÷àþùèõñÿ ÷èñåë çíà÷åíèå ýòîé ôóíêöèè ìåíüøå 5, ÷òî ïîçâîëÿåò óòâåðæäàòü, ÷òî ïîëó÷åííàÿ ñëîæíîñòü ïî÷òè ëèíåéíà265.2.4Ðàçíèöà ñ ÀíäåðñåíîìÐåçóëüòàòû ïîäõîäà Ñòèíñãàðäà óñòóïàþò ïî òî÷íîñòè ðåçóëüòàòàì àëãîðèòìà Àíäåðñåíà. Äëÿ ïîíèìàíèÿ ïðè÷èí ýòîãî ôàêòà ïðîùå ðàññìîòðåòü ïðèìåð.Ðàññìîòðèì àíàëèçû óêàçàòåëåé, ïîñòðîåííûå ïî Àíäåðñåíó è ïî Ñòèíñãàðäó, äëÿ ñëåäóþùåãî êîäà:Ïðèìåð 17.p = &a;q = &a;p = &b;paqpbÐèñ. 1: Àíäåðñåía,bqÐèñ. 2: Ñòèíñãàðä äàííîì ïðèìåðå â àíàëèçå Ñòèíñãàðäà îøèáî÷íî ðåøàåòñÿ, ÷òî q ìîæåò óêàçûâàòü íà b.Ãîâîðÿ î ðàçíèöå â òî÷íîñòè ìåæäó äâóìÿ ýòèìè ïîäõîäàìè, ñòîèòñêàçàòü î òîì, ÷òî Ãîðâèö è Øàïèðî ïðîòåñòèðîâàëè 61 ïðîãðàììó íàC ñ ðàçìåðàìè îò 300 äî 24 300 ñòðîê êîäà. Áûëè ïîëó÷åíû ñëåäóþùèåðåçóëüòàòû:• Ñòèíñãàðä ìåíåå òî÷åí - â ñðåäíåì ðàçìåð ìíîæåñòâ â 4 ðàçà áîëüøå; â õóäøåì ñëó÷àå â 15 ðàç.• Àíäåðñåí ìåäëåííåå - â ñðåäíåì â ïîëòîðà ðàçà ìåäëåííåå; â õóäøåì ñëó÷àå â 31 ðàç.5.3Ïîäõîä Ãîðâèö-Øàïèðî (97`)Ðàçðàáîòàí Ñþçàí Ãîðâèö è Ìàðêîì Øàïèðî è ïðåäñòàâëåí â ñîîòâåòñòâóþùåé ðàáîòå â 1997-îì ãîäó.Ïîäõîä ïðåäñòàâëÿåò ñîáîé ñïîñîá ïîëó÷èòü ïðîìåæóòî÷íûå çâåíüÿìåæäó ïîäõîäàìè Àíäåðñåíà è Ñòèíñãàðäà.5.3.1Îñíîâíàÿ èäåÿÎïðåäåëåíèå 20.

Ñòåïåíüþóêàçàòåëÿ p ∈ P áóäåì íàçûâàòü |Vp |.27Çàìåòèì, ÷òî ñòåïåíü êàæäîãî óêàçàòåëÿ â ñëó÷àå Ñòèíñãàðäà îãðàíè÷åíà 1, à â ñëó÷àå Àíäåðñåíà n, ãäå n - ÷èñëî ïåðåìåííûõ â ïðîãðàììå.Òîãäà ñòîèò ðàññìîòðåòü ñëó÷àè, êîãäà ñòåïåíü óêàçàòåëåé îãðàíè÷åíà íåêîòîðûì k : 1 ≤ k ≤ n.  äàííîì ñëó÷àå ∀p ∈ P âñå ïåðåìåííûå v ∈ Vp îïðåäåëÿþòñÿ â êàòåãîðèè, ãäå êàòåãîðèÿ - ýòî íåêîòîðîå ÷èñëî èç [1, k]. Òîãäà ïàðà ïåðåìåííûõ v, w ∈ V ñ÷èòàåòñÿ ýêâèâàëåíòíîé, åñëè ∃p ∈ P òàêîé, ÷òî äëÿ p êàòåãîðèè v è w ñîâïàäàþò.Åñëè ãîâîðèòü ôîðìàëüíî, òî ∀p ∈ P îïðåäåëÿåòñÿ îòîáðàæåíèåηp : Vp → [1, k].v, w ∈ V áóäåì íàçûâàòü ýêâèâàëåíòíûìè ïî ÃîðâèöHSØàïèðî è îáîçíà÷àòü v ∼ w , åñëè è òîëüêî åñëè ∃p ∈ P : v, w ∈ Vp èηp (v) = ηp (w).Îïðåäåëåíèå 21.Ïðèìåð 18.p1p1p1p2====Ðàññìîòðèì ñëåäóþùèé ïðèìåð:&a;&b;&c;&c;Ðàññìîòðèì ñëó÷àé k = 2.Ïóñòü ηp1 (a) = ηp1 (b) = 1, à ηp1 (c) = 2.

Òîãäàp1a,bp2cÐèñ. 3: Ãîðâèö-Øàïèðî. Óäà÷íûé âûáîð êàòåãîðèé äàííîì ñëó÷àå òî÷íîñòü àíàëèçà ñîîòâåòñòâóåò àëãîðèòìó Àíäåðñåíà.Îäíàêî, åñëè æå ηp1 (a) = 1, à ηp1 (b) = ηp1 (c) = 2, òîp1ap2b,cÐèñ. 4: Ãîðâèö-Øàïèðî. Íåóäà÷íûé âûáîð êàòåãîðèé äàííîì ñëó÷àå ìû ïîòåðÿëè â òî÷íîñòè, ò.ê.

ðåçóëüòàò ãîâîðèò, ÷òîb ∈ Vp2 . Íî ñòîèò òàêæå îòìåòèòü, ÷òî ðåçóëüòàò òî÷íåå Ñòèíñãàðäà, ò.ê.â åãî ñëó÷àå îøèáî÷íî ðåøàåòñÿ, ÷òî a, b ∈ Vp2 .Èç ðàññìîòðåííîãî ïðèìåðà âèäíî, ÷òî òî÷íîñòü àíàëèçà ñèëüíî çàâèñèò îò ðàçáèåíèÿ íà êàòåãîðèè, ò.å. îò âûáîðà îòîáðàæåíèé ηp .285.3.2ÊîíêðåòèçàöèÿÑ òî÷êè çðåíèÿ ðåàëèçàöèè, ôîðìèðîâàíèå |P| îòîáðàæåíèé íå ÿâëÿåòñÿïðàêòè÷íûì.  ñâÿçè ñ ýòèì âûáèðàåòñÿ îäíî îòîáðàæåíèå η : V → [1, k].Òîãäà ∀p ∈ P, ∀v ∈ Vp → ηp (v) = η(v).Àñèìïòîòè÷åñêàÿ ñëîæíîñòü ïîëó÷åííîãî àëãîðèòìà â äàííîì ñëó÷àå áóäåò ðàâíà O(k 2 n).Ðåçóëüòèðóþùèé àíàëèç óêàçàòåëåé ξ íåïîñðåäñòâåííî çàâèñèò îòâûáîðà η (äàëåå áóäåì îáîçíà÷àòü ξη ). Ïðè ýòîì íåçàâèñèìî îò âûáîðà η ξη îñòàåòñÿ êîíñåðâàòèâíûì, ÷òî ïîçâîëÿåò äëÿ íåñêîëüêèõ âûáîðîâ îòîáðàæåíèÿ η1 , .

. . , ηm ïðîèçâåñòè êîìïîçèöèþ àíàëèçîâ óêàçàòåëåéζ = ξη1 ◦ · · · ◦ ξηm . Ïî òåîðåìå î êîìïîçèöèè êîíñåðâàòèâíûõ àíàëèçîâóêàçàòåëåé èìååì, ÷òî ζ êîíñåðâàòèâåí è ∀i ∈ [1, m] → ξηi ≤ ζ .Òàê êàê ìû çàïóñêàåì ñõîæèå àëãîðèòìû m ðàç, òî è ðåçóëüòèðóþùàÿ ñëîæíîñòü ðàâíà O(mk 2 n).Îäíàêî, äî ñèõ ïîð îñòàëñÿ íåðåøåííûì âîïðîñ î òîì, ÷òî äåëàòü ñîòîáðàæåíèÿìè η1 , .

. . , ηm è êàêîìó ñâîéñòâó íåîáõîäèìî èõ ñòðîèòü.Ãîðâèö è Øàïèðî ïðåäëîæèëè ñëåäóþùåå ýâðèñòè÷åñêîå ïðàâèëî:∀v, w ∈ V : v 6= w → ∃i ∈ [1, m] : ηi (v) 6= ηi (w). Èëè, ÷òî òî æå ñàìîå, äëÿëþáîé ïàðû ïåðåìåííûõ âåðíî, ÷òî ñóùåñòâóåò îòîáðàæåíèå ηi , êîòîðîåîïðåäåëÿåò v è w â ðàçíûå êàòåãîðèè.Ðàññìîòðèì ñëåäóþùóþ ïðîöåäóðó. Ïåðåíóìåðóåì êàæäóþ ïåðåìåííóþ ïî îñíîâàíèþ k .

Òîãäà êàæäîé ïåðåìåííîé áóäåò ñîïîñòàâëåíî mçíà÷íîå ÷èñëî. Èìåííî m áóäåò êîëè÷åñòâîì çàïóñêîâ, à i-ûé ðàçðÿäáóäåò êàòåãîðèåé äàííîé ïåðåìåííîé â i-îì çàïóñêå.Ïðèìåð 19. Ïóñòü èìååòñÿ 4 ïåðåìåííûå a, b, c è d è k = 2. Ïðîíóìåðóåì ïåðåìåííûå:a00 , b01 , c10 , d11Òîãäà ÷èñëî çàïóñêîâ m = blog2 (4 − 1)c + 1 = 1 + 1 = 2. Ïðè ïåðâîìçàïóñêå ïåðåìåííûå a è c ïîïàäóò â îäíó êàòåãîðèþ, à b, d â äðóãóþ.Ïðè âòîðîì æå â ïåðâóþ êàòåãîðèþ ïîïàäóò a è b, à c è d âî âòîðóþ.Óòâåðæäåíèå 6. Ïîäîáíîå ðàñïðåäåëåíèå îòîáðàæåíèéη1 , . .

. , ηm ñî-îòâåòñòâóåò ïðàâèëó, ñôîðìóëèðîâàííîìó âûøå.Ïóñòü ïðàâèëî íå âûïîëÿíåòñÿ, òîãäà ∃v, w ∈ V : v 6=w, ∀i ∈ [1, m] : ηi (v) = ηi (w). Îäíàêî, ýòî îçíà÷àåò, ÷òî â ÷èñëàõ, ñîîòâåòñòâóþùèõ v è w âñå ðàçðÿäû ðàâíû, ÷åãî íå ìîæåò áûòü ïðè v 6= w.Ïîëó÷èëè ïðîòèâîðå÷èå.Äîêàçàòåëüñòâî.Ïðè òàêîì ïîäõîäå èìååì m = blogk (n − 1)c + 1 è, ñîîòâåòñòâåííî,âðåìÿ âûïîëíåíèÿ O(logk (n)k 2 n).295.3.3Ïîñòðîåíèå àíàëèçàÑîáñòâåííî àëãîðèòì îòëè÷àåòñÿ îò Ñòèíñãàðäà òåì, ÷òî ðàáîòàåò blogk (n−1)c + 1 ðàç è óñòàíàâëèâàåò íåìíîãî îòëè÷àþùååñÿ îòíîøåíèå ýêâèâàëåíòíîñòè.Àëãîðèòì 3: (Ãîðâèö-Øàïèðî)enumerate V ;m ← blogk (n − 1)c + 1;for j ∈ [1, m] dowhile changed dochanged ← f alse;foreach i ∈ I doif not Λ(i)(ξj ) thensolve and merge categories Λ(i)(ξj );changed ← true;endendendendζ ← ξ1 ◦ · · · ◦ ξm ;5.3.4ÐåçóëüòàòûÍà 25 òåñòàõ, ïðè èñïîëüçîâàíèè 3 êàòåãîðèé, ðåçóëüòèðóþùèå ìíîæåñòâà, ïîëó÷åííûå ìåòîäîì Ãîðâèö-Øàïèðî, â ñðåäíåì â 2.67 ðàç áîëüøå,÷åì ìíîæåñòâà Àíäåðñåíà (äëÿ Ñòèíñãàðäà ýòîò ìíîæèòåëü ðàâåí 4.75).Ïîäõîä Ãîðâèö-Øàïèðî ìåäëåííåå Ñòèíñãàðäà, íî îò 7 äî 25 ðàç áûñòðååÀíäåðñåíà.6Ñîâðåìåííûå ïîäõîäûÑ ðîñòîì, êàê ïðîèçâîäèòåëüíîñòè êîìïüþòåðîâ, òàê è îáúåìîâ ïàìÿòè, ñíîâà ïðîÿâèëàñü òåíäåíöèÿ ê ïîëó÷åíèþ áîëåå òî÷íûõ àíàëèçîâ.

Âêà÷åñòâå îñíîâû áûë âûáðàí ïðèíöèï Àíäåðñåíà, îäíàêî, ñïîñîáû ðàçðåøåíèÿ îãðàíè÷åíèé çíà÷èòåëüíî îòëè÷àþòñÿ.Ïåðåä ðàññìîòðåíèåì íåïîñðåäñòâåííî ìåòîäîâ íåîáõîäèìî ïðåäñòàâèòü ñòðóêòóðó äàííûõ, êîòîðàÿ èñïîëüçóåòñÿ â êàæäîì èç ñëåäóþùèõàëãîðèòìîâ.6.1Ãðàô îãðàíè÷åíèéÏðåæäå âñåãî ñòîèò îòìåòèòü, ÷òî ÷èñëî îñíîâíûõ èíñòðóêöèé áûëî ñîêðàùåíî ñ 6 äî 4 (ïî ñðàâíåíèþ ñ Àíäåðñåíîì).306.1.1Îãðàíè÷åíèÿ• p = &a;• p = &a;• p = q;• p = *r;• *p = &a;⇒• p = q;• p = *r;• *p = q;• *p = q;• *p = *r;Ýòî ñäåëàíî, ïîòîìó ÷òî èíñòðóêöèè *p = &a; è *p = *r; ñâîäÿòñÿ êîñòàëüíûì ïðîñòûìè ïðåîáðàçîâàíèÿìè, òî åñòü *p = &a; ≡ t = &a; *p = t;è *p = *r; ≡ t = *r; *p = t;.Îãðàíè÷åíèÿ, ñâÿçàííûå ñ îñíîâíûìè èíñòðóêöèÿìè, ïîëó÷èëè íåñêîëüêî èíûå îáîçíà÷åíèÿ è ñïåöèàëüíûå íàçâàíèÿ:Èíñòðóêöèÿp = &ap=qp = ∗q∗p = qÎãðàíè÷åíèåp ⊇ {a}p⊇qp ⊇ ∗q∗p ⊇ qÍàçâàíèå îãðàíè÷åíèÿÁàçîâîå îãðàíè÷åíèåÏðîñòîå îãðàíè÷åíèåÑëîæíîå îãðàíè÷åíèå IÑëîæíîå îãðàíè÷åíèå IIÑìûñë îãðàíè÷åíèÿb ∈ VpVp ⊇ Vq∀t ∈ Vq → Vp ⊇ Vt∀t ∈ Vp → Vt ⊇ VqÒåïåðü ìîæåì ïåðåõîäèòü íåïîñðåäñòâåííî ê ãðàôó îãðàíè÷åíèé.6.1.2ÎïðåäåëåíèåÎïðåäåëåíèå 22.

Ãðàôîì îãðàíè÷åíèéG áóäåì íàçûâàòü ñëåäóþùóþïÿòåðêó < V, E, ξ, C1 , C2 >, ãäåV = P - ìíîæåñòâî âåðøèí ãðàôà îãðàíè÷åíèéE - ìíîæåñòâî îðèåíòèðîâàííûõ ðåáåð ãðàôà, òàêîå ÷òî ∀a, b ∈ P →((a, b) ∈ E ⇔ Vb ⊇ Va ). Èçíà÷àëüíîE = E0 = {(a, b) : a, b ∈ P è èìååòñÿ îãðàíè÷åíèå b ⊇ a}ξ - àíàëèç óêàçàòåëåé, êîòîðûé ñîïîñòàâëÿåò êàæäîé âåðøèíå p ìíîæåñòâî Vp , èçíà÷àëüíîξ : ∀p ∈ P → ξ(p) = {v : v ∈ V è èìååòñÿ îãðàíè÷åíèå p ⊇ {v}}C1 - îòîáðàæåíèå P → 2P , òàêîå ÷òî∀p ∈ P C1 (p) = {q : q ∈ P è èìååòñÿ îãðàíè÷åíèå q ⊇ ∗p}Òî åñòü êàæäîé âåðøèíå ãðàôà p îòîáðàæåíèå C1 ñîïîñòàâëÿåò ìíîæåñòâî âåðøèí, êîòîðûå âõîäÿò â ñëîæíûå îãðàíè÷åíèÿ I âìåñòå ñ ∗p31C2 - îòîáðàæåíèå P → 2P , òàêîå ÷òî∀p ∈ P C2 (p) = {q : q ∈ P è èìååòñÿ îãðàíè÷åíèå ∗ p ⊇ q}Òî åñòü C2 èäåíòè÷íî C1 c òîé ëèøü ðàçíèöåé, ÷òî ðàññìàòðèâàþòñÿñëîæíûå îãðàíè÷åíèÿ II.6.1.3Ðàçðåøåíèå îãðàíè÷åíèé íà ãðàôåÒåïåðü ñëåäóåò ðàññìîòðåòü äàííûé ãðàô ñ òî÷êè çðåíèÿ ðåøåíèÿ ïîñòðîåíèÿ àíàëèçà.Ðàññìîòðèì íåñêîëüêî ñèòóàöèé, êîòîðûå ïîçâîëÿò ïîíÿòü êàê óñòðîåíî ïîñòðîåíèå àíàëèçà.• Ïóñòü a, b ∈ P , (a, b) ∈ E è ξ(a) = {c}.

Òàê êàê (a, b) ∈ E , òîξ(b) ⊇ ξ(a), òî åñòü ξ(b) ⊇ {c} è, åñëè c íå áûëî â ξ(b), òî åãîíåîáõîäèìî äîáàâèòü. Ïîäîáíàÿ îïåðàöèÿ íàçûâàåòñÿ ðàñïðîñòðàíåíèåì çíà÷åíèé ïî ðåáðàì ãðàôà îãðàíè÷åíèé.Åñëè èçîáðàçèòü ïîäîáíóþ ñèòóàöèþ ñîáñòâåííî â âèäå ãðàôà, òîïîëó÷èì ñëåäóþùåå:{c}{c}a{c}abÐèñ.

5: ÄîbÐèñ. 6: Ïîñëå• Ïóñòü a, b ∈ P , ξ(a) = {c} è C1 (a) = {b}. Èç òîãî êàê ñôîðìóëèðîâàíî C1 ñëåäóåò, ÷òî ∀t ∈ Va → Vb ⊇ Vt , îòêóäà ñëåäóåò, ÷òî Vb ⊇ Vc ,è ñëåäóåò äîáàâèòü ðåáðî (c, b).Åñëè èçîáðàçèòü ïîäîáíóþ ñèòóàöèþ ñîáñòâåííî â âèäå ãðàôà, òîïîëó÷èì ñëåäóþùåå:c{c}cba{c}baÐèñ. 7: ÄîÐèñ. 8: Ïîñëå• Ïóñòü a, b ∈ P , ξ(a) = {c} è C2 (a) = {b}. Èç òîãî êàê ñôîðìóëèðîâàíî C2 ñëåäóåò, ÷òî ∀t ∈ Va → Vt ⊇ Vb , îòêóäà ñëåäóåò, ÷òî Vc ⊇ Vb ,è ñëåäóåò äîáàâèòü ðåáðî (b, c).Åñëè èçîáðàçèòü ïîäîáíóþ ñèòóàöèþ ñîáñòâåííî â âèäå ãðàôà, òîïîëó÷èì ñëåäóþùåå:32c{c}cba{c}baÐèñ. 9: ÄîÐèñ.

10: ÏîñëåÍà îñíîâàíèè âñåãî ëèøü ýòèõ òðåõ ïðàâèë çàïèøåì èòåðàòèâíûéàëãîðèòì ðåøåíèÿ, êîòîðûé òàêæå íàçûâàþò àëãîðèòìîì äèíàìè÷åñêîãîòðàíçèòèâíîãî çàìûêàíèÿ.Àëãîðèòì 4:(Äèíàìè÷åñêîå òðàíçèòèâíîå çàìûêàíèå)W ←V;while W 6= ∅ don ← get from W ;remove n from W ;foreach v ∈ ξ(n) doforeach a ∈ C1 (n) doif (v, a) 6∈ E thenE ← E ∪ {(v, a)};W ← W ∪ {v};endendb ∈ C2 (n) do(b, v) 6∈ E thenE ← E ∪ {(b, v)};W ← W ∪ {b};foreachifendendend(n, z) ∈ E doξ(z) ← ξ(z) ∪ ξ(n);if ξ(z) changed thenW ← W ∪ {z};foreachendendend6.1.4Ïðèìåð ðàáîòû àëãîðèòìàÏðèìåð 20.Ðàññìîòðèì ðàáîòó àëãîðèòìà íà ñëåäóþùåì êîäå:B = &A;A = &C;D = A;*D = B;33A = *D;Äëÿ äàííîãî ïðèìåðà P = {A, B, C, D}, E = E0 = (A, D), ξ(B) ={A}, ξ(A) = {C}, C1 (D) = {A} è C2 (D) = {B}.Èçîáðàçèì äàííûé ãðàô:{C}{A}ABDCÍà÷íåì àëãîðèòì1.