Jak pisać prawidłowe pętle?

65

Większość czasu podczas pisania pętli zwykle piszę złe warunki brzegowe (np .: zły wynik) lub moje założenia dotyczące zakończenia pętli są błędne (np. Nieskończenie działająca pętla). Mimo że moje założenia były prawidłowe po kilku próbach i błędach, ale byłem zbyt sfrustrowany z powodu braku poprawnego modelu obliczeniowego w mojej głowie.

/**
 * Inserts the given value in proper position in the sorted subarray i.e. 
 * array[0...rightIndex] is the sorted subarray, on inserting a new value 
 * our new sorted subarray becomes array[0...rightIndex+1].
 * @param array The whole array whose initial elements [0...rightIndex] are 
 * sorted.
 * @param rightIndex The index till which sub array is sorted.
 * @param value The value to be inserted into sorted sub array.
 */
function insert(array, rightIndex, value) {
    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];
    }   
    array[j + 1] = value; 
};

Błędy, które popełniłem na początku to:

  1. Zamiast j> = 0 zachowałem j> 0.
  2. Mam wątpliwości, czy tablica [j + 1] = wartość, czy tablica [j] = wartość.

Jakie są narzędzia / modele mentalne, aby uniknąć takich błędów?

CodeYogi
źródło
6
W jakich okolicznościach uważasz, że j >= 0to pomyłka? Byłbym bardziej ostrożny wobec tego, że uzyskujesz dostęp array[j]i array[j + 1]bez uprzedniej kontroli array.length > (j + 1).
Ben Cottrell,
5
podobnie jak powiedział @LightnessRacesinOrbit, prawdopodobnie rozwiązujesz problemy, które już zostały rozwiązane. Ogólnie mówiąc, wszelkie pętle, które należy wykonać w strukturze danych, istnieją już w niektórych podstawowych modułach lub klasach (na Array.prototypeprzykładzie JS). Zapobiega to napotkaniu warunków brzegowych, ponieważ coś takiego mapdziała na wszystkich tablicach. Możesz rozwiązać powyższe za pomocą plasterka i konkatatu, aby uniknąć zapętlenia: codepen.io/anon/pen/ZWovdg?editors=0012 Najbardziej poprawnym sposobem na napisanie pętli jest jej całkowite pominięcie .
Jed Schneider
13
Właściwie, śmiało i rozwiązuj rozwiązane problemy. To się nazywa praktyka. Tylko nie zawracaj sobie głowy ich publikowaniem. To znaczy, chyba że znajdziesz sposób na ulepszenie rozwiązań. To powiedziawszy, wynalezienie koła wymaga więcej niż koła. Obejmuje cały system kontroli jakości kół i obsługę klienta. Nadal niestandardowe felgi są ładne.
candied_orange 17.04.16
53
Obawiam się, że zmierzamy w złym kierunku. Dawanie bzdur CodeYogi, ponieważ jego przykład jest częścią dobrze znanego algorytmu, jest raczej bezpodstawny. Nigdy nie twierdził, że wynalazł coś nowego. Pyta, jak uniknąć bardzo częstych błędów granicznych podczas pisania pętli. Biblioteki przeszły długą drogę, ale wciąż widzę przyszłość dla ludzi, którzy wiedzą, jak pisać pętle.
candied_orange 17.04.16
5
Zasadniczo, mając do czynienia z pętlami i indeksami, powinieneś nauczyć się, że indeksy wskazują między elementami i zapoznać się z półotwartymi przedziałami (w rzeczywistości są to dwie strony tych samych pojęć). Po uzyskaniu tych faktów większość pętli / indeksów drapanie głowy znika całkowicie.
Matteo Italia,

Odpowiedzi:

208

Test

Poważnie, nie testuj.

Koduję od ponad 20 lat i nadal nie ufam sobie, że za pierwszym razem poprawnie zapiszę pętlę. Piszę i uruchamiam testy, które dowodzą, że działa, zanim podejrzewam, że działa. Przetestuj każdą stronę każdego warunku brzegowego. Na przykład co rightIndex0 powinien zrobić? A może -1?

Nie komplikuj

Jeśli inni nie widzą, co robi na pierwszy rzut oka, utrudniasz to. Możesz zignorować wydajność, jeśli oznacza to, że możesz napisać coś łatwego do zrozumienia. Przyspiesz tylko w mało prawdopodobnym przypadku, którego naprawdę potrzebujesz. I nawet wtedy, gdy jesteś absolutnie pewien, że dokładnie wiesz, co Cię spowalnia. Jeśli możesz osiągnąć faktyczną poprawę Big O, działanie to może nie być bezcelowe, ale nawet wtedy spraw, aby Twój kod był jak najbardziej czytelny.

Wyłączone o jeden

Poznaj różnicę między liczeniem palców a liczeniem odstępów między palcami. Czasami przestrzeń jest naprawdę ważna. Nie pozwól, aby twoje palce cię rozpraszały. Dowiedz się, czy twój kciuk jest palcem. Dowiedz się, czy odstęp między Twoim paluszkiem a kciukiem liczy się jako spacja.

Komentarze

Zanim zgubisz się w kodzie, spróbuj powiedzieć, co masz na myśli po angielsku. Jasno określ swoje oczekiwania. Nie wyjaśniaj, jak działa kod. Wyjaśnij, dlaczego robisz to, co robi. Ukryj szczegóły implementacji. Kod powinien być refaktoryzowany bez konieczności zmiany komentarza.

Najlepszy komentarz to dobre imię.

Jeśli możesz powiedzieć wszystko, co musisz powiedzieć dobrym imieniem, NIE mów tego ponownie z komentarzem.

Abstrakcje

Obiekty, funkcje, tablice i zmienne są abstrakcjami, które są tak dobre, jak ich nazwy. Nadaj im nazwy, które zapewnią, że kiedy ludzie będą w nich zaglądać, nie będą zaskoczeni tym, co znajdą.

Krótkie imiona

Używaj krótkich nazw dla rzeczy krótkotrwałych. ijest dobrą nazwą dla indeksu w ładnej ciasnej pętli w małym zakresie, co czyni go oczywistym. Jeśli iżycie wystarcza na tyle długo, aby rozłożyć się po linii z innymi pomysłami i nazwami, które można pomylić, inadszedł czas, aby nadać iładne, długie, objaśniające imię.

Długie imiona

Nigdy nie skracaj nazwy ze względu na długość linii. Znajdź inny sposób ułożenia kodu.

Biała przestrzeń

Wady uwielbiają ukrywać się w nieczytelnym kodzie. Jeśli twój język pozwala ci wybrać styl wcięcia, przynajmniej bądź spójny. Nie sprawiaj, że Twój kod wygląda jak strumień hałasu. Kod powinien wyglądać, jakby maszerował w szyku.

Konstrukcje pętli

Dowiedz się i przejrzyj struktury pętli w swoim języku. Oglądanie podświetlenia for(;;)pętli przez debugger może być bardzo pouczające. Naucz się wszystkich form. while, do while, while(true), for each. Użyj najprostszego, z którego możesz uciec. Spójrz, zalewając pompę . Dowiedzieć się, co breaki continuezrobić, jeśli je masz. Poznaj różnicę między c++i ++c. Nie bój się wracać wcześniej, dopóki zawsze zamykasz wszystko, co wymaga zamknięcia. Na koniec blokuje lub najlepiej coś, co oznacza to automatyczne zamykanie po otwarciu: Korzystanie z instrukcji / Spróbuj z zasobami .

Alternatywne pętle

Pozwól, aby coś innego wykonało pętlę, jeśli możesz. To jest łatwiejsze dla oczu i już debugowane. Pochodzą one w wielu formach: zbiory lub strumienie, które pozwalają map(), reduce(), foreach(), i inne takie metody, które stosują lambda. Poszukaj funkcji specjalnych, takich jak Arrays.fill(). Występuje również rekurencja, ale spodziewaj się, że ułatwi to w szczególnych przypadkach. Zasadniczo nie używaj rekurencji, dopóki nie zobaczysz, jak wyglądałaby alternatywa.

Och, i przetestuj.

Test, test, test.

Czy wspomniałem o testowaniu?

Była jeszcze jedna rzecz. Nie pamiętam Zaczęło się od T ...

