C3-superluokan linearisointi on algoritmi , jota käytetään ensisijaisesti moniperinnön hierarkian vakaan linearisoinnin saamiseksi olio -ohjelmoinnissa . Tätä linearisointia käytetään määrittämään järjestys, jossa menetelmät tulisi periä, johon viitataan usein englanninkielisessä kirjallisuudessa "MRO" (lyhenne sanoista "Method Resolution Order", eli "method resolution order"). Otsikon C3 osoittaa lopullisen linearisoinnin kolme pääpiirrettä: vakaa ja laajeneva (vanhuuden mukaan) graafi , paikallisen tärkeysjärjestyksen säilyminen ja monotonisuus. Tämä teoria esiteltiin ensimmäisen kerran vuonna 1996 OOPSLA- konferenssissa asiakirjassa "Monotone Superclass Linearization for the Dylan Language" [1] . Myöhemmin tämä algoritmi valittiin oletusalgoritmiksi menetelmän resoluutiolle ohjelmointikielessä Python 2.3 (ja uudemmissa), Perl 6 :ssa ja Parrot - virtuaalikoneessa . Se on saatavana myös vaihtoehtona (ei oletuksena MRO) Perl 5 -ytimessä versiosta 5.10.0 lähtien. Perl 5:n aiempien versioiden laajennettu toteutus on nimeltään Class::C3 , ja se on olemassa osoitteessa CPAN .
varten
luokkaO luokka A laajentaa O:ta luokka B laajentaa O:ta luokka C laajentaa O:ta luokka D laajentaa O:ta luokka E laajentaa O:ta luokka K1 ulottuu A, B, C luokka K2 ulottuu D, B, E luokka K3 ulottuu D, A luokka Z ulottuu K1, K2, K3Z:n linearisointia pidetään
L(O) := [O] // O:n linearisointi on triviaali, se on yksialkioinen lista [O] koska O:lla ei ole vanhempia L(A) := [A] + yhdistä(L(O), [O]) // A:n linearisointi on A plus A:n vanhempien ja A:n vanhempien linearisaatioiden liitto = [A] + yhdistä ([O], [O]) = [A,O] L(B) := [B, O] // B:n, C:n, D:n ja E:n linearisointi L(C) := [C,O] L(D) := [D, O] L(E) := [E, O] L(K1) := [K1] + yhdistä(L(A), L(B), L(C), [A, B, C]) // etsi ensin K1:n vanhempien linearisoinnit: L(A ), L(B) ja L(C); ja liitä heidät vanhempien luetteloon [A, B, C] = [K1] + yhdistä([A, O], [B, O], [C, O], [A, B, C]) // luokka A sopii ensimmäiseen yhdistämisvaiheeseen, koska se näkyy vain kaikkien luetteloiden alussa = [K1, A] + yhdistä([O], [B, O], [C, O], [B, C]) // luokka O ei sovi, koska se on listojen 2 ja 3 päissä, mutta... = [K1, A, B] + yhdistä ([O], [O], [C, O], [C]) = [K1, A, B, C] + yhdistä([O], [O], [O]) // luokka O on kuitenkin ainoa ja viimeinen ehdokas = [K1, A, B, C, O] L(K2) := [K2] + yhdistä(L(D), L(B), L(E), [D, B, E]) = [K2] + yhdistä ([D, O], [B, O], [E, O], [D, B, E]) // valitse D = [K2, D] + yhdistä ([O], [B, O], [E, O], [B, E]) // O ei sovi, valitse B = [K2, D, B] + yhdistä([O], [O], [E, O], [E]) // O ei sovi, valitse E = [K2, D, B, E] + yhdistä ([O], [O], [O]) // valitse O = [K2, D, B, E, O] L(K3) := [K3] + yhdistä(L(D), L(A), [D, A]) = [K3] + yhdistä ([D, O], [A, O], [D, A]) = [K3, D] + yhdistä ([O], [A, O], [A]) = [K3, D, A] + yhdistä ([O], [O]) = [K3, D, A, O] L(Z) := [Z] + yhdistä(L(K1), L(K2), L(K3), [K1, K2, K3]) = [Z] + yhdistä([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3]) / / valitse K1 = [Z, K1] + yhdistä ([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3]) // A ei sovellu, valitse K2 = [Z, K1, K2] + yhdistä ([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3]) // A ei t sovi, D ei sovi, valitse K3 = [Z, K1, K2, K3] + yhdistä([A, B, C, O], [D, B, E, O], [D, A, O]) // A ei sovi, valitse D = [Z, K1, K2, K3, D] + yhdistä ([A, B, C, O], [B, E, O], [A, O]) // valitse A = [Z, K1, K2, K3, D, A] + yhdistä ([B, C, O], [B, E, O], [O]) // valitse B = [Z, K1, K2, K3, D, A, B] + yhdistä ([C, O], [E, O], [O]) // valitse C = [Z, K1, K2, K3, D, A, B, C] + yhdistä([O], [E, O], [O]) // O ei sovi, valitse E = [Z, K1, K2, K3, D, A, B, C, E] + yhdistä([O], [O], [O]) // valitse O = [Z, K1, K2, K3, D, A, B, C, E, O] // vastausNimitykset:
L(Class) - luokan luokan linearisointi [A,B,C] - kolmen elementin luettelo, joissa pää on A ja häntä on [B,C] yhdistä - yhdistä luettelotYhdistämistoiminto yhdistää listat siten, että kukin elementti esiintyy tuloksessa täsmälleen kerran, jolloin se on samanlainen kuin joukkojen yhdistäminen, mutta listan elementtien järjestys on tässä tärkeä. Yhdistämistoiminto toimii seuraavasti - se toistuu argumenttiluetteloissa esiintymisjärjestyksessä (vasemmalta oikealle) valitsemalla ensimmäisen elementin, joka voi olla ensimmäinen useissa listoissa, mutta jota ei mainita missään toisessa ja sen jälkeen, ja siirtää sen tulosluetteloon jättäen pois listoista -argumentit, toistaen tämän toimenpiteen useita kertoja, kunnes kaikki elementit on siirretty argumenttilistoista tulosluetteloon. Jos jossain vaiheessa syntyy tilanne, että on mahdotonta valita ehdokaselementtiä, joka täyttää määritellyn ehdon, ts. jos kaikissa argumenttiluetteloissa ensimmäiset elementit eivät ole ensimmäisinä muissa argumenttiluetteloissa, tuloksena olevaa listaa ei luoda.