Showing posts with label programowanie. Show all posts
Showing posts with label programowanie. Show all posts

12/09/2013

Nullable<T>.Equals(T value) 2

Home

Pytanie o opinię na temat Nullable<T>.Equals(T value) z poprzedniego postu zadałem również na portalu stackoverflow. Jeden z odpowiadających bardzo słusznie zwrócił uwagę, że opisany przeze mnie "problem" nie dotyczy tylko typu Nullable<T>. Aby przekonać się o czym mowa uruchomcie następujący kod:
Console.WriteLine((2m).Equals(2));
Console.WriteLine((2).Equals(2M));
Pierwsza myśli to 2xTrue ale poprawny wynik to True, False. Dzieje się tak ponieważ istnieje niejawna kowersja z typu int na decimal ale nie na odwrót. Czyli w pierwszym przypadku zostanie użyta metoda Equals(decimal value), a w drugim Equals(object value) A piszę o tym ponieważ to jedna z tych rzeczy, o których bardzo łatwo zapomnieć.

11/09/2013

Nullable<T>.Equals(T value)

Home

Po dłuższej urlopowej przerwie w blogowaniu zacznę od zagadki z serii co zostanie wypisane na ekran, którą podsunął mi kolega Przemek:
decimal d = 2;

Console.WriteLine("d == 2 = {0}", d == 2);
Console.WriteLine("d == (decimal)2 = {0}", d == (decimal)2);

Console.WriteLine("d.Equals(2) = {0}", d.Equals(2));
Console.WriteLine("d.Equals((decimal)2) = {0}", d.Equals((decimal)2));
Tutaj jeszcze nie ma haczyka i odpowiedź to 4XTrue. Zmieńmy jednak jedną liniję:

decimal? d = 2;

Tym razem odpowiedź jest mniej oczywista. Na ekran zostanie wypisane: True, True, False, True. Czym więc różni się pierwsze wywołanie Equals od drugiego?

W obu przypadkach wołana jest metoda wirtualna. W obu przypadkach metoda ta wołana jest dla struktury Nullable<T>. Zmienna d nie jest null'em, a więc to też nie jest problemem. Spójrzmy zatem jak zaimplementowano Equals dla Nullable<T>:
public override bool Equals(object other)
{
    if (!this.HasValue)
    {
        return (other == null);
    }
    if (other == null)
    {
        return false;
    }
    return this.value.Equals(other);
}
Nic skomplikowanego, jeśli zmienna jest ustawiona to ponownie wywoływana jest metoda Equals w tym przypadku Decimal.Equals Odpowiedzi musimy szukać więc dalej. Wszystkie typy numeryczne mają przeciążoną metodę Equals w następujący sposób:
public override bool Equals(object value)
public override bool Equals(decimal value)
Która z nich zostanie wywołana w tej sytuacji? Nullable<T>.Equals ma parametr typu object, a więc Decimal.Equals(object value) pasuje lepiej niż Decimal.Equals(decimal value). Ta pierwsza działa natomiast w ten sposób, że jeśli przekazany parametr nie jest typu decimal to zawsze zwraca false nie sprawdzając czy przekazany obiekt można bezpiecznie konwertować na decimal. I ot cała tajemnica ;)

Moim zdaniem działanie Nullable<T> nie jest teraz intuicyjne. Wzorując się na typach numerycznych, można by dopisać do Nullable<T> jeszcze jedną metodę:
public bool Equals(T other)
{
    if (!this.HasValue)
        return false;

    return this.value.Equals(other);
}
Z jakiegoś powodu tego nie zrobiono. Przeoczenie czy celowe działanie? Jestem ciekawy Waszych opinii.

28/07/2013

Ciekawa metoda obliczenia pierwiastka kwadratowego

Home

Istnieje wiele metod wyznaczania pierwiastka kwadratowego z liczb naturalnych. Ja napiszę o jednej, która mnie ostatnio urzekła i pokazuje piękno matematyki.

Otóż, wynikiem zastosowania tej metody jest ułamek, który stanowi przybliżenie pierwiastka z danej liczby. Dlaczego tylko przybliżenie? Pierwiastki kwadratowe z liczb naturalnych, nie będących kwadratem innej liczby naturalnej, są liczbami niewymiernymi. Liczb niewymiernych nie da się natomiast zapisać w postaci ułamka.

Metoda ta opiera się o tzw. ułamki łańcuchowe (ang. continued fraction). W skrócie chodzi o to, aby pierwiastek kwadratowy z danej liczby przedstawić w następujący sposób:
sqrt(S) = a0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + 1 / (...))))
Nim dłuższa sekwencja tym otrzymamy dokładniejsze przybliżenie. Co bardzo ciekawe, dla każdej liczby niewymiernej sekwencja wartości a0, a1, a2... w pewnym momencie stworzy cykl. Na przykład dla sqrt(2) sekwencja ta ma postać:
[1, 1, 2, 1, 2, ...]
Natomiast dla sqrt(53):
[7, 3, 1, 1, 3, 14, 3, 1, 1, 3, 14, ...].
Jak wyznaczyć taką sekwencję? Algorytm nie jest bardzo skomplikowany i można go zapisać w kilkunastu liniach kodu. Nie będą go jednak tutaj przytaczał, ponieważ doskonały opis znajduje się już na Wikipedii. Zachęcam do wypróbowania swoich sił i jego zaimplementowania.

Skorzystać możemy również z silnika Wolframalpha. Komenda continued fraction sqrt(X) zwróci nam rozwinięcie pierwiastka z danej liczby X w postaci ułamka łańcuchowego. Natomiast komenda convergents[sqrt(X),N] obliczy N pierwszych przybliżeń pierwiastka z danej liczby X w oparciu o opisaną metodę.

Metoda ta z pewnością może przydać się w obliczeniach naukowych, kiedy bardzo istotna jest precyzja obliczeń i operacje na zmiennym przecinku są niedopuszczalne. W takim przypadku powinniśmy wyznaczyć odpowiednio dokładne przybliżenie sqrt(x) w postaci ułamka.

Na przykład ułamek sqrt(3) ~= 13623482 / 7865521 da nam tyle samo poprawnie obliczonych cyfr po przecinku co Math.Pow(3, -0.5). W tym przypadku sekwencja a0, a1, a2... miała 25 elementów. Każdy dodatkowy element sekwencji da nam większą precyzję. W skrajnym przypadku możemy skorzystać ze struktury BigInteger do reprezentacji licznika i mianownika.

Jeśli temat Was zainteresował to polecam rozwiązanie zadania 64, 65 lub 66 ze strony Project Euler.

21/07/2013

Przykład przeglądu kodu i co z tego wynikło

Home

Jakiś czas temu robiłem przegląd kodu i zwróciłem uwagę na taki fragment implementacji:
public class SrvObject
{
   public int Id { get; set; }
   public string Code { get; set; }
   ...
}
...
private Dictionary<int, SrvObject> _cache = new Dictionary<int, SrvObject>();
...
if (_cache.Values.Any(x => x.Code == codeToFind))
{
   var obj = _cache.Values.FirstOrDefault(x => x.Code == codeToFind);
   ...
}
else
{
   var obj = ReadObject(codeToFind);
   _cache.Add(obj.Id, obj);
   ...
}
Zacznijmy od tego, że mamy klasę, która modeluje jakąś encję z bazy danych i ta encja posiada zarówno identyfikator (wewnętrzny dla systemu) oraz kod, który można na przykład wyświetlić użytkownikowi.

Programista użył słownika, z kluczem w postaci identyfikatora, aby buforować już odczytane z bazy danych encje. Pierwsza rzecz jaka rzuca się w oczy to fakt, że kluczem jest identyfikator, a my wyszukujemy na podstawie kodu co wymaga iterowania po wszystkich zgromadzonych w słowniku obiektach. Wynika to z tego, że w większości przypadków posługujemy się identyfikatorem, a tylko czasami kodem i wspomniany kod został dodany później.

Załóżmy przez chwilę, że jest to ok. Druga rzecz na jaką należy zwrócić uwagę to fakt użycia metody Any i zaraz potem użycie FirstOrDefault. Jest to zbyteczne, kod ten robi dwa razy to samo, wystarczy zastosować tylko FirstOrDefault.

Wróćmy teraz do przeszukiwania słownika na podstawie kodu. Przy pokazanej implementacji musimy w najgorszym wypadku sprawdzić wszystkie obiekty w słowniku co ma złożoność liniową. Przy dużej liczbie obiektów w słowniku i częstych odwołaniach do niego jest to nieefektywne. W takim wypadku należy wprowadzić drugi słownik, w którym kluczem będzie kod. W zależności od sytuacji będziemy używać jednego albo drugiego słownika. Jeśli nie znajdziemy w którymś słowniku szukanego obiektu to dodajemy go do OBU słówników.

Przeprowadziłem mały test obu rozwiązań. Najpierw napisałem trzy metody wyszukujące encje:
  • Znajdź na podstawie identyfikatora
  • Znajdź na podstawie kodu bez dodatkowego słownika
  • Znajdź na podstawie kodu z dodatkowym słownikiem
Początkowo słowniki są puste i generuję pewną liczbę N losowych identyfikatorów i kodów. Następnie znajduję te identyfikatory i kody korzystając z jednego słownika (Znajdź na podstawie identyfikatora + Znajdź na podstawie kodu bez dodatkowego słownika) oraz z dwóch słowników (Znajdź na podstawie identyfikatora + Znajdź na podstawie kodu z dodatkowym słownikiem). Oto wyniki:

Liczba N Liczba unikalnych identyfikatorów Czas (ms) dla dwóch słowników Czas (ms) dla jednego słownika
100 63 3 4
500 320 2 4
1000 639 2 6
5000 3169 2 96
10000 6326 4 370
50000 31579 14 9190

Czas mierzyłem dla trybu Release. Jak widać nawet dla małej liczby elementów dwa słowniki są szybsze i to pomimo konieczności zarządzania jednym słownikiem więcej. Dla dużej liczby elementów przewaga jest miażdżąca. Jest to kolejny przykład, jak ważne są dobrze dobrane struktury danych.

Na koniec zwrócę jeszcze uwagę, że dwa słowniki oznaczają większe zapotrzebowanie na pamięć. W moich eksperymentach dwa słowniki dla 10 tyś elementów zużyły ~0.5MB więcej pamięci niż 1 słownik, dla 50 tyś elementów ~1.3 MB więcej, a dla 100 tyś elementów ~3.3 MB więcej.

07/07/2013

TPL Dataflow + problem filozofów

Home

Jakiś czas temu na blogu Piotrka Zielińskiego przeczytałem o TPL Dataflow Library czyli o bibliotece dostarczającej komponentów ułatwiających komunikację (przekazywanie danych) w środowisku wielowątkowym. Temat mnie zaciekawił i postanowiłem trochę pobawić się z tą technologią. Na tapecie nie miałem żadnego "prawdziwego" projektu, w którym dałoby się wykorzystać nową zabawkę, postanowiłem więc wykonać ćwiczenie umysłowe i rozwiązać klasyczny problem pięciu filozofów z użyciem TPL Dataflow.

W moim rozwiązaniu każda pojedyncza pałeczka do jedzenia ryżu reprezentowana jest przez instancję klasy BufferBlock<T&gt gdzie T to w tym przypadku klasa Chopstick (klasa wydmuszka, nie zawiera żadnych właściwości ani metod). BufferedBlock<T>to nic innego jak kolejka FIFO, która może mieć wielu czytelników i wielu zapisujących.

Filozof potrzebuje jednak dwóch pałeczek aby rozpocząć jedzenie. Aby spełnić to wymaganie używam klasy JoinBlock<T,Z> gdzie T i Z do znowu klasa Chopstick. JoinBlock działa w ten sposób, ze monitoruje dwa źródła danych i jeśli w obu źródłach równocześnie są dane to grupuje je i wysyła do słuchacza. W tym przypadku JoinBlock czeka na dwie wolne pałeczki.
var chopsticks = new JoinBlock<Chopstick, Chopstick>(new GroupingDataflowBlockOptions { MaxNumberOfGroups = 1 });

_left.LinkTo(chopsticks.Target1);
_right.LinkTo(chopsticks.Target2);

_chopsticks = chopsticks.Receive();
Ustawienie właściwości MaxNumberOfGroups jest konieczne, aby blok odczytał tylko dwa komunikaty. Odłożenie pałeczek na stół jest natomiast równoważne z wysłaniem komunikatu (pałeczki) z powrotem do bufora tak, aby oczekujący na nie filozofowie mogli rozpocząć jedzenie.
_left.SendAsync(_chopsticks.Item1);
_right.SendAsync(_chopsticks.Item2);
Do tego, aby filozofowie mogli informować świat zewnętrzny o tym, co robią, również użyłem klasy BufferBlock<T>. Za każdym razem kiedy jeden z filozofów kończy/rozpoczyna jedzenie wysyła komunikat ze swoim aktualnym stanem. Ja napisałem prostą aplikację w WinForms, która nasłuchuje na te komunikaty i odpowiednio uaktualnia UI.
private readonly BufferBlock<PhilosopherState> _philosophersState = new BufferBlock<PhilosopherState>();
...
_philosophersState.LinkTo(new ActionBlock<PhilosopherState>(state => UpdateState(state)), new DataflowLinkOptions());
Każdy filozof modelowany jest przez instancję klasy Philosopher i działa w swoim własnym wątku. Co jakiś losowy czas decyduje, co robić dalej tj.: kontynuować myślenie/jedzenie czy rozpocząć myślenie/jedzenie. Kiedy zbierzemy to wszystko do kupy, otrzymamy następujący kod.

Pokaż/Ukryj kod klasy Philosopher
namespace PhilosopherProblemWithDataFlows
{
    public class Philosopher
    {
        private const int SleepTime = 100;

        private readonly int _index;
        private readonly BufferBlock<Chopstick> _left;
        private readonly BufferBlock<Chopstick> _right;
        private readonly BufferBlock<PhilosopherState> _philosophersState;

        private bool _goHome;
        private Tuple<Chopstick, Chopstick> _chopsticks;

        public Philosopher(int index, BufferBlock<Chopstick> left, BufferBlock<Chopstick> right, BufferBlock<PhilosopherState> philosophersState)
        {
            _index = index;
            _left = left;
            _right = right;
            _philosophersState = philosophersState;
        }

        public void TakeASeat()
        {
            var rand = new Random((int)DateTime.Now.Ticks);

            while (true)
            {
                if (_goHome)
                {
                    PutChopsticks();                
                    return;
                }

                if (rand.Next() % 2 == 0)
                    Eat();
                else
                    Think();

                Thread.Sleep((rand.Next(10) + 1) * SleepTime);
            }
        }

        public void GoHome()
        {
            _goHome = true;
        }

        private void Eat()
        {
            if (_chopsticks == null)
            {
                var chopsticks =
                    new JoinBlock<Chopstick, Chopstick >(new GroupingDataflowBlockOptions { MaxNumberOfGroups  = 1 });

                _left.LinkTo(chopsticks.Target1);
                _right.LinkTo(chopsticks.Target2);

                _chopsticks = chopsticks.Receive();
                chopsticks.Complete();
            }

            _philosophersState.SendAsync(new PhilosopherState { Index = _index,  IsEating = true });
        }

        private void Think()
        {
            PutChopsticks();

            _philosophersState.SendAsync(new PhilosopherState { Index = _index,  IsEating = false});
        }

        private void PutChopsticks()
        {
            if (_chopsticks != null)
            {
                _left.SendAsync(_chopsticks.Item1);
                _right.SendAsync(_chopsticks.Item2);
                _chopsticks = null;
            }
        }
    }

    public class Chopstick
    {
    }

    public class PhilosopherState
    {
        public int Index { get; set; }
        public bool IsEating { get; set; }
    }
}
Pokaż/Ukryj kod okna Win Forms
namespace PhilosopherProblemWithDataFlows
{
    public partial class Form1 : Form
    {
        private readonly Color EatingColor = Color.Red;
        private readonly Color ThinkingColor = Color.Green;

        private readonly List<Label> _stateLabels = new List<Label>();
        private readonly List<Philosopher> _philosophers = new List<Philosopher>();
        private readonly BufferBlock<PhilosopherState> _philosophersState = new BufferBlock<PhilosopherState>();

        public Form1()
        {
            InitializeComponent();
            Closing += (sender, args) =>
                {
                    _philosophersState.Complete();
                    _philosophers.ForEach(p => p.GoHome());
                };

            _stateLabels.Add(philosopher1);
            _stateLabels.Add(philosopher2);
            _stateLabels.Add(philosopher3);
            _stateLabels.Add(philosopher4);
            _stateLabels.Add(philosopher5);
            _stateLabels.ForEach(l => l.BackColor = ThinkingColor);
            
            Start();
        }

        private void Start()
        {
            _philosophersState.LinkTo(new ActionBlock<PhilosopherState>(state => UpdateState(state)), new DataflowLinkOptions());

            var chopsticks = new[]
                {
                    new BufferBlock<Chopstick>(),
                    new BufferBlock<Chopstick>(),
                    new BufferBlock<Chopstick>(),
                    new BufferBlock<Chopstick>(),
                    new BufferBlock<Chopstick>()
                };

            foreach (var ch in chopsticks)
                ch.Post(new Chopstick());

            for (var i = 0; i < 5; ++i)
                _philosophers.Add(new Philosopher(
                            i,
                            chopsticks[i],
                            chopsticks[(i + 1) % 5],
                            philosophersState));

            for (var i = 0; i < 5; ++i)
            {
                var th = new Thread(_philosophers[i].TakeASeat);
                th.Start();
            }
        }

        private void UpdateState(PhilosopherState state)
        {
            var label = _stateLabels[state.Index];
            label.Invoke((MethodInvoker)delegate { label.BackColor = state.IsEating ? EatingColor : ThinkingColor; });
        }
    }
}

Kod designer'a pominąłem bo jest trywialny i zawiera tylko 5 etykiet o nazwach philosopher1, philosopher2 itd.

Na koniec mała zagadka. Moja implementacja zawiera pewne uproszczenie oryginalnego problemu 5 ucztujących filozofów. Jakie?

08/06/2013

Project Euler

Home

Po raz pierwszy o Project Euler usłyszałem już tak dawno temu, że nie pamiętam kiedy ale dopiero ostatnio założyłem konto i rozpocząłem zabawę. W skrócie jest to zestaw zadań matematyczno programistycznych (obecnie ponad 400) o różnym stopniu złożoności i trudności. Rozwiązanie zadania polega na podaniu zawsze jednej liczby np.: liczba cyklicznych liczb pierwszych poniżej 1 miliona. Część problemów można rozwiązać siłowo ale nim dalej w las tym trudniej i trzeba kombinować.

Do założenia konta zachęcił mnie kolega z pracy (Dzięki Piotrek!). Okazało się, że w zabawie bierze udział już kilku z nas. Witryna projektu umożliwia śledzenie postępów innych, dyskusję na temat problemów, podaje statystyki ile osób rozwiązało poszczególne zadania itd.

Do tej pory korzystałem z konkurencyjnego portalu TopCoder. Co przyciągnęło mnie do Project Euler? Sądzę, że kilka rzeczy:
  • Proste reguły zabawy.
  • Bardzo prosty interfejs.
  • Element społecznościowy.
  • Stopniowanie trudności. Można zacząć od bardzo prostych problemów i przechodzić do coraz trudniejszych.
  • Krótkie i zwięzłe zadania, co nie znaczy, że zawsze proste.
  • To coś.
Nie mówię, że TopCoder jest gorszy. Jest po prostu innych. Dla mnie Project Euler to czysta, nieskomplikowana zabawa. TopCoder ma wyższy próg wejścia ale z drugiej strony daje dużo więcej np.: nagrody pieniężne.

Podsumowując, jeśli jeszcze nie próbowaliście to zachęcam. Ja spróbowałem i nie mogę się oderwać.

05/06/2013

Microsoft.Office.Interop

Home

Będzie krótko i zwięźle, temat nie jest pasjonujący ale może komuś oszczędzi trochę nerwów. Ostatnio zdarzyło mi się pracować z kodem używającym Microsoft.Office.Interop do generacji dokumentów programu Word. Kod do najpiękniejszych nie należał ale najwięcej problemów miałem z interoperacyjnością.

Pierwszy błąd napotkałem po otwarciu dokumentu i próbie ustawienia właściwości MailMerge.MainDocumentType lub jak się później okazało dowolnej innej. Ten błąd to:

This command is not available because no document is open.

Przyczyną błędu okazał się brak katalogu C:\Windows\System32\config\systemprofile\Desktop. W moim przypadku po prostu skopiowałem analogiczny katalog C:\Windows\SysWOW64\config\systemprofile\Desktop i błąd przestał występować. Drugi błąd jaki napotkałem to:

Programmatic access to Visual Basic Project is not trusted.

Na początku spróbowałem więc zaznaczyć odpowiednią opcję w programie Word:

Word Options -> Trust Center -> Trust Center Settings -> Trust access to the VBA project object model

Niestety ale to nie pomogło. Skoro nie można po dobroci to skorzystałem z rozwiązanie "siłowego" i dodałem odpowiedni klucz do rejestru:

[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Office\14.0\Word\Security]
"AccessVBOM"=dword:00000001


Problemy te zaobserwowałem na Windows 7 Professional dla Microsoft Word 2010.

14/05/2013

Przeszukiwanie przestrzeni stanów 5

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Przeszukiwanie przestrzeni stanów to podejście, które pozwala rozwiązać bardzo wiele problemów. Należy jednak uważać, ponieważ siłą rzeczy wymaga sprawdzenia wielu ścieżek w drzewie/grafie stanów, co może trwać bardzo długo. W końcu uzyskamy poprawny wynik, ale po co czekać skoro dla niektórych problemów rezultat można uzyskać dużo szybciej. Spójrzmy na to zadanie.

Dana jest liczba N (z przedziału od 1 do 1000000) płytek domina. Każda płytka składa się z 2 połówek. Każda połówka zawiera liczbę z przedziału od 1 do 100. Dwie płytki domina pasują do siebie jeśli na jednej z połówek zawierają tą samą liczbę np.: płytka 1|10 pasuje do kostki 10|3 ale nie pasuje do kostki 4|5. Należy napisać program, który sprawdzi czy zadane płytki można ułożyć w łańcuch np.: 10|1 1|100 100|65 65|78...

Problem ten można rozwiązać w oparciu o strategię przeszukiwania przestrzeni stanów np.:
  • Definicji stanu początkowego - zbiór płytek.
  • Formuła/Akcje - Wyszukanie wszystkich płytek, które mogą zostać dopasowane do ostatniej płytki w łańcuchu. Dla każdej z nich należy wygenerować nowy stan czyli usunąć ze zbioru i dodać do łańcucha.
  • Warunku stopu - pusty zbiór płytek
  • Funkcja kosztu - brak.
Podejście to da poprawne rozwiązanie, ale dla dużych wartości liczby klocków N zajmie to niepraktycznie dużo czasu. Czemu? W tym podejściu każda płytka to węzeł grafu, który jest połączony z innymi klockami, do których pasuje. Rozwiązanie problemu to znalezienie ścieżki w grafie, która odwiedzi wszystkie jego węzły, ale każdy węzeł tylko raz. Innymi słowy szukamy ścieżki Hamiltona w grafie (rozwiązania problemu komiwojażera), który jest problemem z klasy NP.

Do problemy można podejść inaczej. Użyjmy modelu, w którym płytki reprezentowane będą jako krawędzie grafu, a nie węzły. W ten sposób otrzymamy graf o małej liczbie węzłów (tyle ile różnych liczb na połówkach płytek) i dużej liczbie krawędzi. Na przykład jeśli zbiór początkowy zawiera 1000 płytek postaci 3|57 to w nowej reprezentacji będziemy mieli 1000 krawędzi łączących węzły 3 i 57.

Przy takiej reprezentacji rozwiązanie problemu to znalezienie ścieżki w grafie, która przejdzie przez każdą krawędź tylko raz czyli znalezienie ścieżki Eulera, a to można zrobić w czasie wielomianowym. Aby w grafie istniała ścieżka Eulera muszą zostać spełnione następujące warunki (stopień węzła to liczba krawędzi wchodzących/ wychodzących do/z tego węzła):
  • Graf musi być spójny.
  • Co najwyżej dla jednego węzła spełnione jest (stopień wchodzący) - (stopień wychodzący) = 1
  • Co najwyżej dla jednego węzła spełnione jest (stopień wychodzący) - (stopień wchodzący) = 1
  • Dla wszystkich pozostałych węzłów stopień wchodzący jest taki sam jak stopień wychodzący.
20/05/2013:
Powyższe warunki dotyczą grafu skierowanego. Graf z płytkami jest natomiast grafem nieskierowanym, a więc powyższe warunki jeszcze się uproszczą.

Innymi słowy wśród wszystkich możliwych grafów są takie ich odmiany, dla których problem znalezienia ścieżki Hamiltona można sprowadzić do znalezienia ścieżki Eulera.

Przeszukiwanie przestrzeni stanów może być bardziej intuicyjne, ale zawsze warto zastanowić się dwa razy.

08/05/2013

Przeszukiwanie przestrzeni stanów 4

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Napisaliśmy już silnik przeszukiwania przestrzeni stanów. Teraz, przy jego pomocy, rozwiążemy problem statków, który stanowił początek naszych rozważań. Zacznijmy od klasy, która będzie przechowywała informacje o bieżącym stanie.

public class ShipsProblemData
{
    public Dictionary<string, Stack<string>> Ports { get; private set; }

    public Stack<string> CurrentPath { get; private set; }

    public ShipsProblemData()
    {
        Ports = new Dictionary<string, Stack<string>>();
        CurrentPath = new Stack<string>();
    }

    public ShipsProblemData Clone()
    {
        var state = new ShipsProblemData();

        foreach (var pair in Ports)
        {
            var stack = new Stack<string>();
            foreach (var target in pair.Value.Reverse())
                stack.Push(target);

            state.Ports[pair.Key] = stack;
        }

        foreach (var item in CurrentPath.Reverse())
            state.CurrentPath.Push(item);

        return state;
    }
}

Właściwość Ports to słownik, którego kluczami są nazwy portów, a wartości to dzienniki modelowane przy pomocy stosu. Właściwość CurrentPath przechowuje natomiast listę odwiedzonych już portów. Metoda Clone ułatwi nam generowanie nowych stanów. Właściwa definicja problemu wygląda tak:

public class ShipsProblem : Problem<ShipsProblemData>
{
    public override ShipsProblemData DataForInitialState
    {
        get
        {
            var data = new ShipsProblemData();

            var port1 = "Gdańsk";
            var port2 = "Szczecin";
            var port3 = "Kołobrzeg";

            data.CurrentPath.Push(port1);

            var book = new Stack<string>();

            book.Push(port2);
            book.Push(port1);
            book.Push(port3);
            book.Push(port2);
            book.Push(port1);
            book.Push(port3);
            data.Ports[port1] = book;

            book = new Stack<string>();

            book.Push(port3);
            book.Push(port1);
            book.Push(port1);
            book.Push(port3);
            book.Push(port1);
            book.Push(port1);
            data.Ports[port2] = book;

            book = new Stack<string>();

            book.Push(port2);
            book.Push(port3);
            book.Push(port2);
            book.Push(port2);
            book.Push(port3);
            book.Push(port2);
            data.Ports[port3] = book;

            return data;
        }
    }

    public override bool IsFinalState(State<ShipsProblemData> state)
    {
        return state.Data.Hosts.All(kvp => !kvp.Value.Any());
    }

    public override IList<State<ShipsProblemData>> Expand(State<MyData> state)
    {
        var newStates = new List<State<ShipsProblemData>>);

        var currentHost = state.Data.CurrentPath.Peek();
        foreach (var host in state.Data.Hosts.Keys)
        {
            if (state.Data.Hosts[host].Count > 0 && state.Data.Hosts[host].Peek() == currentHost)
            {
                var copy = state.Data.Clone();
                copy.Hosts[host].Pop();
                copy.CurrentPath.Push(host);

                newStates.Add(new State<ShipsProblemData> { Data = copy });
            }
        }

        return newStates;
    }
}

Stan początkowy można odczytać z pliku lub bazy danych, ale w naszym przypadku równie dobrze można go zaszyć w kodzie. Stan końcowy możemy wykryć bardzo łatwo, tj. wszystkie dzienniki powinny być puste. Generowanie nowych stanów też jest proste. W każdym kroku musimy znaleźć porty, z których mógł wypłynąć statek i przybić do portu bieżącego czyli takie, których dziennik zawiera na ostatnim miejscu bieżący port. Następnie kopiujemy dane i modyfikujemy je tak aby odpowiadały nowemu stanowi.

Nie pozostaje nic innego jak uruchomić silnik i uzyskać wynik.

var solver = new ProblemSolver<ShipsProblemData>();
var results = solver.SolveProblem(new DFSFringe<ShipsProblemData>(), new ShipsProblem ());

foreach (var res in results)
{
    Console.WriteLine(" ----------- Solution ----------- ");
    foreach (var data in res.ResultData)
        Console.WriteLine(data.CurrentPath.Peek());
    
}

04/05/2013

Przeszukiwanie przestrzeni stanów 3

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Zgodnie z obietnicą dzisiaj napiszę jak zaimplementować klasę Fringe i jakie to może mieć znaczenie. Dla przypomnienia potrzebujemy stworzyć kontener, który będzie przechowywał stany, które musimy jeszcze odwiedzić. Wynika to z tego, że przestrzeń stanów ma strukturę drzewiastą albo w ogólności grafową jeśli możliwe jest wrócenie do już odwiedzonego stanu. Węzły tego drzewa/grafu możemy odwiedzać w różnej kolejności, a co z tym związane w różnej kolejności je produkować. Kolejność ta zależy właśnie od implementacji klasy Fringe.

Zacznijmy od dwóch przykładowych implementacji.

public class DFSFringe<TCustomData> : Fringe<TCustomData>
{
    private readonly Stack<State<TCustomData>> _fringe = new Stack<State<TCustomData>>();

    public override int Count
    {
            get { return _fringe.Count; }
    }

    public override bool IsEmpty
    {
        get { return _fringe.Count == 0; }
    }

    public override State<TCustomData> Next
    {
        get { return _fringe.Pop(); }
    }

    public override void Add(State<TCustomData> s)
    {
        _fringe.Push(s);
    }
}

public class BFSFringe<TCustomData> : Fringe<TCustomData>
{
    private readonly Queue<State<TCustomData>> _fringe = new Queue<State<TCustomData>>();

    public override int Count
    {
            get { return _fringe.Count; }
    }

    public override bool IsEmpty
    {
        get { return _fringe.Count == 0; }
    }

    public override State<TCustomData> Next
    {
        get { return _fringe.Dequeue(); }
    }

    public override void Add(State<TCustomData> s)
    {
        _fringe.Enqueue(s);
    }
}

DFS oraz BFS to skróty od Depth-first search czyli przeszukiwania w głąb oraz Breadth-first search czyli przeszukiwania wszerz. DFSFringe opiera się na stosie, a BFSFringe na kolejce. Ma to ogromne znaczenie.

Zastosowanie stosu powoduje, że rozwijany jest najgłębszy jeszcze nie rozwinięty węzeł - stan, a jego następniki ustawiane są na początku zbioru stanów. Natomiast użycie kolejki powoduje, że rozwijany jest najpłytszy jeszcze nie rozwinięty węzeł, a jego następniki ustawiane są na końcu zbioru stanów.

DFS będzie więc, przeważnie, trzymał mniej stanów w pamięci niż BFS. Przy bardzo szerokich drzewach BFS może być wręcz niepraktyczny z powodu zbyt dużego zapotrzebowania na pamięć. Z drugiej strony, przy bardzo głębokich drzewach,  DFS może tracić czas na przeszukiwanie kolejnych gałęzi podczas gdy rozwiązanie będzie znajdować się dość płytko tj. niedaleko korzenia.

DFSFringe, BFSFringe to zresztą tylko dwa przypadki z wielu. Inne podejścia to min.: przeszukiwanie z równomiernym kosztem (ang. uniform-cost search), przeszukiwanie z ograniczoną głębokością (ang. depth-limited search), iteracyjne pogłębianie (ang. iterative deepening) czy przeszukiwanie zgodnie z zasadą najlepszy wpierw (an.g best-first search).

W kolejnym poście w końcu ;) rozwiążemy problem ze statkami.

30/04/2013

Przeszukiwanie przestrzeni stanów 2

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Implementacja przeszukiwania przestrzeni stanów powinna być możliwe ogólna, tak abyśmy mogli zastosować ją również dla innych problemów. Najpierw napiszmy klasę reprezentującą stan. Wygląda ona w następujący sposób:

public class State<TCustomData>
{
    public TCustomData Data { get; set; }

    public double Cost { get; set; }

    public State<TCustomData> Parent { get; internal set; }

    public IList<State<TCustomData>> Children { get; internal set; }
}

TCustomData to dowolna klasa, która przechowuje właściwe dane opisujące stan.

Teraz stwórzmy klasę Problem, która będzie miała trzy zadania: dostarczenie stanu początkowego, produkowanie nowych stanów i określenie kiedy znaleźliśmy stan końcowy. Wszystkie składowe tej klasy są abstrakcyjne, ponieważ ich implementacja zależy od rozwiązywanego problemy.

public abstract class Problem<TCustomData>
{
    public abstract TCustomData DataForInitialState { get; }

    public abstract bool IsFinalState(State<TCustomData> state);

    public abstract IList<State<TCustomData>> Expand(State<TCustomData> state);
}

Potrzebujemy jeszcze jednej klasy. Będzie ona odpowiedzialna za przechowywanie stanów, które musimy odwiedzić. Wracając do zadania ze statkiem. W pewnym momencie może być tak, że nie będziemy mogli jednoznacznie powiedzieć skąd przypłynął statek. Możliwości może być wiele i w najgorszym przypadku musimy sprawdzić je wszytskie. Innymi słowy ze stanu A możemy przejść do stanu B, C, D... i gdzieś te stany musimy zapamiętać.

public abstract class Fringe<TCustomData>
{
    public abstract State<TCustomData> Next { get; }

    public abstract int Count { get; }

    public abstract bool IsEmpty { get; }

    public abstract void Add(State<TCustomData> s);

    public void AddRange(IEnumerable<State<TCustomData>> data)
    {
        foreach (var s in data)
            Add(s);
    }
}

Klasa ta jest abstrakcyjna, ponieważ stany możemy odwiedzać w różnej kolejności co może mieć bardzo duże znaczenie, ale o tym później.

Napiszmy jeszcze jedną prostą klasę zanim przejdziemy do właściwego silnika, czyli klasę modelującą rozwiązanie. W tej implementacji rozwiązanie do sekwencja stanów od początkowego aż do końcowego:

public class Result<TCustomData>
{
    private readonly List<TCustomData> _resultData = new List<TCustomData>();

    public IList<TCustomData> ResultData
    {
        get { return _resultData; }
    }
}

Przygotowaliśmy już całą infrastrukturę. Zobaczmy więc silnik. Wbrew pozorom jest on bardzo prosty.

public class ProblemSolver<TCustomData>
{
    public IList<Result<TCustomData>> SolveProblem(Fringe<TCustomData> fringe, Problem<TCustomData> problem)
    {
        var initialState = new State<TCustomData> { Data = problem.DataForInitialState };
        fringe.Add(initialState);

        var res = new List<Result<TCustomData>>();
        while (!fringe.IsEmpty)
        {
            var next = fringe.Next;

            if (problem.IsFinalState(next))
            {
                res.Add(GetSolution(next));
            }
            else
            {
                next.Children = problem.Expand(next);
                foreach (var child in next.Children)
                    child.Parent = next;

                fringe.AddRange(next.Children);
            }
        }

        return res;
    }

    private static Result<TCustomData> GetSolution(State<TCustomData> state)
    {
        var res = new Result<TCustomData>();
        while (state != null)
        {
            res.ResultData.Add(state.Data);
            state = state.Parent;
        }

        return res;
    }
}

Rola silnika sprowadza się do dwóch zadań:
  1. Odwiedzanie kolejnych stanów i sprawdzanie czy są rozwiązaniem.
  2. Zapamiętywanie kolejno znalezionych rozwiązań.
W kolejnym poście napiszę więcej o możliwych implementacjach klasy Fringe.

27/04/2013

Przeszukiwanie przestrzeni stanów

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Zacznijmy od rozwiązania zadania z poprzedniego posta. Poprawna sekwencja portów to:

Gdańsk
Szczecin
Kołobrzeg
Szczecin
Gdańsk
Gdańsk
Kołobrzeg
Kołobrzeg
Szczecin
Gdańsk
Szczecin
Kołobrzeg
Szczecin
Gdańsk
Gdańsk
Kołobrzeg
Kołobrzeg
Szczecin
Gdańsk

Zapewne można do niej dojść stosując algorytm na chłopski rozum czyli:
  1. Wiemy, że ostatnim portem był Szczecin.
  2. Patrzymy więc na ostatnie wpisy w dziennikach z Gdańska i Kołobrzegu.
  3. Okazuje się, że do Szczecina statek przypłynął z Gdańska.
  4. Wykreślamy ten wpis.
  5. Patrzymy na ostatnie wpisy w dziennikach z Szczecina i Kołobrzegu.
  6. Okazuje się, że do Gdańska statek przypłynął z Kołobrzegu.
  7. Wykreślamy ten wpis.
  8. Patrzymy na ostatnie wpisy w dziennikach z Szczecina i Gdańska.
  9. Okazuje się, że do Kołobrzegu statek mógł przypłynąć Szczecina lub Gdańska i musimy rozważyć oba scenariusze.
  10. ...