candied_orange
źródło
36
Dobra odpowiedź, ale może powinieneś wspomnieć o testowaniu. Jak radzić sobie z nieskończoną pętlą w teście jednostkowym? Czy taka pętla nie „zrywa” testów ???
GameAlchemist 17.04.16
139
@GameAlchemist To test pizzy. Jeśli mój kod nie przestaje działać w czasie, który zajmuje mi zrobienie pizzy, zaczynam podejrzewać, że coś jest nie tak. Jasne, to nie jest lekarstwo na problem z zatrzymaniem Alana Turinga, ale przynajmniej dostaję pizzę poza umową.
candied_orange 17.04.16
12
@CodeYogi - w rzeczywistości może być bardzo blisko. Rozpocznij od testu, który działa na pojedynczej wartości. Zaimplementuj kod bez pętli. Następnie napisz test, który działa na dwóch wartościach. Zaimplementuj pętlę. Jest bardzo mało prawdopodobne, że dostaniesz błędny warunek brzegowy w pętli, jeśli zrobisz to w ten sposób, ponieważ w prawie wszystkich okolicznościach jeden lub drugi z tych dwóch testów zakończy się niepowodzeniem, jeśli popełnisz taki błąd.
Jules
15
@CodeYogi Koleś należny kredyt TDD, ale testowanie >> TDD. Wyprowadzanie wartości może być testowaniem, testowanie drugiego zestawu oczu (możesz sformalizować to jako przegląd kodu, ale często po prostu łapię kogoś na 5-minutową rozmowę). Test to szansa, że ​​wyrazisz zamiar niepowodzenia. Do diabła, możesz przetestować swój kod, rozmawiając z mamą. Znalazłem błędy w moim kodzie, gdy patrzyłem na kafelek pod prysznicem. TDD to skuteczna, sformalizowana dyscyplina, której nie ma w każdym sklepie. Nigdy nie kodowałem nigdzie, gdzie ludzie nie testowali.
candied_orange 17.04.16
12
Kodowałem i testowałem wiele lat, zanim jeszcze usłyszałem o TDD. Dopiero teraz zdaję sobie sprawę z korelacji tych lat z latami spędzonymi na kodowaniu bez spodni.
candied_orange 18.04.16
72

Podczas programowania warto pomyśleć o:

a podczas eksploracji niezbadanego terytorium (takiego jak żonglowanie indeksami) bardzo, bardzo przydatne może być nie tylko myśleć o nich, ale w rzeczywistości wyrażać je w kodzie za pomocą asercji .

Weźmy twój oryginalny kod:

/**
 * Inserts the given value in proper position in the sorted subarray i.e. 
 * array[0...rightIndex] is the sorted subarray, on inserting a new value 
 * our new sorted subarray becomes array[0...rightIndex+1].
 * @param array The whole array whose initial elements [0...rightIndex] are 
 * sorted.
 * @param rightIndex The index till which sub array is sorted.
 * @param value The value to be inserted into sorted sub array.
 */
function insert(array, rightIndex, value) {
    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];
    }   
    array[j + 1] = value; 
};

I sprawdź, co mamy:

  • warunek wstępny: array[0..rightIndex]jest posortowany
  • warunek końcowy: array[0..rightIndex+1]jest posortowany
  • niezmienny: 0 <= j <= rightIndexale wydaje się nieco zbędny; lub jako @Jules zauważył w komentarzach, na końcu „rundzie” for n in [j, rightIndex+1] => array[j] > value.
  • niezmienny: na końcu „rundy” array[0..rightIndex+1]jest sortowany

Możesz więc najpierw napisać is_sortedfunkcję, a także minfunkcję działającą na wycinku tablicy, a następnie potwierdzić:

function insert(array, rightIndex, value) {
    assert(is_sorted(array[0..rightIndex]));

    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];

        assert(min(array[j..rightIndex+1]) > value);
        assert(is_sorted(array[0..rightIndex+1]));
    }   
    array[j + 1] = value; 

    assert(is_sorted(array[0..rightIndex+1]));
};

Istnieje również fakt, że stan pętli jest nieco skomplikowany; możesz to ułatwić sobie, dzieląc rzeczy:

function insert(array, rightIndex, value) {
    assert(is_sorted(array[0..rightIndex]));

    for (var j = rightIndex; j >= 0; j--) {
        if (array[j] <= value) { break; }

        array[j + 1] = array[j];

        assert(min(array[j..rightIndex+1]) > value);
        assert(is_sorted(array[0..rightIndex+1]));
    }   
    array[j + 1] = value; 

    assert(is_sorted(array[0..rightIndex+1]));
};

Teraz pętla jest prosta ( jprzechodzi od rightIndexdo 0).

Wreszcie, teraz należy to przetestować:

  • pomyśl o warunkach brzegowych ( rightIndex == 0, rightIndex == array.size - 2)
  • pomyśl o valuebyciu mniejszym array[0]lub większym niżarray[rightIndex]
  • myśleć o valuerównym array[0], array[rightIndex]lub jakimś średnim indeksie

Nie lekceważ też rozmycia . Masz asercje do wychwytywania błędów, więc wygeneruj losową tablicę i posortuj ją za pomocą swojej metody. Jeśli zadziała asercja, znalazłeś błąd i możesz rozszerzyć swój pakiet testowy.

Matthieu M.
źródło
8
@CodeYogi: Z ... testami. Chodzi o to, że wyrażanie wszystkiego w asercjach może być niepraktyczne : jeśli asercja po prostu powtarza kod, to nie przynosi niczego nowego (powtórzenie nie pomaga w jakości). To dlatego tu nie twierdzić, że w pętli 0 <= j <= rightIndexlub array[j] <= value, byłoby to po prostu powtórzyć kod. Z drugiej strony is_sortedprzynosi nową gwarancję, dlatego jest cenna. Następnie do tego służą testy. Jeśli zadzwonisz insert([0, 1, 2], 2, 3)do swojej funkcji, a wynik nie [0, 1, 2, 3]zostanie znaleziony, to znajdziesz błąd.
Matthieu M.
3
@MatthieuM. nie pomijaj wartości asercji tylko dlatego, że powiela ona kod. Rzeczywiście, mogą to być bardzo cenne twierdzenia, jeśli zdecydujesz się przepisać kod. Testowanie ma wszelkie prawo do powielania się. Zastanów się raczej, czy asercja jest tak sprzężona z pojedynczą implementacją kodu, że każde przepisanie unieważniłoby asercję. Wtedy marnujesz swój czas. Nawiasem mówiąc, fajna odpowiedź.
candied_orange 17.04.16
1
@CandiedOrange: Przez powielenie kodu mam na myśli dosłownie array[j+1] = array[j]; assert(array[j+1] == array[j]);. W tym przypadku wartość wydaje się bardzo niska (jest to kopia / wklej). Jeśli powielisz znaczenie, ale wyrazisz je w inny sposób, staje się ono bardziej wartościowe.
Matthieu M.
10
Reguły Hoare'a: pomaganie w pisaniu poprawnych pętli od 1969 roku. „Mimo to, że techniki te są znane od ponad dekady, większość porgramerów nigdy o nich nie słyszała”.
Joker_vD 18.04.16
1
@MatthieuM. Zgadzam się, że ma bardzo niską wartość. Ale nie uważam tego za spowodowane kopiowaniem / wklejaniem. Powiedzmy, że chciałem zrefaktoryzować insert()tak, aby działało, kopiując ze starej tablicy na nową. Można to zrobić bez zepsucia innych assert. Ale nie ten ostatni. Pokazuje tylko, jak dobrze assertzostały zaprojektowane Twoje inne .
candied_orange 18.04.16
29

Użyj testu jednostkowego / TDD

Jeśli naprawdę potrzebujesz dostępu do sekwencji za pośrednictwem forpętli, możesz uniknąć błędów poprzez testy jednostkowe , a zwłaszcza programowanie oparte na testach .

Wyobraź sobie, że musisz zaimplementować metodę, która przyjmuje wartości wyższe od zera w odwrotnej kolejności. Jakie przypadki testowe możesz wymyślić?

  1. Sekwencja zawiera jedną wartość wyższą od zera.

    Rzeczywista: [5]. Oczekiwany: [5].

    Najprostsza implementacja, która spełnia wymagania, polega po prostu na zwróceniu sekwencji źródłowej dzwoniącemu.

  2. Sekwencja zawiera dwie wartości, obie powyżej zera.

    Rzeczywista: [5, 7]. Oczekiwany: [7, 5].

    Teraz nie możesz po prostu zwrócić sekwencji, ale powinieneś ją odwrócić. Jeśli użyjesz for (;;)pętli, konstrukcja innego języka lub metoda biblioteczna nie ma znaczenia.

  3. Sekwencja zawiera trzy wartości, z których jedna to zero.

    Rzeczywista: [5, 0, 7]. Oczekiwany: [7, 5].

    Teraz powinieneś zmienić kod, aby filtrować wartości. Ponownie można to wyrazić za pomocą ifinstrukcji lub wywołania ulubionej metody frameworka.

  4. W zależności od algorytmu (ponieważ jest to testowanie w białej skrzynce, ważna jest implementacja), może być konieczne potraktowanie konkretnie pustej sekwencji [] → [], a może nie. Lub może mieć pewność, że sprawa krawędzi, gdzie wszystkie wartości są ujemne [-4, 0, -5, 0] → []są obsługiwane poprawnie, a nawet, że graniczne wartości ujemne są: [6, 4, -1] → [4, 6]; [-1, 6, 4] → [4, 6]. Jednak w wielu przypadkach będziesz mieć tylko trzy testy opisane powyżej: jakikolwiek dodatkowy test nie spowoduje zmiany kodu, a więc nie będzie miał znaczenia.

Pracuj na wyższym poziomie abstrakcji

Jednak w wielu przypadkach można uniknąć większości tych błędów, pracując na wyższym poziomie abstrakcji, używając istniejących bibliotek / frameworków. Te biblioteki / ramy umożliwiają odwracanie, sortowanie, dzielenie i łączenie sekwencji, wstawianie lub usuwanie wartości w tablicach lub podwójnie połączonych listach itp.

