Jeszcze o radzeniu sobie z głęboką rekursją

Home

W poście opisałem ogólne podejście to radzenia sobie z bardzo głęboką rekursją, która prowadzi do StackOverflowException. Dzisiaj powrócę do tematu. Od czasu do czasu, oprócz pogłębiania wiedzy na temat bibliotek, framework'ów itd. lubię rozwiązywać różnego rodzaju algorytmiczne zadania programistyczne. Jakiś czas temu rozwiązywałem takie zadanie:

Zadana jest mapa świata w postaci prostokątnej tablicy dwuwymiarowej. Każdy element tablicy ma swój kolor. Sąsiadujące (stykające się jednym z boków) z sobą elementy tego samego koloru należą do jednego kraju. Należy policzyć liczbę krajów na tej mapie. Jeśli dwa elementy tablicy mają ten sam kolor, ale nie znajdują się w jednym ciągłym obszarze, to należą do różnych krajów. 

Poniższy rysunek przedstawia przykładową mapę takiego świata, na który składa się 6 krajów.



Zacznijmy od głównej metody wykonującej obliczenia. Koncepcja jest prosta. Nie ulega wątpliwości, że należy odwiedzić wszystkie elementy tablicy aby móc zwrócić poprawny wynik. Aby nie zliczać tego samego elementu dwa razy używam wartości Int32.MaxValue jako znacznika już odwiedzonych elementów. Jeśli odwiedzając kolejny element znajduję wartość inną niż Int32.MaxValue to znaczy, że danego elementu jeszcze nie odwiedziłem i zwiększam licznik krajów.

public int Count(int[][] map)
{
 if (map == null) return 0;
 
 if (map.Length == 0) return 0;

 var numberOfCountries = 0;

 for (var y = 0; y < map.Length; ++y)
 {
  for (var x = 0; x < map[0].Length; ++x)
  {
   if (map[y][x] != Int32.MaxValue)
   {
    numberOfCountries++;
    /* Zaznacz elementy należące do danego kraju */
    VisitCountry(map, map[y][x], y, x);
   }
  }
 }

 return numberOfCountries;
}

Co kryje się pod tajemniczym Zaznacz elementy należące do danego kraju? W pierwszym podejście napisałem funkcję rekurencyjną, która począwszy od zadanego elementu odwiedzała wszystkie pola należącego do danego kraju i oznaczała je jako odwiedzone.

public void VisitCountry(int[][] map, int currentColor, int y, int x)
{
 if (y < 0 || x < 0 || y >= map.Length || x >= map[0].Length) return;

 if (map[y][x] != currentColor) return;
            
 map[y][x] = Int32.MaxValue;

 VisitCountry(map, currentColor, y + 1, x);
 VisitCountry(map, currentColor, y, x + 1);
 VisitCountry(map, currentColor, y - 1, x);
 VisitCountry(map, currentColor, y, x - 1);
}

Poniżej kod testujący dla przykładu z początku postu:

int[][] map = new int[5][];

for (int i = 0; i < map.Length; ++i)
 map[i] = new int[4];

map[0][0] = 1; map[0][1] = 3; map[0][2] = 3; map[0][3] = 2;
map[1][0] = 1; map[1][1] = 2; map[1][2] = 3; map[1][3] = 2;
map[2][0] = 1; map[2][1] = 1; map[2][2] = 1; map[2][3] = 1;
map[3][0] = 2; map[3][1] = 3; map[3][2] = 3; map[3][3] = 1;
map[4][0] = 2; map[4][1] = 2; map[4][2] = 2; map[4][3] = 2; 

var result = Count(map);

W warunkach zadania było jednak napisane, że szerokość/wysokość mapy może znajdować się w przedziale od 1 do 1000000. Sprawdźmy, więc czy kod ten obsłuż dużo większą mapę:

int[][] bigMap = new int[10000][];
for (int i = 0; i < bigMap.Length; ++i)
{
 bigMap[i] = new int[10000];
 for (int j = 0; j < bigMap.Length; ++j)
  bigMap[i][j] = i;
}

