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?

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 ...

Podczas programowania warto pomyśleć o:

• warunki wstępne
• warunki końcowe
• warianty
• i niezmienniki ( pętli lub typów )

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.

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;
}

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ść.

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.

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.

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).

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:

• Wprowadzenie do algortihms

• Algorytmy

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.

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,

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;
}

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.

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.

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.

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.

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ń;

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:]

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.