Zwykle foreachmożna go użyć zamiast for, dzięki czemu sprawdzanie warunków brzegowych nie ma znaczenia: język robi to za Ciebie. Niektóre języki, takie jak Python, nawet nie mają for (;;)konstrukcji, ale tylko for ... in ....

W języku C # LINQ jest szczególnie wygodny podczas pracy z sekwencjami.

var result = source.Skip(5).TakeWhile(c => c > 0);

jest znacznie bardziej czytelny i mniej podatny na błędy w porównaniu do swojego forwariantu:

for (int i = 5; i < source.Length; i++)
{
    var value = source[i];
    if (value <= 0)
    {
        break;
    }

    yield return value;
}
Arseni Mourzenko
źródło
3
Cóż, z twojego pierwotnego pytania mam wrażenie, że wybór jest z jednej strony przy użyciu TDD i znalezienia właściwego rozwiązania, az drugiej strony pomijanie części testowej i błędne warunki brzegowe.
Arseni Mourzenko
18
Dziękuję za to, że jeden wspomnieć słonia w pokoju: nie za pomocą pętli w ogóle . Dlaczego ludzie wciąż kodują jak w 1985 roku (a ja jestem hojny) jest poza mną. BOCTAOE.
Jared Smith
4
@JaredSmith Kiedy komputer faktycznie wykona ten kod, ile chcesz założyć, że nie ma tam instrukcji skoku? Używając LINQ, abstrahujesz pętlę, ale ona nadal tam jest. Wyjaśniłem to współpracownikom, którzy nie dowiedzieli się o ciężkiej pracy malarza Shlemiela . Niezrozumienie, gdzie występują pętle, nawet jeśli są one abstrakcyjne w kodzie, a kod jest znacznie bardziej czytelny, w rezultacie prawie niezmiennie prowadzi do problemów z wydajnością, których wyjaśnienie, a tym bardziej naprawienie, będzie utrudnione.
CVn
6
@ MichaelKjörling: kiedy używać LINQ The pętla ma, ale konstrukcja nie byłaby bardzo opisowe z tej pętli . Ważnym aspektem jest to, że LINQ (podobnie jak rozumienie list w Pythonie i podobne elementy w innych językach) sprawia, że ​​warunki brzegowe są w większości nieistotne, przynajmniej w zakresie pierwotnego pytania. Nie mogę jednak zgodzić się więcej na temat potrzeby zrozumienia, co dzieje się pod maską podczas korzystania z LINQ, szczególnie jeśli chodzi o leniwą ocenę. for(;;)
Arseni Mourzenko 18.04.16
4
@ MichaelKjörling Niekoniecznie mówiłem o LINQ i trochę nie rozumiem, o co ci chodzi. forEach, map, LazyIterator, Itd. Są dostarczane przez kompilator lub Runtime Environment języku i są prawdopodobnie mniej prawdopodobne wracając do wiadra farby na każdej iteracji. To, czytelność i błędy indywidualne to dwa powody, dla których funkcje te zostały dodane do współczesnych języków.
Jared Smith
15

Zgadzam się z innymi osobami, które mówią, przetestuj swój kod. Jednak miło jest to zrobić w pierwszej kolejności. W wielu przypadkach mam skłonność do błędnych warunków brzegowych, dlatego opracowałem sztuczki mentalne, aby zapobiec takim problemom.

W przypadku tablicy z indeksowaniem 0 normalne warunki będą następujące:

for (int i = 0; i < length; i++)

lub

for (int i = length - 1; i >= 0; i--)

Te wzory powinny stać się drugą naturą, nie powinieneś w ogóle o nich myśleć.

Ale nie wszystko jest zgodne z tym dokładnym wzorem. Więc jeśli nie masz pewności, czy napisałeś to dobrze, oto następny krok:

Podłącz wartości i oceń kod we własnym mózgu. Spraw, aby myślenie było tak proste, jak to tylko możliwe. Co się stanie, jeśli odpowiednie wartości to 0? Co się stanie, jeśli będą to jedności?

for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
    array[j + 1] = array[j];
}   
array[j + 1] = value;

W twoim przykładzie nie masz pewności, czy powinna to być [j] = wartość, czy [j + 1] = wartość. Czas zacząć oceniać go ręcznie:

Co się stanie, jeśli masz tablicę o długości 0? Odpowiedź staje się oczywista: rightIndex musi wynosić (długość - 1) == -1, więc j zaczyna się od -1, więc aby wstawić indeks 0, musisz dodać 1.

Udowodniliśmy więc, że ostateczny warunek jest prawidłowy, ale nie wewnątrz pętli.

Co się stanie, jeśli masz tablicę z 1 elementem, 10, a my spróbujemy wstawić 5? W przypadku pojedynczego elementu rightIndex powinien rozpoczynać się od 0. Więc za pierwszym razem przez pętlę, j = 0, więc „0> = 0 i 10> 5”. Ponieważ chcemy wstawić 5 w indeksie 0, 10 powinno zostać przeniesione do indeksu 1, więc tablica [1] = tablica [0]. Ponieważ dzieje się tak, gdy j wynosi 0, tablica [j + 1] = tablica [j + 0].

Jeśli spróbujesz wyobrazić sobie jakąś dużą tablicę i to, co się stanie, wstawiając w dowolne miejsce, twój mózg prawdopodobnie zostanie przytłoczony. Ale jeśli trzymasz się prostych przykładów wielkości 0/1/2, powinien być łatwy szybki przegląd mentalny i sprawdzenie, gdzie załamują się twoje warunki brzegowe.

Wyobraź sobie, że nigdy wcześniej nie słyszałeś o problemie ze słupkiem ogrodzeniowym i mówię ci, że mam 100 słupków ogrodzeniowych w linii prostej, ile segmentów między nimi. Jeśli spróbujesz wyobrazić sobie 100 słupków ogrodzeniowych w swojej głowie, po prostu zostaniesz przytłoczony. Więc co jest najmniejszą liczbą słupków ogrodzeniowych, aby stworzyć prawidłowe ogrodzenie? Potrzebujesz 2, aby zrobić ogrodzenie, więc wyobraź sobie 2 słupki, a obraz mentalny pojedynczego segmentu między słupkami czyni go bardzo wyraźnym. Nie musisz tam siedzieć licząc posty i segmenty, ponieważ sprawiłeś, że problem stał się intuicyjnie oczywisty dla twojego mózgu.

Gdy uznasz, że jest to poprawne, dobrze jest przeprowadzić test i upewnić się, że komputer robi to, co według ciebie powinno, ale w tym momencie powinna to być tylko formalność.

Bryce Wagner
źródło
4
Bardzo mi się podoba for (int i = 0; i < length; i++). Po przyzwyczajeniu się do tego nawyku przestałem używać <=prawie tak często i czułem, że pętle stały się prostsze. Ale for (int i = length - 1; i >= 0; i--)wydaje się to zbyt skomplikowane, w porównaniu do: for (int i=length; i--; )(co prawdopodobnie byłoby bardziej rozsądne, gdyby napisać jako whilepętlę, chyba że starałem się, aby imieć mniejszy zakres / życie). Wynik nadal przechodzi przez pętlę z i == długość-1 (początkowo) do i == 0, przy czym jedyną różnicą funkcjonalną jest to, że while()wersja kończy się z i == -1 po pętli (jeśli trwa), zamiast i = = 0
TOOGAM
2
@TOOGAM (int i = length; i--;) działa w C / C ++, ponieważ 0 jest interpretowane jako fałsz, ale nie wszystkie języki mają tę równoważność. Wydaje mi się, że można powiedzieć, że -> 0.
Bryce Wagner
Oczywiście, jeśli używasz języka wymagającego „ > 0”, aby uzyskać pożądaną funkcjonalność, należy użyć takich znaków, ponieważ są one wymagane przez ten język. Jednak nawet w tych przypadkach użycie samego „ > 0” jest prostsze niż wykonanie dwuczęściowego procesu najpierw odejmowania jednego, a następnie również używania „ >= 0”. Kiedy nauczyłem się tego, dzięki odrobinie doświadczenia, przyzwyczaiłem się do używania znaku równości (np. „ >= 0”) W warunkach testu pętli o wiele rzadziej, a wynikowy kod wydaje się odtąd łatwiejszy.
TOOGAM 18.04.16
1
@BryceWagner, jeśli musisz to zrobić i-- > 0, spróbuj klasycznego żartu i --> 0!
porglezomp 18.04.16
3
@porglezomp Ach, tak, trafia do operatora . Większość języków podobnych do C, w tym C, C ++, Java i C #, ma taki język.
CVn
11

Byłem zbyt sfrustrowany z powodu braku poprawnego modelu komputerowego w mojej głowie.

Jest bardzo interesującym punktem tego pytania i wygenerowało następujący komentarz:

Jest tylko jeden sposób: lepiej zrozumieć swój problem. Ale to jest tak ogólne, jak twoje pytanie. - Thomas Junk

