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:
- Zamiast j> = 0 zachowałem j> 0.
- 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?
programming-practices
loops
CodeYogi
źródło
źródło
j >= 0
to pomyłka? Byłbym bardziej ostrożny wobec tego, że uzyskujesz dostęparray[j]
iarray[j + 1]
bez uprzedniej kontroliarray.length > (j + 1)
.Array.prototype
przykładzie JS). Zapobiega to napotkaniu warunków brzegowych, ponieważ coś takiegomap
dział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 .Odpowiedzi:
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
rightIndex
0 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.
i
jest dobrą nazwą dla indeksu w ładnej ciasnej pętli w małym zakresie, co czyni go oczywistym. Jeślii
życie wystarcza na tyle długo, aby rozłożyć się po linii z innymi pomysłami i nazwami, które można pomylić,i
nadszedł 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ę, cobreak
icontinue
zrobić, jeśli je masz. Poznaj różnicę międzyc++
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 jakArrays.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 ...
źródło
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:
I sprawdź, co mamy:
array[0..rightIndex]
jest posortowanyarray[0..rightIndex+1]
jest posortowany0 <= j <= rightIndex
ale 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
.array[0..rightIndex+1]
jest sortowanyMożesz więc najpierw napisać
is_sorted
funkcję, a takżemin
funkcję działającą na wycinku tablicy, a następnie potwierdzić:Istnieje również fakt, że stan pętli jest nieco skomplikowany; możesz to ułatwić sobie, dzieląc rzeczy:
Teraz pętla jest prosta (
j
przechodzi odrightIndex
do0
).Wreszcie, teraz należy to przetestować:
rightIndex == 0
,rightIndex == array.size - 2
)value
byciu mniejszymarray[0]
lub większym niżarray[rightIndex]
value
równymarray[0]
,array[rightIndex]
lub jakimś średnim indeksieNie 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.
źródło
0 <= j <= rightIndex
lubarray[j] <= value
, byłoby to po prostu powtórzyć kod. Z drugiej stronyis_sorted
przynosi nową gwarancję, dlatego jest cenna. Następnie do tego służą testy. Jeśli zadzwoniszinsert([0, 1, 2], 2, 3)
do swojej funkcji, a wynik nie[0, 1, 2, 3]
zostanie znaleziony, to znajdziesz błąd.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.insert()
tak, aby działało, kopiując ze starej tablicy na nową. Można to zrobić bez zepsucia innychassert
. Ale nie ten ostatni. Pokazuje tylko, jak dobrzeassert
zostały zaprojektowane Twoje inne .Użyj testu jednostkowego / TDD
Jeśli naprawdę potrzebujesz dostępu do sekwencji za pośrednictwem
for
pę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ć?
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.
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.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ą
if
instrukcji lub wywołania ulubionej metody frameworka.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
foreach
można go użyć zamiastfor
, 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 tylkofor ... in ...
.W języku C # LINQ jest szczególnie wygodny podczas pracy z sekwencjami.
jest znacznie bardziej czytelny i mniej podatny na błędy w porównaniu do swojego
for
wariantu:źródło
for(;;)
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.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:
lub
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?
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ść.
źródło
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. Alefor (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ć jakowhile
pętlę, chyba że starałem się, abyi
mieć 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, żewhile()
wersja kończy się z i == -1 po pętli (jeśli trwa), zamiast i = = 0> 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.i-- > 0
, spróbuj klasycznego żartui --> 0
!Jest bardzo interesującym punktem tego pytania i wygenerowało następujący komentarz:
... 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: -
Istnieje kilka innych problemów związanych z wydajnością i projektem kodu ...
SortedList<t>
w C #)?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.
źródło
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
foreach
lubmap
cał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 indeksustart
do indeksu , ale bez indeksuend
.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.
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
rightIndex
argument 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ęrightIndex
wskazanie 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.
źródło
myArray.Length
lubmyList.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.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).
źródło
Być może powinienem dodać trochę mego komentarza:
Chodzi o to
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 kodseem
mó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:
Code Katas to sposób, który może trochę pomóc.
Kod Kata
Jedna strona, którą bardzo lubię: Code Wars
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.
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-
ado
-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:
Tak, powinniśmy sprawić, by kodowanie znów było świetne!
Nowe motto dla Stackoverflow.
źródło
pre-post
warunkach do tej pory i doceniam to.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:
Jeśli zauważysz, że piszesz if () {...; break;} wewnątrz a, potrzebujesz trochę czasu i już masz warunek
„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,
źródło
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
for
pętli, więcwhile
zamiast 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 > 0
i przypisaniearray[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
value
została wstawiona.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+1
zamiastrightIndex
. 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ść.
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ćj
niżj+1
.Rozpocznij j o
rightIndex+1
Zmień warunek pętli na
j > 0 && arr[j-1] > value
Zmień przydział na
arr[j] := value
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:
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
for
konstrukcja 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
for
konstrukcji 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+1
do metody, a nierightIndex
. Zmiany te eliminują wszystkie+2
przesunięcia, które w innym przypadku byłyby wymagane, aby pomyśleć o poprawności pętli.źródło
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? Comax-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]
ia[I-1]
co dzieje się, kiedyI
jest 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.
źródło
Spróbuję już unikać omawianych tematów.
Przybory
Dla mnie największym narzędziem do lepszego pisania
for
iwhile
pętli jest w ogóle nie pisaniefor
aniwhile
pę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
Iterator
od 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
,.map
etc.) 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 zerofor
i około 5while
.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
while
jest to najgorsze minimum abstrakcji, jakie możesz uzyskać, zaledwie jeden krok powyżejgoto
. Moim zdaniemfor
sprawia , ż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
for
jest używany, to cholernie upewniam się, że wszystkie 3 części są bardzo proste i zawsze takie same. Oznacza to, że napiszę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 środkuwhile(...)
będzie tak prosty, jak to możliwe, i unikambreak
najlepiej, 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
while
samej instrukcji:(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.
źródło
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:
jest równa:
(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ść
step
część na górę pętli, jak poniżej:lub jako pętla for:
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:
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.
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.
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:
To pozostawia miejsce, w
j
którym chcemy nowej wartości.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.
źródło
Czy jesteś po prostu zdezorientowany tym, co
for
faktycznie robi pętla i mechaniką jej działania?Przydatne może być przepisanie tego kodu przy użyciu innej konstrukcji. Oto to samo przy użyciu pętli while:
Oto kilka innych sugestii:
for
pę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.
źródło
Próba dodatkowego wglądu
W przypadku nietrywialnych algorytmów z pętlami możesz wypróbować następującą metodę:
i
lubj
, i zwiększaj / zmniejszaj te zmienne, jeśli to konieczne (ale nadal bez żadnej pętli);Twój problem
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:
Przepisz, usuwając zakodowane wartości
Przetłumacz na pętlę
Z
while
:Refaktoryzuj / przepisz / zoptymalizuj pętlę tak, jak chcesz:
Z
while
:z
for
:PS: kod zakłada, że dane wejściowe są prawidłowe, a tablica nie zawiera powtórzeń;
źródło
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):
źródło
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.
źródło