C3 superklasslinjärisering är en algoritm som främst används för att få en stabil linjärisering av en multipel arvshierarki i objektorienterad programmering . Denna linjärisering används för att bestämma i vilken ordning metoder ska ärvas, vilket ofta i engelsk litteratur kallas "MRO" (förkortning av "Method Resolution Order", det vill säga "method resolution order"). C3 i titeln indikerar tre huvuddrag i den slutliga lineariseringen: stabil och expanderande (efter tjänsteår) graf , bevarande av lokal prioritetsordning och monotoni. Denna teori presenterades första gången 1996 vid OOPSLA- konferensen , i en artikel med titeln "Monotone Superclass Linearization for the Dylan Language" [1] . Därefter valdes denna algoritm som standardalgoritm för metodupplösning i programmeringsspråket Python 2.3 (och senare), Perl 6 och den virtuella maskinen Parrot . Den är också tillgänglig som ett alternativ (inte standard MRO) i Perl 5 -kärnan sedan version 5.10.0. En utökad implementering för tidigare versioner av Perl 5 kallas Class::C3 och finns på CPAN .
För
klass O klass A sträcker sig O klass B förlänger O klass C sträcker sig O klass D sträcker sig O klass E sträcker sig O klass K1 sträcker sig A, B, C klass K2 sträcker sig D, B, E klass K3 sträcker sig D, A klass Z förlänger K1, K2, K3Linjäriseringen av Z anses vara
L(O) := [O] // linjärisering av O är trivial, det är en enelementslista [O] eftersom O inte har några föräldrar L(A) := [A] + sammanfoga(L(O), [O]) // linjärisering av A är A plus föreningen av linjäriseringarna av A:s föräldrar och A:s föräldrar = [A] + sammanfoga([O], [O]) = [A,O] L(B) := [B, O] // linjärisering av B, C, D och E L(C) := [C,O] L(D) := [D, O] L(E) := [E, O] L(K1) := [K1] + sammanfoga(L(A), L(B), L(C), [A, B, C]) // hitta först linjäriseringarna av föräldrarna till K1: L(A L(B) och L(C); och gå med i listan över föräldrar [A, B, C] = [K1] + sammanfoga([A, O], [B, O], [C, O], [A, B, C]) // klass A är lämplig för det första sammanfogningssteget eftersom den endast visas vid börjar alla listor = [K1, A] + sammanfoga([O], [B, O], [C, O], [B, C]) // klass O är inte lämplig eftersom den finns i ändarna på listorna 2 och 3, men... = [K1, A, B] + sammanfoga([O], [O], [C, O], [C]) = [K1, A, B, C] + sammanfoga([O], [O], [O]) // trots allt förblir klass O den enda och sista kandidaten = [K1, A, B, C, O] L(K2) := [K2] + sammanfoga(L(D), L(B), L(E), [D, B, E]) = [K2] + sammanfoga([D, O], [B, O], [E, O], [D, B, E]) // välj D = [K2, D] + sammanfoga([O], [B, O], [E, O], [B, E]) // O är inte lämplig, välj B = [K2, D, B] + sammanfoga([O], [O], [E, O], [E]) // O passar inte, välj E = [K2, D, B, E] + sammanfoga([O], [O], [O]) // välj O = [K2, D, B, E, O] L(K3) := [K3] + sammanfoga(L(D), L(A), [D, A]) = [K3] + sammanfoga([D, O], [A, O], [D, A]) = [K3, D] + sammanfoga([O], [A, O], [A]) = [K3, D, A] + sammanfoga([O], [O]) = [K3, D, A, O] L(Z) := [Z] + sammanfoga(L(K1), L(K2), L(K3), [K1, K2, K3]) = [Z] + sammanfoga([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3]) / / välj K1 = [Z, K1] + sammanfoga([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3]) // A inte lämplig, välj K2 = [Z, K1, K2] + sammanfoga([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3]) // A inte' t passar , D passar inte, välj K3 = [Z, K1, K2, K3] + sammanfoga([A, B, C, O], [D, B, E, O], [D, A, O]) // A passar inte, välj D = [Z, K1, K2, K3, D] + sammanfoga([A, B, C, O], [B, E, O], [A, O]) // välj A = [Z, K1, K2, K3, D, A] + sammanfoga([B, C, O], [B, E, O], [O]) // välj B = [Z, K1, K2, K3, D, A, B] + sammanfoga([C, O], [E, O], [O]) // välj C = [Z, K1, K2, K3, D, A, B, C] + sammanfoga([O], [E, O], [O]) // O passar inte, välj E = [Z, K1, K2, K3, D, A, B, C, E] + sammanfoga([O], [O], [O]) // välj O = [Z, K1, K2, K3, D, A, B, C, E, O] // svarBeteckningar:
L(Klass) - linjärisering av klass Klass [A,B,C] - en lista med tre element, där huvudet är A och svansen är [B,C] slå samman - slå samman listorMerge-funktionen slår samman listor på ett sådant sätt att varje element förekommer exakt en gång i resultatet, på så sätt liknar det att slå samman mängder, men ordningen på elementen i listan är viktig här. Sammanfogningsfunktionen fungerar enligt följande - den itererar över argumentlistorna i ordningsföljd (från vänster till höger), väljer det första elementet, som kan vara det första i flera listor, men inte nämns någonstans i den andra och därefter, och flyttar den till resultatlistan, exklusive från listorna -argument, upprepar denna procedur flera gånger tills alla element flyttas från argumentlistorna till resultatlistan. Om det i något skede uppstår en situation att det är omöjligt att välja ett kandidatelement som uppfyller det angivna villkoret, d.v.s. om i alla argumentlistor de första elementen inte förekommer först i andra argumentlistor skapas inte den resulterande listan.