... i Thomas ma rację. Brak wyraźnego zamiaru dla funkcji powinien być czerwoną flagą - wyraźnym wskazaniem, że należy natychmiast ZATRZYMAĆ się, wziąć ołówek i papier, odejść od IDE i właściwie rozwiązać problem; a przynajmniej sprawdzać rozsądek, co zrobiłeś.

Widziałem tak wiele funkcji i klas, które stały się kompletnym bałaganem, ponieważ autorzy próbowali zdefiniować implementację, zanim w pełni zdefiniowali problem. I tak łatwo sobie z tym poradzić.

Jeśli nie w pełni rozumiesz problem, prawdopodobnie nie będziesz w stanie kodować optymalnego rozwiązania (pod względem wydajności lub przejrzystości), ani nie będziesz w stanie stworzyć naprawdę użytecznych testów jednostkowych w metodologii TDD.

Weź swój kod tutaj jako przykład, zawiera on wiele potencjalnych wad, których jeszcze nie rozważałeś, na przykład: -

  • co jeśli prawy indeks jest zbyt niski? (wskazówka: będzie utratę danych)
  • co jeśli rightIndex jest poza granicami tablicy? (dostaniesz wyjątek, czy sam stworzyłeś przepełnienie bufora?)

Istnieje kilka innych problemów związanych z wydajnością i projektem kodu ...

  • czy ten kod będzie wymagał skalowania? Czy utrzymywanie tablicy w sortowaniu jest najlepszą opcją, czy powinieneś spojrzeć na inne opcje (np. Listę połączoną?)
  • czy możesz być pewien swoich założeń? (czy możesz zagwarantować sortowanie tablicy, a jeśli tak nie jest?)
  • czy wynajdujesz koło? Posortowane tablice są dobrze znanym problemem, czy studiowałeś istniejące rozwiązania? Czy jest już dostępne rozwiązanie w twoim języku (na przykład SortedList<t>w C #)?
  • czy należy ręcznie kopiować jedną pozycję tablicy na raz? lub czy Twój język udostępnia popularne funkcje, takie jak JScript Array.Insert(...)? czy ten kod byłby jaśniejszy?

Istnieje wiele sposobów na ulepszenie tego kodu, ale dopóki nie zdefiniujesz poprawnie, co musisz zrobić, nie tworzysz kodu, po prostu hakujesz go razem w nadziei, że zadziała. Zainwestuj w to czas, a twoje życie stanie się łatwiejsze.

James Snell
źródło
2
Nawet jeśli przekazujesz swoje indeksy do istniejącej funkcji (takiej jak Array.Copy), nadal może być konieczne przemyślenie, aby uzyskać poprawne warunki powiązane. Wyobrażenie sobie, co dzieje się w sytuacjach 0 długości i 1 długości i 2 długości może być najlepszym sposobem, aby upewnić się, że nie kopiujesz za mało lub za dużo.
Bryce Wagner,
@BryceWagner - Absolutnie prawda, ale bez jasnego pojęcia, jaki problem polega na tym, że tak naprawdę rozwiązujesz, spędzasz dużo czasu na rzucaniu się w ciemności w strategii „trafienia i nadziei”, która jest zdecydowanie PO największy problem w tym momencie.
James Snell
2
@CodeYogi - masz i, jak zauważyli inni, dość słabo podzieliłeś problem na podproblemy, dlatego wiele odpowiedzi wspomina o twoim podejściu do rozwiązania problemu jako sposobie jego uniknięcia. To nie jest coś, co powinieneś wziąć osobiście, po prostu doświadczenie od tych z nas, którzy tam byli.
James Snell 17.04.16
2
@CodeYogi, myślę, że mogłeś pomylić tę stronę z przepełnieniem stosu. Ta strona jest odpowiednikiem sesji pytań i odpowiedzi na tablicy , a nie na terminalu komputerowym. „Pokaż kod” to dość wyraźne wskazanie, że znajdujesz się na niewłaściwej stronie.
Wildcard
2
@Wildcard +1: „Pokaż mi kod” jest dla mnie doskonałym wskaźnikiem tego, dlaczego ta odpowiedź jest prawidłowa i że może potrzebuję pracy nad sposobami lepszego wykazania, że ​​jest to problem związany z czynnikiem ludzkim / projektem, który może tylko zostać uwzględnione przez zmiany w ludzkim procesie - żadna ilość kodu nie mogłaby go nauczyć.
James Snell,
10

Błędy off-by-one są jednym z najczęstszych błędów programistycznych. Nawet doświadczeni programiści czasami mylą się. Języki wyższego poziomu zwykle mają konstrukcje iteracyjne podobne foreachlub mapcałkowicie unikające jawnego indeksowania. Ale czasami potrzebujesz jawnego indeksowania, jak w twoim przykładzie.

Wyzwanie polega na tym, jak myśleć o zakresach komórek macierzy. Bez jasnego modelu mentalnego mylące jest, kiedy uwzględnić lub wykluczyć punkty końcowe.

Opisując zakresy tablic, konwencja obejmuje dolną granicę, wykluczając górną granicę . Na przykład zakres 0..3 to komórki 0,1,2. Te konwencje są używane we wszystkich językach indeksowanych 0, na przykład slice(start, end)metoda w JavaScript zwraca podtablicę zaczynającą się od indeksu startdo indeksu , ale bez indeksu end.

Jest to wyraźniejsze, gdy myślisz o indeksach zasięgu jako o opisie krawędzi między komórkami macierzy. Poniższa ilustracja przedstawia tablicę o długości 9, a liczby pod komórkami są wyrównane do krawędzi i służą do opisu segmentów tablicy. Np. Z ilustracji jasno wynika, że ​​zakres 2..5 to komórki 2,3,4.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │   -- cell indexes, e.g array[3]
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
0   1   2   3   4   5   6   7   8   9   -- segment bounds, e.g. slice(2,5) 
        └───────────┘ 
          range 2..5

Ten model jest zgodny z tym, że długość tablicy jest górną granicą tablicy. Tablica o długości 5 ma komórki 0..5, co oznacza, że ​​jest pięć komórek 0,1,2,3,4. Oznacza to również, że długość segmentu jest górną granicą minus dolna granica, tj. Segment 2..5 ma 5-2 = 3 komórki.

Mając na uwadze ten model podczas iteracji w górę lub w dół, znacznie łatwiej jest uwzględnić lub wykluczyć punkty końcowe. Podczas iteracji w górę musisz uwzględnić punkt początkowy, ale wykluczyć punkt końcowy. Podczas iteracji w dół należy wykluczyć punkt początkowy (górna granica), ale uwzględnić punkt końcowy (dolna granica).

Ponieważ iterujesz w dół w kodzie, musisz dołączyć dolną granicę, 0, więc iteruj podczas j >= 0.

Biorąc to pod uwagę, wybór, aby rightIndexargument reprezentował ostatni indeks w podtablicy, łamie konwencję. Oznacza to, że musisz uwzględnić oba punkty końcowe (0 i prawy indeks) w iteracji. Utrudnia to także przedstawienie pustego segmentu (który jest potrzebny podczas rozpoczynania sortowania). Podczas wstawiania pierwszej wartości musisz użyć -1 jako rightIndex. To wydaje się dość nienaturalne. Bardziej naturalne wydaje się rightIndexwskazanie indeksu po segmencie, więc 0 oznacza pusty segment.

Oczywiście twój kod jest wyjątkowo mylący, ponieważ rozszerza posortowaną podtablicę o jedną, zastępując element natychmiast po początkowo posortowanej podtablicy. Czytasz więc z indeksu j, ale zapisujesz wartość do j + 1. Tutaj powinieneś po prostu wyjaśnić, że j jest pozycją w początkowej podtablicy, przed wstawieniem. Kiedy operacje indeksowania stają się zbyt trudne, pomaga mi to narysować na kartce papieru.

JacquesB
źródło
4
@CodeYogi: Narysowałbym małą tablicę jako siatkę na kawałku papieru, a następnie ręcznie wykonałem iterację pętli ręcznie ołówkiem. Pomaga mi to wyjaśnić, co się faktycznie dzieje, np. Że zakres komórek jest przesunięty w prawo i gdzie wstawiana jest nowa wartość.
JacquesB,
3
„w informatyce istnieją dwie trudne rzeczy: unieważnienie pamięci podręcznej, nazywanie rzeczy i błędy indywidualne”.
Cyfrowa trauma
1
@CodeYogi: Dodano mały schemat pokazujący, o czym mówię.
JacquesB
1
Świetny wgląd, szczególnie, że ostatnie dwa pary są warte przeczytania, zamieszanie wynika również z natury pętli for, nawet znajduję odpowiedni indeks dekrementacji pętli j jeden raz przed zakończeniem, a zatem cofam się o krok.
CodeYogi 22.04.16
1
Bardzo. Doskonały. Odpowiedź. I dodam, że ta konwencja włączania / wyłączania indeksów jest również motywowana wartością myArray.Lengthlub myList.Count- która zawsze jest o jeden większa niż liczony od zera indeks „najbardziej na prawo”. ... Długość wyjaśnienia przeczy praktycznemu i prostemu zastosowaniu tych wyraźnych heurystyk kodowania. Brakuje tłumu TL; DR.
radarbob
5

Wprowadzenie do twojego pytania sprawia, że ​​myślę, że nie nauczyłeś się poprawnie kodować. Każdy, kto programuje w języku imperatywnym przez więcej niż kilka tygodni, powinien naprawdę dobrze po raz pierwszy w ponad 90% przypadków. Być może śpieszysz się, aby rozpocząć kodowanie, zanim wystarczająco dobrze przemyślisz problem.

Sugeruję usunięcie tego niedoboru poprzez (ponowne) nauczenie się, jak pisać pętle - i zaleciłbym kilka godzin pracy nad szeregiem pętli z papierem i ołówkiem. Zrób sobie wolne popołudnie. Następnie poświęć około 45 minut na pracę nad tym tematem, aż naprawdę go zrozumiesz.

To wszystko bardzo dobrze testuje, ale powinieneś testować w oczekiwaniu, że ogólnie uzyskasz prawidłowe pętle (i resztę kodu).

Znak wysokiej wydajności
źródło
4
Nie byłbym tak asertywny w kwestii umiejętności OP. Popełnianie błędów granicznych jest łatwe, szczególnie w stresującym kontekście, takim jak rozmowa rekrutacyjna. Doświadczony programista może również popełniać te błędy, ale oczywiście doświadczony programista unikałby takich błędów przede wszystkim poprzez testowanie.
Arseni Mourzenko
3
@MainMa - Myślę, że chociaż Mark mógł być bardziej wrażliwy, myślę, że ma rację - Występuje stres podczas wywiadu i jest po prostu hakowanie kodu razem bez należytego rozważenia problemu. Sposób, w jaki pytanie zostało sformułowane, wskazuje bardzo mocno na to drugie i jest to coś, co najlepiej można rozwiązać w dłuższej perspektywie, upewniając się, że masz solidne podstawy, a nie hackując IDE
James Snell
@JamesSnell Myślę, że jesteś zbyt pewny siebie. Spójrz na kod i powiedz mi, co sprawia, że ​​myślisz, że jest niedokumentowany? Jeśli widzisz wyraźnie, nie ma mowy o tym, że nie mogłem rozwiązać problemu? Chciałem tylko wiedzieć, jak uniknąć powtórzenia tego samego błędu. Myślę, że wszystkie twoje programy są poprawne za jednym razem.
CodeYogi 17.04.16
4
@CodeYogi Jeśli musisz zrobić „próbę i błąd” i „denerwujesz się” i „popełniasz te same błędy” w kodzie, to są oznaki, że nie zrozumiałeś wystarczająco dobrze swojego problemu przed rozpoczęciem pisania . Nikt nie mówi, że go nie rozumiałeś, ale twój kod mógł być lepiej przemyślany i są znakami, że walczysz, z którego możesz wybrać i uczyć się, czy nie.
James Snell
2
@CodeYogi ... a skoro pytasz, rzadko mam problemy z zapętlaniem się i rozgałęzianiem, ponieważ staram się dobrze zrozumieć, co muszę osiągnąć przed napisaniem kodu, nie jest trudno zrobić coś prostego, na przykład posortowanego klasa tablicowa. Jako programista jedną z najtrudniejszych rzeczy jest przyznać, że jesteś problemem, ale dopóki tego nie zrobisz, nie zaczniesz pisać naprawdę dobrego kodu.
James Snell
3

Być może powinienem dodać trochę mego komentarza:

Jest tylko jeden sposób: lepiej zrozumieć swój problem. Ale to jest tak ogólne, jak twoje pytanie

Chodzi o to

Mimo że moje założenia były prawidłowe po kilku próbach i błędach, ale byłem zbyt sfrustrowany z powodu braku poprawnego modelu obliczeniowego w mojej głowie.

Kiedy czytam trial and error, moje dzwonki alarmowe zaczynają dzwonić. Oczywiście wielu z nas zna stan umysłu, kiedy ktoś chce naprawić mały problem i owinął głowę innymi rzeczami i zaczyna zgadywać w taki czy inny sposób, aby kod seemmógł zrobić, co powinien. Wyłaniają się z tego jakieś hackerskie rozwiązania - a niektóre z nich są genialne ; ale szczerze mówiąc: większość z nich nie jest . Włącznie ze mną, znając ten stan.

Niezależnie od konkretnego problemu zadawałeś pytania, jak poprawić:

1) Test

To powiedzieli inni i nie miałbym nic cennego do dodania

2) Analiza problemu

Trudno jest na to poradzić. Mogę ci dać tylko dwie wskazówki, które prawdopodobnie pomogą ci poprawić swoje umiejętności w tym temacie:

  • oczywisty i najbardziej trywialny jest na dłuższą metę najbardziej skuteczny: rozwiązać wiele problemów. Ćwicząc i powtarzając, rozwijasz sposób myślenia, który pomaga ci w przyszłych zadaniach. Programowanie jest jak każde inne działanie, które można ulepszyć poprzez ciężką pracę

Code Katas to sposób, który może trochę pomóc.

Jak zostać świetnym muzykiem? Pomaga poznać teorię i zrozumieć mechanikę twojego instrumentu. Pomaga mieć talent. Ale ostatecznie wielkość wynika z praktykowania; stosowanie teorii w kółko, za pomocą opinii, aby za każdym razem być lepszym.

Kod Kata

Jedna strona, którą bardzo lubię: Code Wars

Osiągnij mistrzostwo poprzez wyzwanie Popraw swoje umiejętności, trenując z innymi na prawdziwych wyzwaniach związanych z kodem

Są to stosunkowo niewielkie problemy, które pomagają wyostrzyć umiejętności programowania. W Code Wars najbardziej podoba mi się to, że możesz porównać swoje rozwiązanie z jednym z innych .

A może powinieneś zajrzeć na Exercism.io, gdzie uzyskasz informacje zwrotne od społeczności.

  • Druga rada jest prawie równie trywialna: Naucz się rozwiązywać problemy Musisz ćwiczyć się, rozkładając problemy na naprawdę małe problemy. Jeśli powiesz, że masz problemy z pisaniem pętli , popełniasz błąd, że widzisz pętlę jako całą konstrukcję i nie rozkładasz jej na części. Jeśli nauczysz się rozbierać rzeczy krok po kroku , nauczysz się unikać takich błędów.

Wiem - jak mówiłem powyżej, że czasami jesteś w takim stanie - że ciężko jest rozbić „proste” rzeczy na bardziej „martwe proste” zadania; ale bardzo pomaga.

Pamiętam, kiedy po raz pierwszy nauczyłem się profesjonalnego programowania, miałem ogromne problemy z debugowaniem mojego kodu. W czym był problem? Hybris - Błąd nie może znajdować się w takim i takim regionie kodu, ponieważ wiem, że nie może być. A w konsekwencji? Przejrzałem kod zamiast analizować go, którego musiałem się nauczyć - nawet jeśli żmudne było łamanie mojego kodu instrukcji .

3) Opracuj pasek narzędzi

Oprócz znajomości twojego języka i narzędzi - wiem, że są to lśniące rzeczy, o których twórcy myślą w pierwszej kolejności - ucz się Algorytmów (aka czytanie).

Oto dwie książki na początek:

To tak, jakby nauczyć się kilku przepisów, aby rozpocząć gotowanie. Na początku nie wiesz, co robić, więc musisz sprawdzić, jakich wcześniej szefów kuchni przygotowali dla ciebie . To samo dotyczy algortihms. Algorytmy są jak przepisy kulinarne na wspólne posiłki (struktury danych, sortowanie, mieszanie itp.) Jeśli znasz je (przynajmniej staraj się) na pamięć, masz dobry punkt wyjścia.

3a) Zna konstrukty programistyczne

Ten punkt jest pochodną - że tak powiem. Poznaj swój język - i lepiej: wiedz, jakie konstrukcje są możliwe w twoim języku.

Wspólny punkt za złą lub inefficent kod jest czasami, że programista nie zna różnicę między różnymi rodzajami pętli ( for-, while-a do-loops). Wszystkie są w jakiś sposób wymiennie użyteczne; ale w niektórych okolicznościach wybranie innej zapętlonej konstrukcji prowadzi do bardziej eleganckiego kodu.

I jest urządzenie Duffa ...

PS:

w przeciwnym razie twój komentarz nie będzie dobry niż Donal Trump.

Tak, powinniśmy sprawić, by kodowanie znów było świetne!

Nowe motto dla Stackoverflow.