Dla dużej liczby portów jest to zadanie karkołomne. Ja przy takich problemach stosuję przeszukiwanie przestrzeni stanów (ang. State space search), w skrócie PPS. Podejście to pozwala rozwiązać wiele problemów algorytmicznych, które pozornie wydają się bardzo trudne, w prosty sposób. Między innymi stosowane jest w uczeniu maszyn, warto więc je znać.

PPS zakłada, że problem reprezentujemy przy pomocy:
  • Definicji stanu początkowego.
  • Formuły, która powie nam jakie stany można odwiedzić, z bieżącego stanu. Albo inaczej zbioru akcji, które powodują zmianę stanu.
  • Warunku stopu, który powie nam czy znaleźliśmy rozwiązanie.
  • Opcjonalnie funkcji kosztu, która pozwala nam wybrać lepsze, bardziej optymalne rozwiązanie.
Na tej podstawie PPS znajduje sekwencję akcji prowadzących od stanu początkowego do rozwiązania. Dla opisanego przeze mnie problemy wygląda to tak:
  • Definicji stanu początkowego - port końcowy + stan dzienników.
  • Formuła/Akcje - Znalezienie listy portów, z których statek mógł przypłynąć do bieżącego portu. Wybranie portu oznacza dodanie go do listy już odwiedzonych portów oraz wykreślenie odpowiedniego wpisu z dziennika.
  • Warunku stopu - Wszystkie dzienniki są puste.
  • Funkcja kosztu - brak.
Stan to para składająca się z aktualnej listy odwiedzonych portów oraz aktualnego stanu dzienników. Mając definicję problemu możemy przejść do implementacji o czym napiszę w kolejnym poście.

26/04/2013

Zadanie do pogłówkowania

Home

Post ten stanowi pierwszy z serii, w której opisze podejście do rozwiązywania pewnej klasy problemów. W ostatnim czasie po raz kolejny zastosowałem to podejście do rozwiązania problemu, jaki napotkałem, i dlatego postanowiłem o tym napisać. Na początek proponuję zastanowić się nad takim zadaniem.

Treść zadania:

Załóżmy, że statek podróżuje pomiędzy pewną liczną N portów. Za każdym razem kiedy zawinie do portu jest to odnotowywane przez kapitanat w dzienniku. Kapitanat zapisuje również informacje o kolejnym docelowym porcie podróży.

Mając zbiór dzienników ze wszystkich portów, oraz port końcowy należy odtworzyć trasę podróży statku. Statek może wielokrotnie odwiedzać ten sam port. Statek może również wypłynąć z portu A i do niego wrócić.

Niestety dzienniki są prowadzone niechlujnie i nie możemy polegać na datach wpisów. Wpisy są natomiast ułożone chronologicznie w ramach dziennika, czyli jeśli wpis A jest wcześniej w danym dzienniku niż wpis B to znaczy, że statek najpierw odpłynął do A, wrócił po jakimś czasie i popłynął do B.

Przykład 1:

Rozważmy przypadek z 3 portami Szczecin, Gdańsk oraz Kołobrzeg. Portem końcowym jest Szczecin. Dzienniki dla pewnego statku wyglądają w następujący sposób:

SzczecinGdańskKołobrzeg
GdańskKołobrzegGdańsk
KołobrzegKołobrzegSzczecin
SzczecinGdańsk

Z dziennika dla Szczecina możemy odczytać, że statek najpierw odpłynął do Gdańska potem wrócił i odpłynął do Kołobrzegu itd.

Rozwiązanie 1:

Rozwiązaniem jest następująca trasa:

Szczecin
Gdańsk
Kołobrzeg
Gdańsk
Kołobrzeg
Szczecin
Kołobrzeg
Gdańsk
Szczecin

Teraz w ramach ćwiczeń, zanim opiszę swoje podejście, proponuję rozwiązać problem dla poniższych danych. Port końcowy to Gdańsk.

Przykład 2:

GdańskSzczecinKołobrzeg
SzczecinKołobrzegSzczecin
GdańskGdańskKołobrzeg
KołobrzegGdańskSzczecin
SzczecinKołobrzegSzczecin
GdańskGdańskKołobrzeg
KołobrzegGdańskSzczecin

23/03/2013

Migracja bazy danych w EF

Home

Już dawno temu pisałem o zastosowaniu RavenDB w swoim projekcie. Początkowo byłem zadowolony z tego wyboru ale jakiś czas temu zdecydowałem się przejść na Entity Framework + SQLCe. Czemu? To temat ta cały post, tak w skrócie to zirytowało mnie to, że RavenDB stara się być mądrzejszy od programisty oraz to jak trudno osiągnąć w nim niektóre rzeczy. Nie twierdzę, że RavenDB jest zły, ale tak jak inne dokumentowe bazy danych nie do wszystkiego się nadaje.

Wracając do tematu, przechodząc do EF zdecydowałem się wykorzystać podejście code first. Wcześniej tego nie próbowałem i muszę powiedzieć, że byłem bardzo zadowolony, migracja odbyła się w miarę bezboleśnie. Swoją drogą zaprocentowała początkowa decyzja aby ukryć technologię dostępu do danych za dobrze określonym interfejsem. Dzięki temu zmiany musiałem wprowadzić w niewielu miejscach. Nie ma jednak róży bez końców. Kiedy po jakimś czasie chciałem dodać nową właściwość do swoich encji otrzymywałem błąd:

The model backing the context has changed since the database was created...

Za pierwszym razem poradziłem sobie z tym tworząc bazę danych od początku i importując dane ale na dłuższą metę byłoby to uciążliwe. Zacząłem kombinować nad rozwiązaniem, które zmieniłoby schemat bazy danych przed użyciem EF. Wtedy natknąłem się na artykuł opisujący to zagadnienie i był to strzał w dziesiątkę. Oto krótki opis co zrobiłem:.
  • Dodałem nową właściwość do encji.
  • Zmodyfikowałem logikę biznesową.
  • Uruchomiłem Package Manager Console.
  • Jako Default project wybrałem projekt, z klasę dziedziczącą po DbContext. Jeśli takich klas jest więcej zostanie zgłoszony błąd.
  • Wydałem polecenie Enable-Migrations.
  • Do projektu został dodany katalog Migrations, a w nim klasa Configuration.
  • Wydałem polecenie Add-Migration tj. Add-Migration AddColumn.
  • W projekcie została utworzona klasa AddColumn dziedzicząca po DbMigration. Dla mnie interesujące była metoda Up, w której umieściłem kod odpowiedzialny za uaktualnienie bazy danych. Wyglądało to w następujący sposób:

    public override void Up()
    {
       AddColumn("TranslationEntities", "Translation2", c => c.String(true, maxLength: 4000, storeType: "nvarchar"));
    }
    

    Metoda AddColumn to metoda klasy DbMigration. Jest ich dużo więcej np.: AddForeignKey, CreateIndex czy RenameColumn.
  • Na koniec użyłem klasy MigrateDatabaseToLatestVersion w celu zainicjowania bazy danych:

    Database.SetInitializer(new MigrateDatabaseToLatestVersion<ExpressionsDataContext, Configuration>());

  • Przy kolejnym uruchomieniu aplikacji zadziały się dwie rzeczy. Do tabelki TranslationEntities została dodana nowa kolumna oraz utworzona została nowa tabela __MigrationHistory. Dzięki tej nowej tabelce EF będzie śledził historię wprowadzanych zmian i nie uruchomi tej samej migracji więcej niż raz.
To bardzo prosty przykład. Jestem ciekawy jak ta funkcjonalność spisuje się w bardziej skomplikowanych scenariuszach. Czy macie jakieś doświadczenia?

22/03/2013

Konwencja wołania

Home