var result = Count(bigMap);

Na mojej maszynie wystarczy już mapa 10000 x 10000 aby pojawił sie wyjątek StackOverflowException. Zgodnie z tym co napisałem we wcześniejszym poście metoda VisitCountry powinna więc wyglądać tak:

public void VisitCountry(int[][] map, int startY, int startX)
{
 var toCheck = new Queue<Tuple<int, int>>();
 toCheck.Enqueue(new Tuple<int, int>(startY, startX));

 var currentColor = map[startY][startX];

 while (toCheck.Count > 0)
 {
  var t = toCheck.Dequeue();

  if (t.Item1 < 0 || t.Item2 < 0 || t.Item1 >= map.Length || t.Item2 >= map[0].Length) continue;

  if (map[t.Item1][t.Item2] != currentColor) continue;

  map[t.Item1][t.Item2] = Int32.MaxValue;

  toCheck.Enqueue(new Tuple<int, int>(t.Item1 + 1, t.Item2));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1, t.Item2 + 1));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1 - 1, t.Item2));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1, t.Item2 - 1));
 }
}

Tym razem mapa 10000 x 10000 i większe zostanie poprawnie obsłużona. Kod ten można jeszcze optymalizować. Na przykład zliczać ile pól się już odwiedziło i przerwać dalsze przetwarzanie, jeśli odwiedziło się wszystkie. Dalszą optymalizację kodu można potraktować jako ćwiczenie.

Go

Home

GO to komenda, która sygnalizuje, że narzędzie takie jak sqlcmd powinno wysłać bieżący batch kodu T-SQL do instancji SQL Server'a. Do tej pory nie przywiązywałem do niej dużej uwagi, skupiając się na właściwym kodzie. Pominięcie GO może jednak doprowadzić do kłopotów. Popatrzmy na poniższy skrypt, który tworzy procedurę składowaną pr_Fun.

IF OBJECT_ID(N'dbo.pr_Fun') IS NOT NULL
BEGIN
      DROP PROCEDURE dbo.pr_Fun
END
GO

CREATE PROCEDURE dbo.pr_Fun
AS
BEGIN
      /*...*/
      RETURN
END

GRANT EXECUTE ON dbo.pr_Fun TO public
GO

Na pierwszy rzut oka wygląda prawidłowo i jeśli spróbujemy go uruchomić wykona się bez żadnych problemów. Niestety ale zawiera błąd, który pojawi się dopiero kiedy z procedury pr_Fun spróbuje skorzystać użytkownik z ograniczonymi uprawnieniami. Otrzyma taki komunikat:

Msg 229, Level 14, State 5, Procedure pr_Fun, Line 1
The EXECUTE permission was denied on the object 'pr_Fun', database 'Test', schema 'dbo'.

Dlaczego? Stanie się tak ponieważ wbrew pozorom powyższy skrypt nie nada uprawnień do wykonywania procedury pr_Fun użytkownikom z rolą public. Dzieje się tak z powodu braku komendy GO w odpowiednim miejscu.

Jeśli uruchomimy powyższy skrypt, a potem podejrzymy kod procedury (np.: sp_helptext pr_Fun) to okaże się, że polecenie GRANT EXECUTE zostało dołączone do kodu procedury, zamiast zostać wykonane. Prawidłowa wersja powyższego skryptu powinna wyglądać tak:

...
END
GO

GRANT EXECUTE ON dbo.pr_Fun TO public
GO

Niestety ale uruchamiając skrypt z takim błędem nie zostaniemy o tym poinformowani, ani ostrzeżeni. Jest to dla mnie o tyle dziwne, że słowo kluczowe END jawnie wskazuje koniec kodu procedury, a skoro GO jest wymagane to można by o tym poinformować. Po drugie próba uruchomienia skryptu z takim samym błędem, ale tworzącego funkcję nie powiedzie się z powodu takiego błędu:

Msg 156, Level 15, State 1, Procedure fn_Fun, Line 8
Incorrect syntax near the keyword 'GRANT'.

Mała rzecz ale na wszelki wypadek dobrze o tym wiedzieć.

Code Retreat

Home

O Code Retreat, czyli swego rodzaju warsztatach programistycznych, usłyszałem po raz pierwszy całkiem niedawno, kiedy dyrektor działu, w którym pracuję, rzucił pomysł zorganizowania czegoś takiego w firmie. Od pomysłu do realizacji nie minęło dużo czasu i w ostatnią sobotę wraz z kolegami i koleżankami z pracy (około 20 osób) wzięliśmy udział w takich warsztatach prowadzonych przez Michała Taszyckiego.

Z czym to się je? Celem Code Retreat jest wymiana wiedzy pomiędzy uczestnikami warsztatów oraz nauka nowych rzeczy, których na co dzień nie używa się w pracy. Warsztaty takie składają się z kilku krótkich sesji, w moim przypadku było to 6 sesji po 45 minut, podczas których rozwiązuje się jakieś problemy programistyczne. Pracowaliśmy w parach i co jakiś czas wymienialiśmy się klawiaturą. W czasie każdej z sesji pary były różne, a ponieważ w wydarzeniu brali udział programiści C# i Java, czasami trzeba było programować w języku, którego nie używa się na co dzień.

Tematem przewodnim tego Code Retreat była gra w życie. W czasie każdej z sesji mieliśmy za zadanie zaprogramować taką grę, ale za każdym razem wymagania na metodykę pracy i użyte techniki programistyczne były inne. Co istotne, każda sesja kończy się usunięciem całego kody. Pogrubienie oznacza fizyczne, trwałe usunięcie kodu, a więc za każdym razem pracę rozpoczynaliśmy się od początku.

Należy podkreślić, że celem nie jest tak naprawdę napisanie działającej gry. Temat nie jest trudny, ale 45 minut to nie jest dużo czasu zważywszy na to, że przy okazji uczymy się nowych rzeczy. Główny cel to nauka, nauka i jeszcze raz nauka, w sprzyjających warunkach i bez stresu, a gra w życie czy inne zadanie to tylko pretekst.

Czego się nauczyłem? W czasie jednej z sesji mieliśmy na przykład zastosować czysto purystyczne podeście to Test Driven Development, czyli nie mogliśmy napisać linijki kodu bez testów. W innej sesji programując nie mogliśmy w ogóle używać myszki, no ewentualnie po to aby raz sprawdzić skrót i potem już go używać. W jeszcze innej sesji pisany kod powinien zawierać minimalną liczbę klauzul sterujących if, a najlepiej w ogóle itd. Zadania mogą być najróżniejsze.

Czy purystyczne trzymanie się TDD jest dobre? Uważam, że nie. Czy używanie tylko i wyłącznie klawiatury nie jest przesadę? Uważam, że dobrze znać skróty klawiaturowe i starać się minimalizować używanie myszki ale ona się też się przydaje. Czy programowanie bez if'ów ma sens, czy tak w ogóle się da? Ano da się, nie jest to może proste, ani oczywiste ale da się.

Zadania z takimi skrajnymi wymaganiami wyrywają jednak z rutyny, pokazują, że coś można zrobić inaczej, pobudzają do myślenia, rozszerzają horyzonty i to jest moim zdaniem SUPER. Niewątpliwą zaletą jest również integracja zespołu. Co by nie mówić, Code Retreat to po prostu świetna zabawa.

Podsumowując jestem bardzo zadowolony z udziału w Code Retreat. Przyznam, że początkowo byłem trochę sceptyczny, nie wiedziałem czego tak naprawdę się spodziewać, ale nie żałuję ani minuty spędzonej w sobotę w biurze :), w czym niewątpliwą zasługę ma również prowadzący Michał Taszycki.

Polecam Code Retreat!!!