Thomas Junk
źródło
Ach, powiem ci bardzo poważnie. Robię wszystko, o czym wspomniałeś i mogę nawet podać ci mój link na tych stronach. Ale frustruje mnie to, że zamiast uzyskać odpowiedź na moje pytanie, otrzymuję wszelkie możliwe porady dotyczące programowania. Tylko jeden facet wspomniał o pre-postwarunkach do tej pory i doceniam to.
CodeYogi 17.04.16
Z tego, co mówisz, trudno sobie wyobrazić, gdzie jest twój problem. Być może pomaga metafora: dla mnie jest to jak powiedzenie „jak mogę zobaczyć” - oczywistą odpowiedzią jest dla mnie „użyj oczu”, ponieważ widzenie jest dla mnie tak naturalne, że nie mogę sobie wyobrazić, jak się nie widzi. To samo dotyczy twojego pytania.
Thomas Junk
Zgadzam się całkowicie z dzwonkami alarmowymi na temat „prób i błędów”. Myślę, że najlepszym sposobem, aby w pełni nauczyć się sposobu myślenia o rozwiązywaniu problemów, jest uruchamianie algorytmów i kodu za pomocą papieru i ołówka.
Wildcard
Hmm ... dlaczego masz gramatyczne ubytki pod względem gramatycznym wobec kandydata politycznego cytowanego bez kontekstu w środku odpowiedzi na temat programowania?
Wildcard
2

Jeśli dobrze zrozumiałem problem, twoje pytanie brzmi, jak pomyśleć o uzyskaniu pętli od pierwszej próby, a nie jak upewnić się, że twoja pętla jest poprawna (dla której odpowiedź byłaby testowana, jak wyjaśniono w innych odpowiedziach).

Uważam, że dobrym podejściem jest napisanie pierwszej iteracji bez żadnej pętli. Po wykonaniu tej czynności powinieneś zauważyć, co należy zmienić między iteracjami.

Czy to liczba, jak 0 czy 1? Wtedy najprawdopodobniej potrzebujesz fora i bingo, masz również swój start i. Zastanów się, ile razy chcesz uruchomić tę samą rzecz, a także mieć swój stan końcowy.

Jeśli nie wiesz DOKŁADNIE, ile razy będzie on działał, nie potrzebujesz chwili, ale chwilę lub czasu.

Technicznie każda pętla może zostać przetłumaczona na dowolną inną, ale kod jest łatwiejszy do odczytania, jeśli używasz właściwej pętli, więc oto kilka wskazówek:

  1. Jeśli zauważysz, że piszesz if () {...; break;} wewnątrz a, potrzebujesz trochę czasu i już masz warunek

  2. „While” jest być może najczęściej używaną pętlą w dowolnym języku, ale nie powinno imo. Jeśli okaże się, że piszesz bool ok = True; while (check) {zrób coś i mam nadzieję, że w pewnym momencie coś zmienisz}; wtedy nie potrzebujesz trochę czasu, ale trochę czasu, ponieważ oznacza to, że masz wszystko, czego potrzebujesz, aby uruchomić pierwszą iterację.

Teraz trochę kontekstu ... Kiedy po raz pierwszy nauczyłem się programować (Pascal), nie mówiłem po angielsku. Dla mnie „for” i „while” nie miało większego sensu, ale słowo kluczowe „repeat” (do while in C) jest prawie takie samo w moim języku ojczystym, więc użyłbym tego do wszystkiego. Moim zdaniem powtarzanie (czynność do momentu) jest najbardziej naturalną pętlą, ponieważ prawie zawsze chcesz coś zrobić, a potem chcesz, aby było to zrobione ponownie, i znowu, aż do osiągnięcia celu. „For” to tylko skrót, który daje iterator i dziwnie umieszcza warunek na początku kodu, nawet jeśli prawie zawsze chcesz coś zrobić, dopóki coś się nie stanie. Ponadto while jest tylko skrótem do if () {do while ()}. Skróty są przydatne na później,

Andrei
źródło
2

Dam bardziej szczegółowy przykład użycia warunków przed / po i niezmienników do opracowania poprawnej pętli. Razem takie twierdzenia nazywane są specyfikacją lub umową.

Nie sugeruję, abyś próbował to zrobić dla każdej pętli. Ale mam nadzieję, że przyda ci się proces myślowy.

W tym celu przełożę twoją metodę na narzędzie o nazwie Microsoft Dafny , które ma na celu udowodnienie poprawności takich specyfikacji. Sprawdza także zakończenie każdej pętli. Pamiętaj, że Dafny nie ma forpętli, więc whilezamiast tego musiałem użyć pętli.

Na koniec pokażę, jak wykorzystać takie specyfikacje do zaprojektowania, prawdopodobnie, nieco prostszej wersji pętli. Ta prostsza wersja pętli faktycznie ma warunek pętli j > 0i przypisanie array[j] = value- tak jak początkowa intuicja.

Dafny udowodni nam, że obie pętle są prawidłowe i robią to samo.

W oparciu o moje doświadczenie przedstawię ogólne twierdzenie o tym, jak napisać prawidłową pętlę wsteczną, która być może pomoże ci w obliczu takiej sytuacji w przyszłości.

Część pierwsza - Pisanie specyfikacji dla metody

Pierwszym wyzwaniem, przed którym stoimy, jest określenie, co właściwie ma zrobić ta metoda. W tym celu zaprojektowałem warunki wstępne i końcowe, które określają zachowanie metody. Aby uczynić specyfikację bardziej dokładną, ulepszyłem metodę, aby zwracała indeks, w którym valuezostała wstawiona.

