Co to jest niezmiennik?
Odpowiedzi:
Niezmiennik jest bardziej „pojęciowy” niż zmienna. Ogólnie rzecz biorąc, jest to właściwość stanu programu, która jest zawsze prawdziwa. Mówi się, że funkcja lub metoda zapewniająca, że niezmienne trzymanie zachowuje niezmienność.
Na przykład, binarne drzewo wyszukiwania może mieć niezmiennik, że dla każdego węzła klucz lewego dziecka węzła jest mniejszy niż własny klucz węzła. Prawidłowo napisana funkcja wstawiania dla tego drzewa zachowa tę niezmienność.
Jak widać, nie jest to coś, co można przechowywać w zmiennej: jest to bardziej oświadczenie o programie. Zastanawiając się, jakie rodzaje niezmienników powinien utrzymywać Twój program, a następnie sprawdzając kod, aby upewnić się, że faktycznie zachowuje te niezmienniki, możesz uniknąć błędów logicznych w kodzie.
Jest to warunek, o którym wiesz, że zawsze jest prawdziwy w określonym miejscu logiki i możesz go sprawdzić podczas debugowania, aby dowiedzieć się, co poszło nie tak.
Zwykle postrzegam je bardziej w kategoriach algorytmów lub struktur.
Na przykład, możesz mieć niezmienną pętlę, którą można by potwierdzić - zawsze prawda na początku lub na końcu każdej iteracji. To znaczy, jeśli twoja pętla miałaby przetwarzać kolekcję obiektów z jednego stosu do drugiego, możesz powiedzieć, że | stack1 | + | stack2 | = c, na górze lub na dole pętli.
Jeśli niezmienne sprawdzenie nie powiodło się, oznaczałoby to, że coś poszło nie tak. W tym przykładzie może to oznaczać, że zapomniałeś włożyć przetworzonego elementu na ostatni stos itp.
Magia Wikipedii: niezmienny (informatyka)
W informatyce predykat, który, jeśli jest prawdziwy, pozostanie prawdziwy przez określoną sekwencję operacji, nazywany jest () niezmiennikiem tej sekwencji.
Zgodnie z tym wierszem:
W informatyce predykat, który, jeśli jest prawdziwy, pozostanie prawdziwy przez określoną sekwencję operacji, nazywany jest () niezmiennikiem tej sekwencji.
Aby lepiej zrozumieć tę nadzieję, pomoże ten przykład w C ++.
Rozważ scenariusz, w którym musisz pobrać niektóre wartości i uzyskać ich całkowitą liczbę w zmiennej o nazwie as, counta następnie dodać je do zmiennej o nazwie assum
Niezmienna (znowu to bardziej jak pojęcie):
// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades
Kod powyższego mógłby wyglądać mniej więcej tak,
int count=0;
double sum=0,x=0;
while (cin >> x) {
++count;
sum+=x;
}
Co robi powyższy kod?
1) Odczytuje dane wejściowe z cini umieszcza jex
2) Po jednym pomyślnym przeczytaniu zwiększ countisum = sum + x
3) Powtarzaj 1-2 do zatrzymania odczytu (np. Ctrl + D)
Niezmiennik pętli:
Niezmiennik musi mieć wartość True ZAWSZE . Więc początkowo zaczynasz swój kod właśnie od tego
while(cin>>x){
}
Ta pętla odczytuje dane ze standardowego wejścia i przechowuje w x. Dobrze i dobrze. Ale niezmiennik staje się fałszywy, ponieważ pierwsza część naszego niezmiennika nie była przestrzegana (lub utrzymywana jako prawda).
// we have read count grades so far, and
Jak sprawić, by niezmiennik był prawdziwy?
Prosty! liczba przyrostów.
Więc ++count;dobrze by było !. Teraz nasz kod wygląda mniej więcej tak,
while(cin>>x){
++count;
}
Ale
Nawet teraz nasz niezmiennik (koncepcja, która musi być PRAWDA) jest fałszywa, ponieważ teraz nie spełniliśmy drugiej części naszego niezmiennika.
// sum is the sum of the first count grades
Więc co teraz zrobić?
Dodaj xdo sumi zapisz w sum( sum+=x), a następnym razem
cin>>xwczyta nową wartość do x.
Teraz nasz kod wygląda mniej więcej tak,
while(cin>>x){
++count;
sum+=x;
}
Sprawdźmy
Czy kod pasuje do naszego niezmiennika
// invariant:
// we have read count grades so far, and
// sum is the sum of the first count grades
kod:
while(cin>>x){
++count;
sum+=x;
}
Ach !. Teraz niezmiennikiem pętli jest zawsze True i kod działa dobrze.
Powyższy przykład został wzięty i zmodyfikowany z książki Accelerated C ++ autorstwa Andrew-koeninga i Barbary-E
Idąc dalej, niezmienniki są bardzo przydatne w pisaniu czystego kodu, ponieważ wiedza koncepcyjna o tym, jakie niezmienniki powinny znajdować się w kodzie, pozwala łatwo zdecydować, jak zorganizować kod, aby osiągnąć te cele. Jak wspomniano wcześniej, są one również przydatne w debugowaniu, ponieważ sprawdzenie, czy utrzymywany jest niezmiennik, jest często dobrym sposobem sprawdzenia, czy jakakolwiek manipulacja, którą próbujesz wykonać, faktycznie robi to, czego chcesz.
Zwykle jest to wielkość, która nie zmienia się pod wpływem pewnych operacji matematycznych. Przykładem jest skalarne, która nie zmienia się pod wpływem obrotów. Na przykład w obrazowaniu metodą rezonansu magnetycznego przydatne jest scharakteryzowanie właściwości tkanki za pomocą niezmiennika rotacji, ponieważ wówczas jej ocena idealnie nie zależy od orientacji ciała w skanerze.
Ta odpowiedź jest dla mojego 5-letniego dziecka. Nie myśl o niezmienniku jako o stałej lub stałej wartości liczbowej. Ale może być. Jednak to coś więcej.
Raczej niezmiennik jest czymś w rodzaju stałego związku między różnymi bytami. Na przykład Twój wiek zawsze będzie niższy w porównaniu z Twoimi biologicznymi rodzicami. Zarówno twój wiek, jak i wiek twojego rodzica zmieniają się z upływem czasu, ale związek, o którym wspomniałem powyżej, jest niezmienny.
Niezmiennik może być również stałą numeryczną. Na przykład wartość pijest niezmiennym stosunkiem obwodu koła do jego średnicy. Bez względu na to, jak duże lub małe jest koło, stosunek ten zawsze będzie pi.
Niezmiennik ADT określa relacje między polami danych (zmiennymi instancji), które zawsze muszą być prawdziwe przed i po wykonaniu dowolnej metody instancji.
Doskonały przykład niezmiennika i dlaczego ma to znaczenie w książce Java Concurrency in Practice .
Chociaż jest skoncentrowany na języku Java, przykład opisuje kod odpowiedzialny za obliczanie współczynników podanej liczby całkowitej. Przykładowy kod próbuje buforować ostatnią podaną liczbę oraz czynniki, które zostały obliczone w celu poprawy wydajności. W tym scenariuszu istnieje niezmiennik, który nie został uwzględniony w przykładowym kodzie, który pozostawił kod podatny na warunki wyścigu w scenariuszu współbieżnym.
Wszystkie odpowiedzi tutaj są świetne, ale czułem, że mogę rzucić więcej światła na tę sprawę:
Niezmienny z językowego punktu widzenia oznacza coś, co nigdy się nie zmienia. Koncepcja ta jednak pochodzi z matematyki, jest to jedna z popularnych technik dowodzenia w połączeniu z indukcją.
Oto jak przebiega dowód, jeśli możesz znaleźć niezmiennik, który jest w stanie początkowym, I że ten niezmiennik utrzymuje się niezależnie od jakiejkolwiek transformacji [prawnej] zastosowanej do stanu, to możesz udowodnić, że jeśli określony stan tego nie ma niezmienny to nigdy nie może wystąpić, bez względu na to, jaka sekwencja przekształceń zostanie zastosowana do stanu początkowego.
Teraz poprzedni sposób myślenia (ponownie połączony z indukcją) umożliwia orzekanie o logice oprogramowania komputerowego. Szczególnie ważne, gdy wykonanie odbywa się w pętlach, w których niezmiennik może być użyty do udowodnienia, że dana pętla przyniesie określony wynik lub że nigdy nie zmieni stanu programu w określony sposób.
Gdy niezmiennik jest używany do predykowania logiki pętli, nazywa się to niezmiennikiem pętli . Można go używać poza pętlami, ale w przypadku pętli jest to naprawdę ważne, ponieważ często masz dużo możliwości lub nieskończoną liczbę możliwości.
Zauważ, że używam słowa „orzeczenie” logiki oprogramowania komputerowego, a nie dowodzenie. A to dlatego, że podczas gdy niezmiennik matematyczny może być użyty jako dowód, nigdy nie może udowodnić, że oprogramowanie komputerowe po wykonaniu da to, czego się oczekuje, ze względu na fakt, że oprogramowanie jest wykonywane na podstawie wielu abstrakcji, których nigdy nie można udowodnić że dadzą to, czego się oczekuje (pomyślmy na przykład o abstrakcji sprzętu).
Wreszcie, podczas gdy teoretyczne i rygorystyczne przewidywanie logiki oprogramowania jest ważne tylko w przypadku aplikacji o wysokim krytycznym znaczeniu, takich jak medyczne i wojskowe. Niezmiennik może być nadal używany do wspomagania typowego programisty podczas debugowania. Można go użyć, aby wiedzieć, gdzie w określonej lokalizacji Program zawiódł, ponieważ nie udało mu się zachować pewnej niezmiennika - wielu z nas i tak używa go bez zastanowienia.