Konwencja wołania (ang. Calling convention) to zestaw zasad, który określa w jaki sposób metoda wołająca przekazuje parametry do metody wołanej i odbiera od niej wyniki. Programując w .NET, o ile nie współpracujemy z kodem natywnym, w ogóle nie musimy się tym interesować. Zgłębiając ten temat można jednak nauczyć się kilku ciekawych rzeczy.

Zacznijmy od tego jakiej konwencji wołania używa CLR. Na to pytanie można odpowiedzieć na dwa sposoby. Odpowiedź "wysoko poziomowa" brzmi: CLR został zaimplemntowany jako maszyna stosowa i nie używa rejestrów, a więc parametry oraz wyniki zostaną przekazane na stosie. Oto prosty przykład, zacznijmy od klasy:

public class Test
{
        public string ReturnString(int i, bool b)
        {
            return i.ToString() + b.ToString();
        }

        public string ReturnString(Fun f)
        {
            return f.ToString();
        }
}

Teraz spójrzmy na kod w C# i odpowiadający mu kod IL, w którym użyto tych metod:

var t = new Test();

newobj instance void ConsoleApplication1.Test::.ctor()
stloc.0 

var res1 = t.ReturnString(10, true);

ldloc.0 
ldc.i4.s 10
ldc.i4.1 
callvirt instance string ConsoleApplication1.Test::ReturnString(int32, bool)
stloc.1 

var res2 = t.ReturnString(new Fun());

ldloc.0
newobj instance void ConsoleApplication1.Fun::.ctor()
callvirt instance string ConsoleApplication1.Test::ReturnString(class ConsoleApplication1.Fun)
stloc.2 

Istotne fragmenty zaznaczyłem na czerwono. ldloc.0 odpowiada za wrzucenie na stos obiektu, na rzecz którego zostanie wywołana metoda (this). Potem wrzucamy argumenty dla wołanej metody czyli ldc.i4.s 10 oraz ldc.i4.1. Po wywołaniu metody zdejmujemy natomiast wynik ze stosu i zapisujemy w zmiennej lokalnej o indeksie 1 przy pomocy komendy stloc.1. Dla drugiego wywołania wygląda to podobnie. Polecenie newobj tworzy nowy obiekt i umieszcza referencję do niego na stosie.

Czemu jednak CLR został zaimplementowany jako automat stosowy (maszyna wirtualna Java zresztą też), a rejestry pojawiają się dopiero kiedy program jest wykonywany i IL jest zamieniany na kod natywny? Otóż CLR to komercyjna implementacja VES (ang. Virtual Execution System). VES jest częścią standardu ECMA-335, który jest niezależny od docelowej architektury, a w szczególności nie wspomina nic o żadnych rejestrach. Dzięki temu konkretne implementacji standardu mogą używać rejestrów w dowolny sposób.

I tutaj dochodzimy do odpowiedzi "nisko poziomowej" na postawione pytanie, czyli jakiej konwencji używa kod natywny wygenerowany na podstawie IL dla Windows'a. Otóż jest to konwencja fastcall, w której na przykład dla architektury x86 dwa pierwsze parametry przekazywane są w rejestrach ECX oraz EDX. Więcej szczegółów na ten temat można znaleźć na blogu Joe Duffy'ego.

Od siebie dodam, że jeśli korzystamy z P/Invoke to domyślnie metody natywne wołane są przy pomocy konwencji Winapi, która w systemie Windows jest tożsama z Stdcall. Zachowanie to możemy zmienić przy pomocy właściwości CallingConvention atrybutu DllImportAttribute.

16/01/2013

Mono C# compiler as a service 3

Home

Ponownie wrócę do tematyki kompilowania C# w locie. Pisałem wcześniej, że potrzebowałem takiej funkcji aby użytkownicy mojej aplikacji mogli w dowolnym momencie zdefiniować własny algorytm obliczania odległości między dwoma wektorami.

Po kilku próbach już wiedziałem jak to zrobić, a chwilę później miałem już zaimplementowaną pierwszą wersję rozwiązania. Przyszła pora wypróbowania nowej zabawki na prawdziwych danych. Uruchomiłem więc aplikację, napisałem krótki skrypt i wystartowałem obliczenia. W tym momencie aplikacja zamarła i było widać, że pożera wszelkie dostępne zasoby. Spodziewałem się czegoś innego :). Skończyło się zabiciem aplikacji. Co zrobiłem nie tak?

Dane jakich użyłem zawierały kilkaset tysięcy wektorów. Oznacza to, że odległość między wektorami musiała zostać obliczona "dużoooooooooooooooooooooo" razy. Każda taka operacja powodowała wywołanie omówionej już metody Evaluator.Run, czyli za każdym razem ten skrypt był ponownie kompilowany, a to trochę trwa. Ziarnko do ziarnka, a zbierze się miarka jak mówi przysłowie. Co więcej każde wywołanie Evaluator.Run powoduje załadowanie do pamięci kolejnego dynamicznie utworzonego modułu. Moduły te są potem usuwane ale to też trwa. W ramach eksperymentu proponuję uruchomić pod kontrolą debugger'a taki kod:

var settings = new CompilerSettings();
var ev = new Evaluator(new CompilerContext(settings, new ConsoleReportPrinter()));

for (int i = 0; i < 1000; ++i)
 ev.Run("System.Console.WriteLine(\"Hello!\");");

Zamiast zobaczyć, że kod wykonuje się błyskawicznie, zaobserwujemy jak VS próbuje załadować symbole dla kolejnych modułów (komunikat w rodzaju Loading symbols for eval-120... na pasku stanu). Jeśli postawimy pułapkę wewnątrz pętli i otworzymy okno Modules to na liście znajdziemy np.: eval-100, eval-101, eval-102...

W takiej sytuacji skrypt należy skompilować raz, a potem wielokrotnie używać wyniku kompilacji. Służy do tego metoday Evaluator.Compile, która zwraca instancję klasy CompiledMethod. Jeśli chcemy wywołać tak przygotowany skrypt korzystamy z metody CompiledMethod.Invoke. Nic trudnego. Parametry do takiego skompilowanego skryptu można przekazać w dokładnie taki sam sposób jak opisałem w poprzednim poście. Po zmianach powyższy kod będzie wyglądał jak poniżej i wykona się błyskawicznie:

var settings = new CompilerSettings();
var ev = new Evaluator(new CompilerContext(settings, new ConsoleReportPrinter()));

var method = ev.Compile("System.Console.WriteLine(\"Hello!\");");

object o = null;
for (int i = 0; i < 1000; ++i)
 method.Invoke(ref o);

Na koniec dodam, że po zastosowaniu takiego zabiegu nie widzę różnicy w czasie odpowiedzi pomiędzy przypadkiem kiedy używam algorytmu osadzonego/wkompilowanego w aplikację, a algorytmu dostarczonego przez użytkownika.

13/01/2013

Mono C# compiler as a service 2

Home

Dzisiaj wrócę do tematu użycia języka C# jako języka skryptowego przy pomocy Mono.CSharp.dll i opiszę w jaki sposób przekazać parametry do takiego skryptu. Pominę podejście opierające się o wklejanie do skryptu string'owej reprezentacji takich parametrów i od razu przejdę do bardziej eleganckiego rozwiązania. Bazuje ono na tym co przeczytałem w tym poście.

Zaczynamy od utworzenia statycznej klasy ScriptContext, która posłuży nam do wymiany danych pomiędzy skryptem, a naszym programem.

namespace Scripting
{
    public static class ScriptContext
    {
        static ScriptContext()
        {
            Items = new Dictionary<string, object>();
        }

        public static object Result { get; set; }

        public static IDictionary<string, object> Items { get; set; }
    }
}

Użycie jej nie jest trudne. Mały przykład:

var settings = new CompilerSettings();
var ev = new Evaluator(new CompilerContext(settings, new ConsoleReportPrinter()));
            
//Informujemy silnik skryptowy gdzie została zdefiniowana klasa ScriptContext
ev.ReferenceAssembly(typeof(ScriptContext).Assembly);

//Ustawiamy parametry
ScriptContext.Items["param1"] = new List<string> { "Hello!", "Welcome!", "Hi!" };

ev.Run("using System;");
ev.Run("using Scripting;");
//Korzystamy z przekazanych parametrów
ev.Run("foreach(var s in (System.Collections.Generic.IEnumerable<string>)ScriptContext.Items[\"param1\"]) Console.WriteLine(s);");

Właściwość ScriptContext.Result dodałem aby nie musieć zastanawiać się kiedy wywołać metodę Evaluator.Run, a kiedy Evaluator.Evaluate. Zawsze używam tej pierwszej, zakładając, że wynik ze skryptu zwracany jest przy użyciu tej właściwości np.:

ev.Run("ScriptContext.Result = 1;");
Console.WriteLine(ScriptContext.Result);

Do szczęścia brakowało mi jednak jeszcze jednej rzeczy. Jak pokazuje pierwszy przykład musiałem użyć rzutowania do IEnumerable<string> aby cieszyć się silnie typowanym parametrem. Napisałem więc metody pomocnicze, które przygotowują silnie typowane parametry:

public static class ScriptingHelper
{
 public static StringBuilder PrepareParameters(IDictionary<string, object> parameters)
 {
  ScriptContext.Items = parameters;

  var sb = new StringBuilder();

  if (parameters != null)
  {
   foreach (var kvp in parameters)
   {
    var typeName = ExtractTypeName(kvp);

    sb.AppendFormat("var {0} = ({1}){2}.Items[\"{0}\"];", kvp.Key, typeName, typeof(ScriptContext).Name);
    sb.AppendLine();
   }
  }

  return sb;
 }

 private static string ExtractTypeName(KeyValuePair<string, object> kvp)
 {
  if (kvp.Value == null)
   throw new Exception("null parameters are not supported!");
   
  var type = kvp.Value.GetType();

  using (var provider = new CSharpCodeProvider())
  {
   var typeRef = new CodeTypeReference(type);
   return  provider.GetTypeOutput(typeRef);
  }
 }
}

Nic bardzo skomplikowanego ale warto zwrócić uwagę na użycie klasy CSharpCodeProvider. Dzięki niej uzyskuję poprawną, pełną nazwę typów, również tych generycznych. Gdybym na przykład dla listy int'ów spróbował użyć czegoś w rodzaju list.GetType().Name to w wyniku otrzymałbym List`1, co do rzutowania się nie nadaje. Wcześniejszy przykład można więc napisać teraz w taki sposób:

//Ustawiamy parametry
var parameters = ScriptingHelper.PrepareParameters(new Dictionary<string, object>
{
 {"param1", new <string> { "Hello!", "Welcome!", "Hi!" } }
});

ev.Run("using System;");
ev.Run("using Scripting;");
ev.Run(parameters.ToString());
//Korzystamy z przekazanych parametrów ale już bez rzutowania
ev.Run("foreach(var s in param1) Console.WriteLine(s);");

Wracając do mojej aplikacji, w której chciałem umożliwić użytkownikowi definiowanie własnych algorytmów obliczania odległości między wektorami. Dane wejściowe to oczywiście dwa wektory. Dzięki takiemu podejściu, zamiast zmuszać użytkownika to rzutowania parametrów na określony typ, używam konwencji czyli: wektor numer 1 znajduje się w zmiennej vector1 itd.

Klasa ScriptingHelper jest również doskonałym miejsce na dodawanie różnych innych "przydasiów" ułatwiających pracę użytkownikowi.

12/01/2013

Mono C# compiler as a service

Home

Od jakiegoś czasu pracuję nad aplikacją do generowania i analizowania wykresów rekurencyjnych. Temat sam w sobie jest bardzo ciekawy, więc może do niego wrócę w przyszłości, ale dzisiejszy post będzie o czymś innym.

Moja aplikacja między innymi wykonuje obliczenia na wektorach np.: oblicza różne odległości (euklidesową, Manhattan czy normę maksimum) między nimi. Dodawanie kolejnych algorytmów wymagało jednak każdorazowej rekompilacji aplikacji. Zacząłem więc szukać sposobu aby umożliwić użytkownikowi dodawanie własnych algorytmów w sposób dynamiczny. Innymi słowy potrzebowałem jakiegoś silnika skryptowego.

Początkowo pomyślałem o PowerShell'u, rozważałem również IronPython'a. Trafiłem jednak na krótki i treściwy post na temat biblioteki Mono.CSharp.dll, która stanowi część dobrze znanego projektu Mono. Opis wyglądał obiecująco dlatego postanowiłem wypróbować tą bibliotekę i był to strzał w dziesiątkę.

Jądrem biblioteki jest klasa Mono.CSharp.Evaluator, która służy do dynamicznego kompilowania i wykonywania kodu C#. Jej użycie jest wręcz trywialne. Oto prosty przykład Hello World!:

var settings = new CompilerSettings();
var ev = new Evaluator(new CompilerContext(settings, new ConsoleReportPrinter()));

ev.Run("using System;");
ev.Run("Console.WriteLine(\"Hello World!\");");

Użycie ConsoleReportPrinter powoduje, że wszelkie komunikaty kompilatora zostaną wypisane na ekran konsoli. Możemy też użyć klasy StreamReportPrinter, wtedy komunikaty zostaną zapisane do wskazanego strumienia. Klasa CompilerSettings pozwala natomiast skonfigurować różne aspekty pracy kompilatora. Kolejny prosty przykład pokazuje, jak zwrócić wynik ze skryptu:

ev.Run("Console.Write(\">\")");
ev.Run("var s = Console.ReadLine();");
var s = (string)ev.Evaluate("s;");

Ciekawe jest to, że możemy zmienić typ raz zadeklarowanej zmiennej np.:

ev.Run("int s = 1;");
ev.Run("Console.WriteLine(s);");
ev.Run("string s = \"Hello!\";");
ev.Run("Console.WriteLine(s);");
ev.Run("bool s = true;");
ev.Run("Console.WriteLine(s);");

Możliwe jest również zdefiniowanie klasy:

ev.Run("class Test { public string Fun(int i) { return \"Hello \" + i; } }");
ev.Run("Console.WriteLine(new Test().Fun(1));");

Załóżmy, że w oddzielnym projekcie mamy zdefiniowaną klasę Test2. Poniższy przykład pokazuje jak użyć jej w skrypcie:

ev.ReferenceAssembly(typeof(Test2).Assembly);
ev.Run("using TestLib;");
ev.Run("Console.WriteLine(new Test2().Welcome(\"Kate\"));");

Praca z klasą Mono.CSharp.Evaluator bardzo mi się podoba. To kawał dobrej roboty, zachęcam więc do wypróbowania. W kolejnych postach opiszę, jak w elegancki sposób przekazać argumenty do skryptu oraz kiedy warto skorzystać z metody Compile zamiast Run lub Evaluate.

Uwaga instalacyjna

Pisząc ten post korzystałem z wersji beta 3.0.3 Mono. Ostatnia dostępna stabilna wersja 2.10.9 zawiera bowiem błąd, który objawia się komunikatem:

Method 'Mono.CSharp.Location.ToString()' is security transparent, but is a member of a security critical type.

przy pierwszej próbie użycia klasy Evaluator.  Nie sprawdzałem ale możliwe, że z github'a można ściągnąć wersję bez tego błędu.

24/12/2012

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.

22/12/2012

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