method insert(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  // the method will modify the array
  modifies arr
  // the array will not be null
  requires arr != null
  // the right index is within the bounds of the array
  // but not the last item
  requires 0 <= rightIndex < arr.Length - 1
  // value will be inserted into the array at index
  ensures arr[index] == value 
  // index is within the bounds of the array
  ensures 0 <= index <= rightIndex + 1
  // the array to the left of index is not modified
  ensures arr[..index] == old(arr[..index])
  // the array to the right of index, up to right index is
  // shifted to the right by one place
  ensures arr[index+1..rightIndex+2] == old(arr[index..rightIndex+1])
  // the array to the right of rightIndex+1 is not modified
  ensures arr[rightIndex+2..] == old(arr[rightIndex+2..])

Ta specyfikacja w pełni oddaje zachowanie metody. Moje główne spostrzeżenie na temat tej specyfikacji jest takie, że uproszczenie byłoby, gdyby procedura przeszła wartość rightIndex+1zamiast rightIndex. Ale ponieważ nie widzę, skąd ta metoda jest wywoływana, nie wiem, jaki wpływ ta zmiana miałaby na resztę programu.

Część druga - określenie niezmiennika pętli

Teraz mamy specyfikację zachowania metody, musimy dodać specyfikację zachowania pętli, która przekona Dafny'ego, że wykonanie pętli zostanie zakończone i spowoduje pożądany stan końcowy array.

Oto twoja oryginalna pętla, przetłumaczona na składnię Dafny z dodanymi niezmiennikami pętli. Zmieniłem go również, aby zwrócić indeks, do którego wstawiono wartość.

{
    // take a copy of the initial array, so we can refer to it later
    // ghost variables do not affect program execution, they are just
    // for specification
    ghost var initialArr := arr[..];


    var j := rightIndex;
    while(j >= 0 && arr[j] > value)
       // the loop always decreases j, so it will terminate
       decreases j
       // j remains within the loop index off-by-one
       invariant -1 <= j < arr.Length
       // the right side of the array is not modified
       invariant arr[rightIndex+2..] == initialArr[rightIndex+2..]
       // the part of the array looked at by the loop so far is
       // shifted by one place to the right
       invariant arr[j+2..rightIndex+2] == initialArr[j+1..rightIndex+1]
       // the part of the array not looked at yet is not modified
       invariant arr[..j+1] == initialArr[..j+1] 
    {
        arr[j + 1] := arr[j];
        j := j-1;
    }   
    arr[j + 1] := value;
    return j+1; // return the position of the insert
}

Sprawdza to w Dafny. Możesz to zobaczyć samodzielnie, klikając ten link . Więc twoja pętla poprawnie implementuje specyfikację metody, którą napisałem w części pierwszej. Musisz zdecydować, czy ta specyfikacja metody jest rzeczywiście zachowaniem, które chciałeś.

Pamiętaj, że Dafny przedstawia tutaj dowód poprawności. Jest to znacznie silniejsza gwarancja poprawności, niż można ją uzyskać testując.

Część trzecia - prostsza pętla

Teraz, gdy mamy specyfikację metody, która przechwytuje zachowanie pętli. Możemy bezpiecznie modyfikować implementację pętli zachowując pewność, że nie zmieniliśmy zachowania pętli.

Zmodyfikowałem pętlę, aby pasowała do twoich pierwotnych intuicji dotyczących stanu pętli i końcowej wartości j. Twierdziłbym, że ta pętla jest prostsza niż pętla opisana w pytaniu. Częściej jest w stanie używać jniż j+1.

  1. Rozpocznij j o rightIndex+1

  2. Zmień warunek pętli na j > 0 && arr[j-1] > value

  3. Zmień przydział na arr[j] := value

  4. Zmniejsz licznik pętli na końcu pętli, a nie na początku

Oto kod. Zauważ, że niezmienniki pętli są teraz nieco łatwiejsze do napisania:

method insert2(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  modifies arr
  requires arr != null
  requires 0 <= rightIndex < arr.Length - 1
  ensures 0 <= index <= rightIndex + 1
  ensures arr[..index] == old(arr[..index])
  ensures arr[index] == value 
  ensures arr[index+1..rightIndex+2] == old(arr[index..rightIndex+1])
  ensures arr[rightIndex+2..] == old(arr[rightIndex+2..])
{
    ghost var initialArr := arr[..];
    var j := rightIndex+1;
    while(j > 0 && arr[j-1] > value)
       decreases j
       invariant 0 <= j <= arr.Length
       invariant arr[rightIndex+2..] == initialArr[rightIndex+2..]
       invariant arr[j+1..rightIndex+2] == initialArr[j..rightIndex+1]
       invariant arr[..j] == initialArr[..j] 
    {
        j := j-1;
        arr[j + 1] := arr[j];
    }   
    arr[j] := value;
    return j;
}

Część czwarta - porady dotyczące zapętlania wstecznego

Po napisaniu i sprawdzeniu poprawności wielu pętli przez dość kilka lat, mam następującą ogólną radę na temat zapętlania wstecz.

Prawie zawsze łatwiej jest pomyśleć i napisać pętlę wsteczną (dekrementującą), jeśli dekrementacja jest wykonywana na początku pętli, a nie na jej końcu.

Niestety forkonstrukcja pętli w wielu językach sprawia, że ​​jest to trudne.

Podejrzewam (ale nie mogę udowodnić), że ta złożoność spowodowała różnicę w twojej intuicji na temat tego, czym powinna być pętla i jaka powinna być. Jesteś przyzwyczajony do myślenia o pętlach do przodu (zwiększających). Gdy chcesz napisać pętlę wsteczną (zmniejszającą), próbuj utworzyć pętlę, próbując odwrócić kolejność, w jakiej dzieje się w pętli przewijającej (zwiększającej). Ale ze względu na sposób działania forkonstrukcji zaniedbałeś odwrócenie kolejności przypisania i aktualizacji zmiennej pętli - co jest potrzebne do prawdziwego odwrócenia kolejności operacji między pętlą wsteczną i następną.

Część piąta - bonus

Dla kompletności, oto kod, który otrzymujesz, jeśli przejdziesz rightIndex+1do metody, a nie rightIndex. Zmiany te eliminują wszystkie +2przesunięcia, które w innym przypadku byłyby wymagane, aby pomyśleć o poprawności pętli.

method insert3(arr:array<int>, rightIndex:int, value:int) returns (index:int)
  modifies arr
  requires arr != null
  requires 1 <= rightIndex < arr.Length 
  ensures 0 <= index <= rightIndex
  ensures arr[..index] == old(arr[..index])
  ensures arr[index] == value 
  ensures arr[index+1..rightIndex+1] == old(arr[index..rightIndex])
  ensures arr[rightIndex+1..] == old(arr[rightIndex+1..])
{
    ghost var initialArr := arr[..];
    var j := rightIndex;
    while(j > 0 && arr[j-1] > value)
       decreases j
       invariant 0 <= j <= arr.Length
       invariant arr[rightIndex+1..] == initialArr[rightIndex+1..]
       invariant arr[j+1..rightIndex+1] == initialArr[j..rightIndex]
       invariant arr[..j] == initialArr[..j] 
    {
        j := j-1;
        arr[j + 1] := arr[j];
    }   
    arr[j] := value;
    return j;
}
Flamingpenguin
źródło
2
Byłbym bardzo wdzięczny za komentarz, jeśli zagłosujesz
flamingpenguin
2

Pierwsze prawo to łatwo i płynnie to kwestia doświadczenia. Mimo że język nie pozwala wyrazić go bezpośrednio lub używasz bardziej złożonego przypadku, niż jest w stanie obsłużyć prosta wbudowana rzecz, Twoim zdaniem jest wyższy poziom, np. „Odwiedzaj każdy element raz w poważnej kolejności” i bardziej doświadczony programista natychmiast przekłada to na właściwe szczegóły, ponieważ robił to wiele razy.

Nawet wtedy, w bardziej skomplikowanych przypadkach, łatwo się pomylić, ponieważ to, co piszesz, zazwyczaj nie jest zwykłą powszechną rzeczą. Dzięki bardziej nowoczesnym językom i bibliotekom nie piszesz łatwej rzeczy, ponieważ istnieje konstrukt lub wezwanie do tego. W C ++ współczesna mantra to „używaj algorytmów zamiast pisać kod”.

Tak więc, aby upewnić się, że jest to właściwe, szczególnie w przypadku tego rodzaju rzeczy, należy spojrzeć na warunki brzegowe . Prześledź kod w twojej głowie dla kilku przypadków na krawędziach, gdzie rzeczy się zmieniają. Jeśli index == array-max, co się stanie? Co max-1? Jeśli kod źle skręci, będzie na jednej z tych granic. Niektóre pętle muszą się martwić o pierwszy lub ostatni element, a także o to, czy konstrukcja pętli prawidłowo dopasowuje granice; np. jeśli odwołujesz się a[I]i a[I-1]co dzieje się, kiedy Ijest minimalna wartość?

Spójrz także na przypadki, w których liczba (poprawnych) iteracji jest ekstremalna: jeśli granice się spełniają, a będziesz mieć 0 iteracji, czy to po prostu zadziała bez specjalnego przypadku? A co z tylko 1 iteracją, gdzie najniższa granica jest jednocześnie najwyższą granicą?

Badanie przypadków na krawędziach (po obu stronach każdej krawędzi) jest tym, co powinieneś zrobić przy pisaniu pętli i co powinieneś zrobić w recenzjach kodu.

JDługosz
źródło
1

Spróbuję już unikać omawianych tematów.

Jakie są narzędzia / modele mentalne, aby uniknąć takich błędów?

Przybory

Dla mnie największym narzędziem do lepszego pisania fori whilepętli jest w ogóle nie pisanie forani whilepętli.

Większość współczesnych języków próbuje rozwiązać ten problem w taki czy inny sposób. Na przykład Java, która Iteratorod samego początku była nieco niezgrabna w użyciu, wprowadziła skróconą składnię, aby łatwiej z nich korzystać w późniejszym wydaniu. C # też je ma itp.

My obecnie preferowane język, Ruby, podjął na podejściu funkcjonalnym ( .each, .mapetc.) w pełnym wymiarze przodu. To jest bardzo potężne. Właśnie zrobiłem szybkie policzenie w bazie kodu Ruby, nad którą pracuję: w około 10.000 linii kodu jest zero fori około 5 while.

Gdybym był zmuszony wybrać nowy język, szukanie takich funkcjonalnych / opartych na danych pętli byłoby bardzo wysoko na liście priorytetów.

Modele psychologiczne

Pamiętaj, że whilejest to najgorsze minimum abstrakcji, jakie możesz uzyskać, zaledwie jeden krok powyżej goto. Moim zdaniem forsprawia , że jest jeszcze gorzej, a nie lepiej, ponieważ ściśle łączy wszystkie trzy części pętli.

Tak więc, jeśli jestem w środowisku, w którym forjest używany, to cholernie upewniam się, że wszystkie 3 części są bardzo proste i zawsze takie same. Oznacza to, że napiszę

limit = ...;
for (idx = 0; idx < limit; idx++) { 

Ale nic bardziej złożonego. Może czasem będę miał odliczanie, ale zrobię co w mojej mocy, aby tego uniknąć.

Jeśli używam while, trzymam się z daleka od zawiłych wewnętrznych shenanniganów obejmujących stan pętli. Test w środku while(...)będzie tak prosty, jak to możliwe, i unikam breaknajlepiej, jak potrafię. Również pętla będzie krótka (zlicza wiersze kodu) i wszelkie większe ilości kodu zostaną uwzględnione.

Zwłaszcza jeśli rzeczywisty warunek while jest złożony, użyję „zmiennej warunkowej”, która jest bardzo łatwa do wykrycia, i nie umieszczam warunku w whilesamej instrukcji:

repeat = true;
while (repeat) {
   repeat = false; 
   ...
   if (complex stuff...) {
      repeat = true;
      ... other complex stuff ...
   }
}

(Lub coś w tym rodzaju, oczywiście we właściwej mierze).

To daje bardzo łatwy model mentalny, który brzmi: „ta zmienna działa monotonicznie od 0 do 10” lub „ta pętla działa, dopóki zmienna nie jest fałszywa / prawdziwa”. Wydaje się, że większość mózgów jest w stanie dobrze poradzić sobie z tym poziomem abstrakcji.

Mam nadzieję, że to pomaga.

AnoE
źródło
1

Zwłaszcza pętle zwrotne mogą być trudne do uzasadnienia, ponieważ wiele naszych języków programowania jest tendencyjnych do iteracji do przodu, zarówno we wspólnej składni dla pętli, jak i przy użyciu półotwartych przedziałów zerowych. Nie twierdzę, że to źle, że języki dokonywały tych wyborów; Mówię tylko, że te wybory komplikują myślenie o pętlach zwrotnych.

Ogólnie pamiętaj, że pętla for to po prostu cukier składniowy zbudowany wokół pętli while:

// pseudo-code!
for (init; cond; step) { body; }

jest równa:

// pseudo-code!
init;
while (cond) {
  body;
  step;
}

(ewentualnie z dodatkową warstwą zakresu, aby zmienne zadeklarowane w kroku inicjalizacji były lokalne dla pętli).

Jest to w porządku dla wielu rodzajów pętli, ale krok ostatni jest niewygodny, gdy idziesz do tyłu. Podczas pracy wstecz uważam, że łatwiej jest rozpocząć indeks pętli od wartości po tej, którą chcę i przenieść stepczęść na górę pętli, jak poniżej:

auto i = v.size();  // init
while (i > 0) {  // simpler condition because i is one after
    --i;  // step before the body
    body;  // in body, i means what you'd expect
}

lub jako pętla for:

for (i = v.size(); i > 0; ) {
    --i;  // step
    body;
}

Może to wydawać się denerwujące, ponieważ wyrażenie kroku znajduje się w treści, a nie w nagłówku. To niefortunny efekt uboczny nieodłącznego uprzedzenia w składni pętli for. Z tego powodu niektórzy będą argumentować, że zamiast tego to robisz:

for (i = v.size() - 1; i >= 0; --i) {
    body;
}

Ale to katastrofa, jeśli twoja zmienna indeksu jest typu bez znaku (jak może być w C lub C ++).

Mając to na uwadze, napiszmy swoją funkcję wstawiania.

  1. Ponieważ będziemy pracować wstecz, pozwolimy, aby indeks pętli był wpisem za „bieżącym” gniazdem tablicy. Zaprojektowałbym funkcję, aby zamiast ostatniego indeksu przyjmowała rozmiar liczby całkowitej, a nie indeks, ponieważ półotwarte zakresy są naturalnym sposobem reprezentowania zakresów w większości języków programowania i ponieważ daje nam to możliwość reprezentowania pustej tablicy bez uciekania się do ucieczki do magicznej wartości, takiej jak -1.

    function insert(array, size, value) {
      var j = size;
    
  2. Chociaż nowa wartość jest mniejsza niż poprzedni element, przesuwaj ją. Oczywiście, poprzedni element może być sprawdzane tylko wtedy, gdy jest wcześniejsza elementem, więc najpierw trzeba sprawdzić, czy nie jesteśmy na samym początku:

      while (j != 0 && value < array[j - 1]) {
        --j;  // now j become current
        array[j + 1] = array[j];
      }
    
  3. To pozostawia miejsce, w jktórym chcemy nowej wartości.

      array[j] = value; 
    };
    

Programowanie pereł Jona Bentleya daje bardzo jasne wyjaśnienie rodzaju wstawiania (i innych algorytmów), które mogą pomóc w budowaniu modeli mentalnych dla tego rodzaju problemów.

Adrian McCarthy
źródło
0

Czy jesteś po prostu zdezorientowany tym, co forfaktycznie robi pętla i mechaniką jej działania?

for(initialization; condition; increment*)
{
    body
}
  1. Najpierw wykonywana jest inicjalizacja
  2. Następnie sprawdzany jest warunek
  3. Jeśli warunek jest spełniony, ciało jest uruchamiane raz. Jeśli nie, to masz # 6
  4. Kod przyrostowy jest wykonywany
  5. Idź do 2
  6. Koniec pętli

Przydatne może być przepisanie tego kodu przy użyciu innej konstrukcji. Oto to samo przy użyciu pętli while:

initialization
while(condition)
{
    body
    increment
}

Oto kilka innych sugestii:

  • Czy możesz użyć konstrukcji języka innego niż pętla foreach? Dba o to warunek i krok przyrostu dla Ciebie.
  • Czy możesz użyć funkcji mapy lub filtra? Niektóre języki mają funkcje o tych nazwach, które wewnętrznie zapętlają kolekcję. Po prostu dostarczasz kolekcję i ciało.
  • Naprawdę powinieneś poświęcić więcej czasu na zapoznanie się z forpętlami. Będziesz ich używać cały czas. Sugeruję przejście przez pętlę for w debuggerze, aby zobaczyć, jak się wykonuje.

* Zauważ, że chociaż używam terminu „przyrost”, to tylko część kodu znajduje się po treści i przed sprawdzeniem warunku. Może to być spadek lub wcale.

user2023861
źródło
1
dlaczego głosowanie negatywne?
user2023861 18.04.2016
0

Próba dodatkowego wglądu

W przypadku nietrywialnych algorytmów z pętlami możesz wypróbować następującą metodę:

  1. Utwórz stałą tablicę z 4 pozycjami i wstaw niektóre wartości, aby zasymulować problem;
  2. Napisz swój algorytm, aby rozwiązać dany problem , bez żadnej pętli i z zakodowanymi indeksami ;
  3. Następnie zamień na stałe indeksowanie w kodzie na pewną zmienną ilub j, i zwiększaj / zmniejszaj te zmienne, jeśli to konieczne (ale nadal bez żadnej pętli);
  4. Przepisz swój kod i umieść powtarzalne bloki w pętli , spełniając warunki przed i po;
  5. [ opcjonalnie ] przepisz pętlę tak, aby była w żądanej formie (for / while / do while);
  6. Najważniejsze jest prawidłowe napisanie algorytmu; po tym dokonujesz refaktoryzacji i optymalizujesz kod / pętle, jeśli to konieczne (ale może to sprawić, że kod nie będzie już trywialny dla czytelnika)

Twój problem

//TODO: Insert the given value in proper position in the sorted subarray
function insert(array, rightIndex, value) { ... };

Napisz treść pętli ręcznie wiele razy

Użyjmy stałej tablicy z 4 pozycjami i spróbujmy napisać algorytm ręcznie, bez pętli:

           //0 1 2 3
var array = [2,5,9,1]; //array sorted from index 0 to 2
var leftIndex = 0;
var rightIndex = 2;
var value = array[3]; //placing the last value within the array in the proper position

//starting here as 2 == rightIndex

if (array[2] > value) {
    array[3] = array[2];
} else {
    array[3] = value;
    return; //found proper position, no need to proceed;
}

if (array[1] > value) {
    array[2] = array[1];
} else {
    array[2] = value;
    return; //found proper position, no need to proceed;
}

if (array[0] > value) {
    array[1] = array[0];
} else {
    array[1] = value;
    return; //found proper position, no need to proceed;
}

array[0] = value; //achieved beginning of the array

//stopping here because there 0 == leftIndex

Przepisz, usuwając zakodowane wartości

//consider going from 2 to 0, going from "rightIndex" to "leftIndex"

var i = rightIndex //starting here as 2 == rightIndex

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

if (array[i] > value) {
    array[i+1] = array[i];
} else {
    array[i+1] = value;
    return; //found proper position, no need to proceed;
}

i--;
if (i < leftIndex) {
    array[i+1] = value; //achieved beginning of the array
    return;
}

//stopping here because there 0 == leftIndex

Przetłumacz na pętlę

Z while:

var i = rightIndex; //starting in rightIndex

while (true) {
    if (array[i] > value) { //refactor: this can go in the while clause
        array[i+1] = array[i];
    } else {
        array[i+1] = value;
        break; //found proper position, no need to proceed;
    }

    i--;
    if (i < leftIndex) { //refactor: this can go (inverted) in the while clause
        array[i+1] = value; //achieved beginning of the array
        break;
    }
}

Refaktoryzuj / przepisz / zoptymalizuj pętlę tak, jak chcesz:

Z while:

var i = rightIndex; //starting in rightIndex

while ((array[i] > value) && (i >= leftIndex)) {
    array[i+1] = array[i];
    i--;
}

array[i+1] = value; //found proper position, or achieved beginning of the array

z for:

for (var i = rightIndex; (array[i] > value) && (i >= leftIndex); i--) {
    array[i+1] = array[i];
}

array[i+1] = value; //found proper position, or achieved beginning of the array

PS: kod zakłada, że ​​dane wejściowe są prawidłowe, a tablica nie zawiera powtórzeń;

Emerson Cardoso
źródło
-1

Dlatego unikałbym pisania pętli, które działają na surowych indeksach, na rzecz bardziej abstrakcyjnych operacji, gdy tylko jest to możliwe.

W takim przypadku zrobiłbym coś takiego (w pseudo kodzie):

array = array[:(rightIndex - 1)] + value + array[rightIndex:]
Alexander
źródło
-3

W twoim przykładzie ciało pętli jest dość oczywiste. I jest całkiem oczywiste, że jakiś element należy zmienić na samym końcu. Więc piszesz kod, ale bez początku pętli, warunku końcowego i końcowego przypisania.

Następnie odchodzisz od kodu i dowiadujesz się, jaki jest pierwszy ruch, który należy wykonać. Zmieniasz początek pętli, aby pierwszy ruch był poprawny. Znowu odchodzisz od kodu i dowiadujesz się, jaki jest ostatni ruch, który należy wykonać. Zmieniasz warunek końcowy, aby ostatni ruch był poprawny. Na koniec odejdziesz od kodu i zastanawiasz się, jakie musi być ostateczne zadanie, i odpowiednio go naprawiasz.

gnasher729
źródło
1
Czy możesz podać przykład?
CodeYogi,
OP miał przykład.
gnasher729 18.04.16
2
Co masz na myśli? Jestem OP.
CodeYogi,