Przeprosiny

uncle bob label image

Poniższy tekst jest luźnym tłumaczeniem wpisu Roberta Cecila "Wujka Boba" Martina z dnia 11 maja 2014 ze strony:

Będącego przeprosinami za tytuł starej wersji wpisu bloga ze strony:


Pierwsza wersja tego wpisu z bloga była nazwana Frameworkowa Chłosta. Spróbowałem porównać kod, który wykorzystuje jakiś framework do konkubin w haremie. Myślałem, że moje komentarze są sprytne i śmieszne; ale wiele ludzi uznało je za obraźliwe.
Szczerze przepraszam za tę obrazę, nie było to zamierzone. Złamałem prawo Dona Normana:
Jeśli myślisz, że coś jest sprytne i wyrafinowane, uważaj, to jest najprawdopodobniej twój brak umiaru.
Spróbuję uniknąć takich błędów w przyszłości. Doceniam rozmowę o nich i mam nadzieję, że będzie ona kontynuowana konstruktywnie.
Pozwólcie, że ujmę to w ten sposób. Mój oryginalny wpis naraził kobiety na zestaw naprawdę kiepskich żartów. Ani to nie było moim zamierzeniem. Ani nie zauważyłem, że to zrobiłem. Wskazano mi to później; i zgodziłem się z tym i przeprosiłem. Wierzę, że postąpiłem słusznie.
Wskazanie, że stałeś/aś się obiektem bardzo słabych żartów jest rzeczą honorową. Nie ma nic złego w tym, że wstałeś/aś i powiedziałeś/aś: "Nie chcę być traktowany/a w ten sposób".
Mam 50`000 followersów na Twitterze. Jeśli niezamierzenie popełnię głupi żart i nie poprawię go, inni mogą zadecydować, aby mnie naśladować. Nie chcę tego.
Więc do tych, którzy uważają, że ugiąłem się pod jakimś rodzajem presji, mówię: nie macie racji. Poprawiłem mój wpis, bo się myliłem.


Powyższy tekst jest luźnym tłumaczeniem wpisu Roberta Cecila "Wujka Boba" Martina z dnia 11 maja 2014 ze strony:

Będącego przeprosinami za tytuł starej wersji wpisu bloga ze strony:


Związani Z Frameworkiem[2]

uncle bob label image
Frameworki to potężne narzędzia. Bez nich bylibyśmy zgubieni. Ale istnieje koszt używania frameworków.

Poniższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina z dnia 11 maja 2014 ze strony:


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.


Pomyśl o Rails, czy Springu, czy JSF czy Hibernate. Pomyśl o tym, jak pisałbyś systemy webowe bez pomocy tych frameworków. To wyobrażenie jest przygnębiające. Byłoby wtedy za dużo małych, upierdliwych szczegółów, z którymi musiałbyś sobie radzić. To byłoby jak zbudowanie obwodu pamięci mnemonicznej przy użyciu kamiennych noży i niedźwiedziej skóry[1].
A więc radośnie łączymy nasz kod ściśle z frameworkami w oczekiwaniu tych wszystkich obiecanych zysków. Popełniamy przy tym błąd, który popełniło już tak wielu programistów przed nami. Związujemy się z frameworkiem.
Użycie frameworku wymaga znaczącego zaangażowania. Akceptując framework w swoim kodzie, tracisz kontrolę nad szczegółami, którymi zarządza framework. Oczywiście wydaje się to być dobre; i zwykle jest. Jednakże pułapka czyha tuż za rogiem; i jest ciężko spostrzec ją w porę. Zanim się zorientujesz, jesteś zaangażowany we wszelkiego rodzaju nienaturalne działania, dziedzicząc z klas bazowych frameworku, rezygnując z coraz większej ilości kontroli przepływu sterowania, kłaniając się coraz głębiej konwencjom frameworku, jego dziwactwom i ekscentryzmom.
I pomimo Twojego ogromnego zaangażowania zrobionego w kierunku frameworku, framework nie odwzajemnił Ci się żadnym zaangażowaniem w Twoim kierunku. Framework łatwo ewoluuje w każdym kierunku, jaki tylko zadowala jego autora. A kiedy to robi, zdajesz sobie sprawę, że będziesz musiał podążać za nim grzecznie, jak wierny szczeniak.
Przywiązywanie się do frameworku zachodzi zbyt często wśród członków zespołów programistycznych. Zaczynają z dzikim entuzjazmem i chętnie wiążą swój kod z frameworkiem, tylko po to, żeby dużo później, wraz z rozwojem projektu, przekonać się, że framework staje im na drodze.
To nie powinno być zaskakujące. Frameworki są pisane przez ludzi do rozwiązania konkretnych problemów, które tylko ci ludzie mają. Te problemy mogą być Twoje, ale one nie są Twoje. Ty masz inne problemy. W momencie, gdy Twoje problemy pokrywają się, framework może być niesamowicie pomocny. W momencie, gdy Twoje problemy są inne, framework może być ogromnym utrudnieniem.

Autorzy Frameworków

Frameworki są pisane przez ludzi, a ludzie mają swoje własne motywy. Jednym z takich motywów może być sprawienie, abyś używał ich frameworku. Jako autor frameworków w przeszłości, mogę Ci powiedzieć, że im więcej ludzi używa twoich frameworków, tym masz o sobie lepsze mniemanie. Duża część mojego dowartościowania samego siebie była związana z akceptacją moich frameworków przez innych ludzi.
Tutaj nie chcę wchodzić zbyt głęboko w psychoanalizę autorów frameworków. Autorzy frameworków nie są złymi ludźmi. W rzeczywistości, w przeważającej części, są bohaterami. Wielu bezinteresownie wypuszcza swój kod dla społeczności open source. Gdyby nie ci ludzie, nasze programistyczne żywota byłyby znacznie mniej przyjemne i produktywne.
Przedstawiłem tę kwestię autorów, ponieważ pomaga mi ona zrozumieć pewną mechanikę zależności pomiędzy autorami a użytkownikami frameworków.
Autorzy frameworków pokonają znaczne odległości, żeby tylko udało im się zagonić Cię do ich zagrody. Będą pisać artykuły i przemawiać na konferencjach. Dostarczą przykłady pokazujące, w jaki sposób możesz połączyć się ściśle, bardzo ściśle z ich kodem. Pokażą wszystkie korzyści, jakie ma takie ścisłe połączenie. Oni są przekonani, że ich kod pomoże Ci, i będą ciężko pracować, żeby Cię o tym przekonać.
To jest zupełnie normalne i w żaden sposób nie jest niehonorowe. Po prostu chcą Cię mieć w swojej zagrodzie.
Jednakże, kiedy już będziesz w ich zagrodzie, ich zainteresowanie Tobą zmienia się w pewien sposób. To jest zdjęcie jednego z popularnych autorów frameworków mówiącego jego użytkownikom, co myśli o niektórych ich obawach. (Tylko dla dorosłych)

Na Odległość Wyciągniętych Ramion

Przez te wszystkie lata, nabyłem zdrowego sceptyzmu dotyczącego frameworków. Mimo że przyznaję, że mogą być ekstremalnie użyteczne i zaoszczędzić ogrom czasu; również zdaję sobie sprawę, że to kosztuje. Czasami te koszty rzeczywiście mogą być bardzo wysokie.
Więc, moją strategią jest trzymać frameworki takie, jak Spring, Hibernate, czy Rails na odległość wyciągniętych ramion; za granicami architektonicznymi. Najwięcej korzyści mam z nich korzystając z nich w taki sposób; i dzięki temu mam nad nimi bezlitosną przewagę.


Ale nie pozwalam tym frameworkom podchodzić zbyt blisko. Nie oddaję im mojej niezależności. I pozwalam mackom ich kodu grzebać w wysokopoziomowych zasadach moich systemów. Mogą dotykać moich drugoplanowych podsystemów; ale trzymam je z dala od kluczowej logiki biznesowej. Wysokopoziomowe zasady moich systemów nigdy nie powinny być dotykane przez frameworki.
[1] Star Trek: The City on the Edge of Forever, Harlan Ellison, 1967
[2] Przeprosiny


Powyższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina z dnia 11 maja 2014 ze strony:


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.

O czym jest Ruch Rzemiosła Oprogramowania

uncle bob label image
TL;DR

Przeszedłem od Dana Northa, przez Gila Zilberfelda, po Michaela Feathersa do Jasona Gormana. Wydaje mi się, że wśród ludzi w ruchu rzemiosła oprogramowania nie ma jasnego przekazu. Mam nadzieję, że ten wpis wyjaśni kilka rzeczy.
Po co powstał ruch rzemiosła oprogramowania? Co motywowało jego powstanie? Czym jest napędzany teraz? Jedna rzecz; jest tylko jedna rzecz.
Jesteśmy zmęczeni pisaniem gówna.
Tak jest. Koniec rumakowania. Do widzenia, ślepa Genia. Bez odbioru.

Poniższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina z dnia 17 stycznia 2011 ze strony:


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.


Jesteśmy zmęczeni pisaniem gówna. Jesteśmy zmęczeni wprowadzaniem w zakłopotanie siebie i naszych klientów poprzez pisanie parszywego oprogramowania. Mamy dość radzenia naszym klientom, żeby najlepiej restartowali system raz dziennie o północy. Nie chcemy list błędów o długości tysiąca stron. Nie chcemy kodu, który staje się każdego dnia bardziej poplątany i zgniły. Jesteśmy zmęczeni robieniem złej roboty. Chcemy zacząć robić dobrą robotę.
To ... jest ... to ... o czym ... to ... jest. O niczym innym.
Tego nie robimy:
  • Nie stawiamy kodu w centrum wszechświata.
  • Nie zamykamy się w sobie i nie ignorujemy ludzi z biznesu czy klienta.
  • Nie jesteśmy egoistami.
  • Nie oferujemy tanich certyfikacji.
  • Nie zapominamy, że naszym zadaniem jest zachwycić klientów.
Tego już nigdy nie będziemy robić:
  • Nie będziemy robić burdelu tylko po to, żeby zdążyć przed deadlinem.
  • Nigdy nie zaakceptujemy starego, głupiego kłamstwa, że sprzątniemy to później.
  • Nie uwierzymy w przeświadczenia, że szybko znaczy niedobrze.
  • Nie wybierzemy możliwości robienia tego źle.
  • Nie pozwolimy nikomu, aby zmusił nas do nieprofesjonalnego zachowania.
To będziemy robić od teraz:
  • Będziemy dotrzymywać terminów, wiedząc to, że jedyną możliwością poruszania się szybko jest poruszanie się w dobry sposób.
  • Będziemy zachwycać naszych klientów poprzez pisanie najlepszego kodu, na jaki nas stać.
  • Uszanujemy naszych pracodawców poprzez tworzenie najlepszych architektur, jakie tylko możemy.
  • Uszanujemy naszych kolegów w zespole poprzez testowanie wszystkiego, co tylko może być stestowane.
  • Będziemy pokorni na tyle, aby pisać te testy najpierw.
  • Będziemy ćwiczyć, aby stać się coraz lepszymi w naszym rzemiośle.
Będziemy zawsze pamiętać, co mówili nam nasi dziadkowie i nasze babcie:
  • Cokolwiek jest warte zrobienia, jest warte zrobienia tego dobrze.
  • Śpiesz się powoli, a wygrasz wyścig.
  • Tnij raz, ale wpierw zmierz dwa razy.
  • Ćwiczyć, ćwiczyć i jeszcze raz ćwiczyć.
Domyślam się, że niektórzy ludzie mogą spoglądać spode łba na nasze kata kodu, programistyczne rekolekcje i sesje ćwiczeń. Mogą pomyśleć, że zamykamy się w sobie i porzucamy naszych klientów. Mogą pomyśleć, że uciekliśmy od prawdziwego świata i poddaliśmy się pokusie samozadowalania. Łatwo mogę sobie wyobrazić kogoś, kto dochodzi do takich wniosków.
Ale oni mylą się w całej rozciągłości. Robimy to, ponieważ zależy nam na klientach. Poświęcamy swój czas i środki, aby być najlepszymi, jakimi tylko możemy być, aby nasi pracodawcy zyskali jak największą wartość ze współpracy z nami.
Czy myślisz, że muzycy grają na swoich instrumentach tylko wtedy, gdy są na scenie? Czy uważasz, że gracze uderzają w piłkę, tylko podczas meczu? Czy myślisz, że prawnicy wygłaszają swoje mowy końcowe tylko na procesach? Oczywiście, że nie. Ci ludzie to profesjonaliści; i profesjonaliści ćwiczą! Profesjonaliści uczą się o szczegółach swoich dyscyplin. Profesjonaliści znają wszystkie małe sztuczki i kruczki. Znają historię, teorię i opowieści anegdotyczne. Znają techniki i sposoby. Wiedzą o dobrych możliwościach i o złych możliwościach i potrafią oddzielić jedne od drugich. I wiedzą o tym wszystkim, ponieważ oni ćwiczą, ćwiczą i jeszcze raz ćwiczą.

Więc, kiedy widzisz kogoś noszącego zieloną opaskę na rękę z napisem "Czysty Kod", albo "Najpierw Testy", albo "Maniak Testowania", to nie znaczy, że oni dołączyli do jakiegoś ruchu, albo podpisali manifest, lub czują się ważniejsi od wszystkich innych. Oni nie uczestniczą w świętych wojnach. Nie próbują dołączyć do plemienia i zgromadzić się przy ognisku. Zielona opaska jest czymś osobistym. Jest obietnicą daną samemu sobie: "Będę robił dobrą robotę. Nie będę się śpieszył. Będę pisał testy. Będę poruszał się szybko, poruszając się dobry sposób. Nie będę pisał gówna. Będę ćwiczył, ćwiczył i jeszcze raz ćwiczył, aby móc być profesjonalistą".

Powyższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina z dnia 17 stycznia 2011 ze strony:


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.

Algorytm Dijkstry

uncle bob label image
Byłem jednego dnia na SCNA, i ktoś zagadnął mnie o TDD i algorytm Dijkstry. Zastanawiał się, czy można znaleźć sekwencję testów, która zaprowadzi do tego algorytmu. To wyglądało mi na fajne, krótkie ćwiczenie, więc zdecydowałem się spróbować.

Poniższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony:


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.


Zacząłem tak, jak zwykle; przez odpalenie ograniczonego przypadku testowego.
public class MinPathTest {
  @Test
  public void nothing() throws Exception {
  }
}
Algorytm Dijkstry jest prostym sposobem znajdowania najkrótszej drogi w grafie o krawędziach mających konkretną długość. Podając węzeł startowy i końcowy, algorytm wskaże, jaka jest najkrótsza ścieżka i jaka jest jej długość.
A więc już od samego początku są ciekawe decyzje do podjęcia. W jaki sposób powinienem przedstawiać wejściowy graf? Jak powinienem przedstawiać wyjście tego algorytmu? O większości tego możemy prawdopodobnie zadecydować później. Na teraz, powinniśmy skoncentrować się na najbardziej ograniczonym przypadku: pustym grafie.
public void noGraph_NoPathZeroLength() throws Exception {
  Assert.assertEquals("{}0", minPath(""));
}
Ten pierwszy test zmusił mnie, abym podjął jakieś decyzje o formacie wyjścia. Będę prezentował wyjściową ścieżkę jako zbiór węzłów pomiędzy nawiasami klamrowymi. Długość ścieżki będzie liczbą całkowitą za nawiasami klamrowymi.
Ta notacja jest tylko na potrzeby moich testów. Używam techniki, którą nazywam skomponowanymi asercjami. Lubię komponować moje asercje w zdania, które czyta się łatwo. To zwykle oznacza, że muszę pisać proste translatory, które zamieniają skomponowane asercje na rzeczywiste API systemu poddawanego testom.
To jasne, że mogę sprawić, aby ten test przechodził, nie używając niczego więcej niż tego:
private String minPath(String graph) {
  return "{}0";
}
Popatrzmy wnikliwie na ten przypadek testowy. Nie jest właściwe takie wywołanie metody minPath. Algorytm Dijkstry znajduje najkrótszą ścieżkę pomiędzy dwoma określonymi węzłami. Więc zakładając, że węzły mają nazwy, test powinien naprawdę wyglądać jakoś tak:
Assert.assertEquals("{}0", minPath("", "A", "Z"));
To brzydko wygląda. Możemy zrefaktorować to tak, aby było odrobinę ładniejsze:
private void assertPath(String graph, String expected) {
  assertEquals(expected, minPath(graph, "A", "Z"));
}

@Test
public void noGraph_NoPathZeroLength() throws Exception {
  assertPath("", "{}0");
}
Zauważ, że metoda assertPath dla prostoty zakłada, że wszystkie przypadki testowe będą używać "A" i "Z" jako ich pozycji startowych i końcowych.
Jedna, ostatnia zmiana. Myślę, że ścieżka i jej długość powinny być oddzielone.
private void assertMinPath(String graph,
                           int length, String path) {
  assertEquals(length, minLength(graph, "A", "Z"));
  assertEquals(path, minPath(graph, "A", "Z"));
}

@Test
public void noGraph_NoPathZeroLength() throws Exception {
  assertMinPath("", 0, "{}");
}

private int minLength(String graph, String begin, String end) {
  return 0;
}

private String minPath(String graph, String begin, String end) {
  return "{}";
}
Ponieważ są dwie metody do sprawdzenia w mojej asercji, myślę, że sensownym byłoby założyć, że powinny one być metodami tej samej klasy uruchamiającej algorytm Dijkstry. Użyjmy więc refaktoringu typu wyciągnij delegata, aby wyciągnąć to do nowej klasy.
public class MinPathTest {
  private void assertMinPath(String graph,
                             int length, String path) {
    PathFinder pf = new PathFinder(graph);
    assertEquals(length, pf.minLength("A", "Z"));
    assertEquals(path, pf.minPath("A", "Z"));
  }

  @Test
  public void noGraph_NoPathZeroLength() throws Exception {
    assertMinPath("", 0, "{}");
  }
}

class PathFinder {
  public PathFinder(String graph) {
  }

  public int minLength(String begin, String end) {
    return 0;
  }

  public String minPath(String begin, String end) {
    return "{}";
  }
}
Uważam to za interesujące, że już tak dużo namysłu i wysiłku zostało włożone w strukturę tego problemu — dla jednego tylko, ograniczonego przypadku testowego. Ale teraz myślę, że możemy dodać kilka innych ograniczonych przypadków:
@Test
public void degenerateCases() throws Exception {
  assertMinPath("", 0, "{}");   //pusty graf
  assertMinPath("A", 0, "{}");  //jeden węzeł
  assertMinPath("B1C", 0, "{}");//nie ma ani początku ani końca
  assertMinPath("A1C", 0, "{}");//nie ma końca
  assertMinPath("B1Z", 0, "{}");//nie ma początku
}
Te testy zmusiły mnie, aby podjąć kolejną decyzję o skomponowanej asercji. Dla naszych testów struktura krawędzi grafu będzie wyglądała tak: <nazwa>długość<nazwa>. Więc B1C jest krawędzią o długości 1, która łączy węzeł B i C.
Myślę, że wszystkie te przypadki testowe są dość ograniczone. Więc przekręćmy koło zębate skomplikowania o jeden ząbek w górę i stwórzmy test, który zmusi nas do zrobienia czegoś choć trochę bardziej sprytnego.
@Test
public void oneEdge() throws Exception {
  assertMinPath("A1Z", 1, "{AZ}");
}
Ten test, oczywiście, nie przejdzie. Czuję też pewien dyskomfort, ponieważ testuję dwie rzeczy naraz, długość i ścieżkę, które mogłyby być testowane oddzielnie. Wyjdę teraz na zrzędę, bo poświęciłem tyle czasu na wprowadzenie skomponowanej asercji; i teraz chciałbym ją rozbić znowu. Ale myślę, że jest jeden "sprytny" sposób na obejście tego:
private static String ANY = null;

private void assertMinPath(String graph,
                           Integer length, String path) {
  PathFinder pf = new PathFinder(graph);
  if (length != null)
    assertEquals((int)length, pf.minLength("A", "Z"));
  if (path != null)
    assertEquals(path, pf.minPath("A", "Z"));
}
...
@Test
public void oneEdge() throws Exception {
  assertMinPath("A1Z", 1, ANY);
}
To pozostawia moją skomponowaną asercję nietkniętą, i pozwala mi pominąć dowolną z tych dwóch komponentów na życzenie. A teraz sprawmy, żeby ten test przechodził.
Teraz, oczywiście, mógłbym zrobić coś tak ohydnego, jak to:
public int minLength(String begin, String end) {
  if (graph.equals("A1Z"))
    return 1;
  return 0;
}
Ale to łamie kilka zasad. Po pierwsze, to łamie zasadę ogólności, która mówi: W miarę, jak testy robią się bardziej konkretne, kod robi się bardziej ogólny. Innymi słowy, kod produkcyjny musi stać się bardziej ogólny, aby spełnić test, który nie przechodzi. Do produkcyjnego kodu nie możesz dodawać wyrażeń, które są specyficzne dla danego testu. (Mówię o tym dużo więcej w Odcinku 19: Zaawansowane TDD, na cleancoders.com)
Drugą złamaną zasadą jest zależność testów. Nie chcemy, aby testy stały się mocno zależne od produkcyjnego kodu. Im więcej zależności, tym bardziej testy stają się kruche. Nie chcemy doprowadzić do sytuacji, gdy pojedyncza zmiana w kodzie produkcyjnym zepsuje dziesiątki czy setki testów.
To oznacza, że nie powinienem przekazywać String graph do konstruktora klasy PathFinder. To też oznacza, że funkcja minPath nie powinna zwracać String używanego przez skomponowaną asercję.
A więc teraz jest czas, aby zacząć uniezależniać testy. Funkcja makePathFinder poniżej pokazuje, jak to zrobiłem.
public class MinPathTest {
  private static String ANY = null;

  private void assertMinPath(String graph,
                             Integer length, String path) {
    PathFinder pf = makePathFinder(graph);
    if (length != null)
      assertEquals((int) length, pf.minLength("A", "Z"));
    if (path != null)
      assertEquals(path, pf.minPath("A", "Z"));
  }

  private PathFinder makePathFinder(String graph) {
    PathFinder pf = new PathFinder();
    Pattern edgePattern =
            Pattern.compile("(\\D+)(\\d+)(\\D+)");
    Matcher matcher = edgePattern.matcher(graph);
    if (matcher.matches()) {
      String start = matcher.group(1);
      int length = Integer.parseInt(matcher.group(2));
      String end = matcher.group(3);
      pf.addEdge(start, end, length);
    }
    return pf;
  }

  @Test
  public void degenerateCases() throws Exception {
    assertMinPath("", 0, "{}");   //empty graph
    assertMinPath("A", 0, "{}");  //one node
    assertMinPath("B1C", 0, "{}");//no start or end
    assertMinPath("A1C", 0, "{}");//no end
    assertMinPath("B1Z", 0, "{}");//no start
  }

  @Test
  public void oneEdge() throws Exception {
    assertMinPath("A1Z", 1, ANY);
  }
}

class PathFinder {
  private List<Edge> edges = new ArrayList<>();

  public PathFinder() {
  }

  public int minLength(String begin, String end) {
    int length = 0;
    for (Edge edge : edges) {
      if (edge.begin.equals(begin) && edge.end.equals(end))
        length += edge.length;
    }
    return length;
  }

  public String minPath(String begin, String end) {
    return "{}";
  }

  public void addEdge(String start, String end, int length) {
    edges.add(new Edge(start, end, length));
  }

  private static class Edge {
    public final String begin;
    public final String end;
    public final int length;

    public Edge(String begin, String end, int length) {
      this.begin = begin;
      this.end = end;
      this.length = length;
    }
  }
}
Zauważ, że całe parsowanie dla skomponowanej asercji pozostaje w klasie testowej. Klasa PathFinder nie wie nic o tej śmiesznej składni, której używam w testach. Zauważ także, że aby testy przechodziły, kod produkcyjny musi zakładać, że wykres ma tylko jedną krawędź. To założenie zamierzamy złamać w kolejnych kilku testach. W międzyczasie powinniśmy pozbyć się tego ANY.
assertMinPath("A1Z", 1, "{AZ}");
Więc zamierzam zbudować listę węzłów w ścieżce. Listę? Aaaa, jest składnia toString dla list. Powinniśmy zmienić ten test i wszystkie inne testy następująco:
@Test
public void degenerateCases() throws Exception {
  assertMinPath("", 0, "[]");   //pusty graf
  assertMinPath("A", 0, "[]");  //jeden węzeł
  assertMinPath("B1C", 0, "[]");//nie ma ani początku ani końca
  assertMinPath("A1C", 0, "[]");//nie ma końca
  assertMinPath("B1Z", 0, "[]");//nie ma początku
}

@Test
public void oneEdge() throws Exception {
  assertMinPath("A1Z", 1, "[A, Z]");
}
Teraz, aby to przechodziło, dodamy w funkcji pomocniczej assertMinPath wywołanie toString.
...
    if (path != null)
      assertEquals(path, pf.minPath("A", "Z").toString());
...
Dodamy listę węzłów path do PathFindera i po prostu zwrócimy ją w minLength.
class PathFinder {
  private List<Edge> edges = new ArrayList<>();
  ...

  public int minLength(String begin, String end) {
    int length = 0;
    for (Edge edge : edges) {
      if (edge.begin.equals(begin) && edge.end.equals(end)) {
        length += edge.length;
        path.add(edge.begin);
        path.add(edge.end);
      }
    }
    return length;
  }

  public List<String> minPath(String begin, String end) {
    return path;
  }
...
To działa. Ale nie podoba mi się fakt, że minLength również oblicza ścieżkę. Myślę, że powinniśmy oddzielić obliczenia od raportowania.
  private void assertMinPath(String graph,
                             Integer length, String path) {
    PathFinder pf = makePathFinder(graph);
    if (length != null)
      assertEquals((int) length, pf.getLength());
    if (path != null)
      assertEquals(path, pf.getPath().toString());
  }

  private PathFinder makePathFinder(String graph) {
    PathFinder pf = new PathFinder();
    ...
    pf.findPath("A", "Z");
    return pf;
  }

class PathFinder {
  private List<Edge> edges = new ArrayList<>();
  private List<String> path = new ArrayList<>();
  private int length;

  ...

  public int getLength() {
    return length;
  }

  public List<String> getPath() {
    return path;
  }

...
OK, teraz lepiej. Teraz, upewnijmy się, że dostajemy prawidłową długość.
assertMinPath("A2Z", 2, "[A, Z]");
Taaa, to działa całkiem nieźle. Więc spróbujmy dwóch następujących po sobie krawędzi.
@Test
public void twoEdges() throws Exception {
  assertMinPath("A1B,B1Z", 2, ANY);
}
To nie przechodzi, jak należało się spodziewać, dając nam w wyniku długość zero. Aby to przechodziło, musimy umieć parsować wiele krawędzi w funkcji pomocniczej makePathFinder. To jest całkiem proste. Tylko podziel graf na przecinkach, i wrzuć dopasowanie wyrażeń regularnych w pętlę.
private PathFinder makePathFinder(String graph) {
  PathFinder pf = new PathFinder();
  Pattern edgePattern = Pattern.compile("(\\D+)(\\d+)(\\D+)");
  String[] edges = graph.split(",");
  for (String edge : edges) {
    Matcher matcher = edgePattern.matcher(edge);
    if (matcher.matches()) {
      String start = matcher.group(1);
      int length = Integer.parseInt(matcher.group(2));
      String end = matcher.group(3);
      pf.addEdge(start, end, length);
    }
  }
  pf.findPath("A", "Z");
  return pf;
}
Oczywiście to nadal nie sprawia, że test przechodzi, więc teraz zamierzamy połączyć dwie krawędzie. Załóżmy, że krawędzie są ułożone po kolei, więc wierzchołek A rozpoczyna pierwszą krawędź, i wierzchołek Z kończy drugą krawędź. Przy takim założeniu, możemy ustawić całe połączenie poprzez zmianę warunku && na || w funkcji findPath:
public void findPath(String begin, String end) {
  length = 0;
  for (Edge edge : edges) {
    if (edge.begin.equals(begin) || edge.end.equals(end)) {
      length += edge.length;
      path.add(edge.begin);
      path.add(edge.end);
    }
  }
}
Podoba Ci się ta zmiana? && na ||. Taaak, całkiem sprytnie. To zadziała tylko dla dwóch kolejnych krawędzi. Założenia wznoszą się w niebiosa! I, tak czy inaczej, to nie działa.
Ooo, przechodzą testy twoEdges, i testy oneEdge, ale nie przechodzą testy degenerateCases. I to nie dziwota, ponieważ tylko nasze dwa ostatnie ograniczone przypadki testowe pasują do założenia "A" pierwszy lub "Z" ostatni.
Aby wszystkie te testy przechodziły, potrzebuję implementacji, która w wyniku daje zerową długość i pustą ścieżkę, jeżeli nie istnieje ścieżka pomiędzy A i Z. Ponieważ nie wiem, ile będzie krawędzi (może być zero, jeden, dwie) nie mogę wziąć tylko dwóch. Zamiast tego, mógłbym zrobić analizę przypadków dla zera, jednej lub dwóch krawędzi; jak poniżej:
public void findPath(String begin, String end) {
  if (edges.size() == 0)
    return;

  else if (edges.size() == 1) {
    Edge edge = edges.get(0);
    if (edge.begin.equals(begin) && edge.end.equals(end)) {
      path.add(edge.begin);
      path.add(edge.end);
      length += edge.length;
    }
  } else {
    for (Edge edge : edges) {
      if (edge.begin.equals(begin) || edge.end.equals(end)) {
        path.add(edge.begin);
        path.add(edge.end);
        length += edge.length;
      }
    }
  }
}
OK, to działa, ale to jest naprawdę okropne. Nie tylko łamie zasadę ogólności; to jest po prostu ohydne. Co więcej, nie do końca poprawnie tworzy ścieżkę. Na przykład test: assertMinPath("A1B,B1Z", 2, "[A, B, Z]"); nie przechodzi, ponieważ tworzy [A, B, B, Z]. Mógłbym to naprawić przez dodanie jeszcze jednej okropnej instrukcji if; ale mam lepszy pomysł. Przejdźmy graf od początku do końca.
public void findPath(String begin, String end) {
  List<String> p = new ArrayList<>();
  int l = 0;
  p.add(begin);

  for (Edge e = findEdge(begin);
       e != null; e = findEdge(e.end)) {
    p.add(e.end);
    l += e.length;
    if (e.end.equals(end)) {
      length = l;
      path = p;
      return;
    }
  }
}

private Edge findEdge(String begin) {
  for (Edge e : edges) {
    if (e.begin.equals(begin))
      return e;
  }
  return null;
}
OK, działa. To osobliwe, że musieliśmy użyć tymczasowych zmiennych length i path; ale to jedyny sposób, jaki przychodzi mi na myśl, na ignorowanie ścieżek, które nie istnieją. Myślę także, że to rozwiązanie pozbawia nas zależności od kolejności.
@Test
public void twoEdges() throws Exception {
  assertMinPath("A1B,B1Z", 2, "[A, B, Z]");
  assertMinPath("B1Z,A1B", 2, "[A, B, Z]");
  assertMinPath("A1X,Y1Z", 0, "[]");
}
Tak, wszystkie przechodzą. Myślę, że trzy i więcej krawędzi też zadziała. I także grafy z jedną kompletną ścieżką i pozostałymi dyndającymi ścieżkami.
@Test
public void threeEdges() throws Exception {
  assertMinPath("A2B,B3C,C4Z", 9, "[A, B, C, Z]");
  assertMinPath("B3C,C4Z,A2B", 9, "[A, B, C, Z]");
}

@Test
public void OnlyOnePath() throws Exception {
  assertMinPath("A1B,B2C,C3Z,B4D,D6E", 6, "[A, B, C, Z]");
}
Ale to nie będzie przechodzić, ponieważ przejście przez graf pomija krawędź C3Z.
assertMinPath("A1B,B2C,C3D,C3Z", 6, "[A, B, C, Z]");
Ok. Więc nie możemy po prostu przejść grafu po kolei. W zamian to, co musimy zrobić, to sprawdzić każdą możliwą drogę, która wychodzi z wierzchołka startowego; i przez całą tę drogę musimy zapisywać nasze tymczasowe znaleziska, aż dojdziemy do końca.
Jak zobaczysz poniżej, to wymaga odrobinę mrówczego wysiłku. Muszę śledzić wszystkie wierzchołki, i ścieżki i długości połączone z tymi wierzchołkami. Ale, poza tym, algorytm jest prawie taki sam jak do tej pory.
Iteracja w pętli jest inna. Zaczyna się w początkowym wierzchołku, i potem przechodzi przez wszystkich nieodwiedzonych sąsiadów, i zapisuje dodane długości i ścieżki w tych sąsiadach.
Zauważ, że użyłem Integer.MAX_VALUE jako strażnika, który oznacza "Nieodwiedzony z odwiedzonego wierzchołka". Ograniczamy limit wyszukiwania do tylko tych wierzchołków, które były odwiedzone, ponieważ przecież idziemy od początku do końca. Każdy węzeł, który nie był odwiedzony, oczywiście, nie może być następnym w ścieżce.
class PathFinder {
  private List<Edge> edges = new ArrayList<>();
  private Set<String> nodeNames = new HashSet<>();
  private Map<String, Node> nodes = new HashMap<>();
  private Node endNode;

  public void findPath(String begin, String end) {
    List<String> unvisited = initializeSearch(begin, end);

    for (String node = begin;
      node != null; node = getNext(unvisited)) {
      unvisited.remove(node);
      visit(node);
    }

    setupEndNode(end);
  }

  private List<String> initializeSearch(String begin,
                                     String end) {
    nodeNames.add(begin);
    nodeNames.add(end);
    List<String> unvisited = new ArrayList<>(nodeNames);
    for (String node : unvisited)
      nodes.put(node, new Node(Integer.MAX_VALUE));

    nodes.get(begin).length = 0;
    return unvisited;
  }

  private void visit(String node) {
    List<Edge> neighbors = findEdges(node);
    Node curNode = nodes.get(node);
    for (Edge e : neighbors) {
      Node nbr = nodes.get(e.end);
      nbr.length = curNode.length + e.length;
      nbr.path = new ArrayList<String>();
      nbr.path.addAll(curNode.path);
      nbr.path.add(node);
    }
  }

  private void setupEndNode(String end) {
    endNode = nodes.get(end);
    if (endNode.length != Integer.MAX_VALUE)
      endNode.path.add(end);
    else
      endNode.length = 0;
  }

  private String getNext(List<String> unvisited) {
    for (String name : unvisited) {
      Node candidate = nodes.get(name);
      if (candidate.length != Integer.MAX_VALUE)
        return name;
    }
    return null;
  }

  private List<Edge> findEdges(String begin) {
    List<Edge> found = new ArrayList<>();
    for (Edge e : edges) {
      if (e.begin.equals(begin))
        found.add(e);
    }
    return found;
  }

  public int getLength() {
    return endNode.length;
  }

  public List<String> getPath() {
    return endNode.path;
  }

  public void addEdge(String start, String end, int length) {
    edges.add(new Edge(start, end, length));
    nodeNames.add(start);
    nodeNames.add(end);
  }

  private static class Edge {
    public final String begin;
    public final String end;
    public final int length;

    public Edge(String begin, String end, int length) {
      this.begin = begin;
      this.end = end;
      this.length = length;
    }
  }

  private static class Node {
    public int length;
    public List<String> path;

    public Node(int l) {
      this.length = l;
      this.path = new ArrayList<>();
    }
  }
}
To przechodzi. Więc teraz potrzebujemy dodać test grafu, który ma równoległe ścieżki. Tu mam jeden prosty, który powinien nie przechodzić:
assertMinPath("A1B,B2Z,A1Z", 1, "[A, Z]");
I nie przechodzi
Aby sprawić, żeby to przechodziło, musimy wykryć, czy dwie ścieżki zbiegają się w jednym węźle. To proste. Jeżeli długość na węźle docelowym nie wynosi Integer.MAX_VALUE to oznacza, że inna ścieżka już osiągnęła ten węzeł. Ponieważ szukamy minimum, możemy po prostu ustawić długość na tym węźle na minimalną wartość spośród zbiegających się w tym węźle ścieżek. Wartość Integer.MAX_VALUE wydaje się byc bardzo przydatna dla tego sprawdzenia, ponieważ jest zamiennikiem dla "nieskończonej" długości.
private void visit(String node) {
  List<Edge> neighbors = findEdges(node);
  Node curNode = nodes.get(node);
  for (Edge e : neighbors) {
    Node nbr = nodes.get(e.end);

    int newLength = curNode.length + e.length;
    if (nbr.length > newLength) {
      nbr.length = newLength;
      nbr.path = new ArrayList<String>();
      nbr.path.addAll(curNode.path);
      nbr.path.add(node);
    }
  }
}
Prawdopodobnie możemy przyspieszyć troszkę algorytm, kończąc poszukiwania, kiedy osiągniemy węzeł końcowy.
for (String node = begin; node != null && !node.equals(end); node = getNext(unvisited)) {
  unvisited.remove(node);
  visit(node);
}
I zapewne możemy przyspieszyć algorytm nawet bardziej przez preferowanie przeszukiwania nieodwiedzonych węzłów, które zostały odwiedzone przez najkrótszą ścieżkę.
private String getNext(List<String> unvisited) {
  String minNodeName = null;
  int minLength = Integer.MAX_VALUE;

  for (String name : unvisited) {
    Node candidate = nodes.get(name);
    if (candidate.length < minLength) {
      minLength = candidate.length;
      minNodeName = name;
    }
  }
  return minNodeName;
}
To, w każdym możliwym sensie, jest algorytm Dijkstry. Ta implementacja nie jest szybka, ponieważ użyłem zbiorów i list, i mnóstwa nieefektywnych struktur. Przyspieszenie tego zajęłoby całkiem sporo roboty. Co więcej, są tam wbudowane pewne założenia, które należałoby naprawić. Przede wszystkim, jest założenie, że graf wejściowy musi być skierowany; natomiast ogólny algorytm nie wymaga takiego założenia. Na koniec, całości przydałaby się odrobina refaktoringu.
Ale celem było zobaczenie, czy możliwe jest wykorzystanie TDD do dojścia do algorytmu Dijkstry krok po kroku. Moim zdaniem jest możliwe; chociaż, muszę przyznać, że to podejście było trochę szarpane. Te kilka początkowych testów prowadziły mnie przez rząd niepewnych algorytmów, które nie bardzo chciały ewoluować jeden w drugi. Nie mniej, każdy nowy test ujawniał słabości we wcześniejszych implementacjach, które mogły być naprawione w stosunkowo prosty sposób.
Czy jest lepsza sekwencja testów, która prowadzi bardziej wprost do algorytmu Dijkstry, bez tej niepewnej szarpaniny? Być może; ale jeśli tak, nie znalazłem ich.


Mimo wszystko, było to zabawne ćwiczenie. Dziękuję uczestnikowi SCNA za zaproponowanie tego.
Końcowy kod, który nadal potrzebuje troszeczkę posprzątania (pozostawiam czytelnikowi jako ćwiczenie ;-)
package dijkstrasAlg;

import org.junit.Test;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import static org.junit.Assert.assertEquals;

public class MinPathTest {
  private static String ANY = null;

  private void assertMinPath(String graph,
                             Integer length, String path) {
    PathFinder pf = makePathFinder(graph);
    if (length != null)
      assertEquals((int) length, pf.getLength());
    if (path != null)
      assertEquals(path, pf.getPath().toString());
  }

  private PathFinder makePathFinder(String graph) {
    PathFinder pf = new PathFinder();
    Pattern edgePattern =
            Pattern.compile("(\\D+)(\\d+)(\\D+)");
    String[] edges = graph.split(",");
    for (String edge : edges) {
      Matcher matcher = edgePattern.matcher(edge);
      if (matcher.matches()) {
        String start = matcher.group(1);
        int length = Integer.parseInt(matcher.group(2));
        String end = matcher.group(3);
        pf.addEdge(start, end, length);
      }
    }
    pf.findPath("A", "Z");
    return pf;
  }

  @Test
  public void degenerateCases() throws Exception {
    assertMinPath("", 0, "[]");   //empty graph
    assertMinPath("A", 0, "[]");  //one node
    assertMinPath("B1C", 0, "[]");//no start or end
    assertMinPath("A1C", 0, "[]");//no end
    assertMinPath("B1Z", 0, "[]");//no start
  }

  @Test
  public void oneEdge() throws Exception {
    assertMinPath("A1Z", 1, "[A, Z]");
    assertMinPath("A2Z", 2, "[A, Z]");
  }

  @Test
  public void twoEdges() throws Exception {
    assertMinPath("A1B,B1Z", 2, "[A, B, Z]");
    assertMinPath("B1Z,A1B", 2, "[A, B, Z]");
    assertMinPath("A1X,Y1Z", 0, "[]");
  }

  @Test
  public void threeEdges() throws Exception {
    assertMinPath("A2B,B3C,C4Z", 9, "[A, B, C, Z]");
    assertMinPath("B3C,C4Z,A2B", 9, "[A, B, C, Z]");
  }

  @Test
  public void OnlyOnePath() throws Exception {
    assertMinPath("A1B,B2C,C3Z,B4D,D6E", 6, "[A, B, C, Z]");
    assertMinPath("A1B,B2C,C3D,C3Z", 6, "[A, B, C, Z]");
  }

  @Test
  public void parallelPaths() throws Exception {
    assertMinPath("A1B,B2Z,A1Z", 1, "[A, Z]");
    assertMinPath("A1B,A1C,A2D,C5E,B8E,C1F,D3F,F2G,G3Z,E2G",
                   7,"[A, C, F, G, Z]");
  }
}

class PathFinder {
  private List<Edge> edges = new ArrayList<>();
  private Set<String> nodeNames = new HashSet<>();
  private Map<String, Node> nodes = new HashMap<>();
  private Node endNode;

  public void findPath(String begin, String end) {
    List<String> unvisited = initializeSearch(begin, end);

    for (String node = begin;
      node != null && !node.equals(end);
      node = getNext(unvisited)) {
      unvisited.remove(node);
      visit(node);
    }

    setupEndNode(end);
  }

  private List<String> initializeSearch(String begin,
                                     String end) {
    nodeNames.add(begin);
    nodeNames.add(end);
    List<String> unvisited = new ArrayList<>(nodeNames);
    for (String node : unvisited)
      nodes.put(node, new Node(Integer.MAX_VALUE));

    nodes.get(begin).length = 0;
    return unvisited;
  }

  private void visit(String node) {
    List<Edge> neighbors = findEdges(node);
    Node curNode = nodes.get(node);
    for (Edge e : neighbors) {
      Node nbr = nodes.get(e.end);

      int newLength = curNode.length + e.length;
      if (nbr.length > newLength) {
        nbr.length = newLength;
        nbr.path = new ArrayList<String>();
        nbr.path.addAll(curNode.path);
        nbr.path.add(node);
      }
    }
  }

  private void setupEndNode(String end) {
    endNode = nodes.get(end);
    if (endNode.length != Integer.MAX_VALUE)
      endNode.path.add(end);
    else
      endNode.length = 0;
  }

  private String getNext(List<String> unvisited) {
    String minNodeName = null;
    int minLength = Integer.MAX_VALUE;

    for (String name : unvisited) {
      Node candidate = nodes.get(name);
      if (candidate.length < minLength) {
        minLength = candidate.length;
        minNodeName = name;
      }
    }
    return minNodeName;
  }

  private List<Edge> findEdges(String begin) {
    List<Edge> found = new ArrayList<>();
    for (Edge e : edges) {
      if (e.begin.equals(begin))
        found.add(e);
    }
    return found;
  }

  public int getLength() {
    return endNode.length;
  }

  public List<String> getPath() {
    return endNode.path;
  }

  public void addEdge(String start, String end, int length) {
    edges.add(new Edge(start, end, length));
    nodeNames.add(start);
    nodeNames.add(end);
  }

  private static class Edge {
    public final String begin;
    public final String end;
    public final int length;

    public Edge(String begin, String end, int length) {
      this.begin = begin;
      this.end = end;
      this.length = length;
    }
  }

  private static class Node {
    public int length;
    public List<String> path;

    public Node(int l) {
      this.length = l;
      this.path = new ArrayList<>();
    }
  }
}


Powyższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina ze strony:


Proszę o komentarze, jeżeli ta luźność jest zbyt daleko posunięta.

[Kod źródłowy jest dostępny tutaj. - przyp. tłum.]

Wpisz adres e-mail, aby zasubskrybować powiadomienia o nowych postach: