LEd i nowa wersja MiKTeX

Home

Z MiKTeX'a czyli implementacji systemu składu tekstu TeX/LaTeX dla Windows'a oraz programu LEd wspomagającego pracę z TeX/LaTeX'em korzystam już od bardzo dawna. Ponieważ należą do osób, które nie wyczekują wszelkiego rodzaju aktualizacji z drżącym sercem i instaluję je dopiero kiedy jest mi to rzeczywiście potrzebne to do tej pory zadowalałem się wersją MiKTeX 2.5 i pewnie pracowałbym z nią jeszcze długo, gdyby nie okazało się, że nie jest już wspierana i nie mogą ściągnąć potrzebnych mi pakietów.

Pobrałem więc najnowszą wersję 2.9, zainstalowałem, zmieniłem ścieżkę w zmiennych środowiskowych, a także dostosowałem ustawienia LEd'a wskazując katalog z nową wersją Configuration->Options->Application->DVI Viewer->TeX Executables. Następnie uruchomiłem kompilację projektu i LEd bez ostrzeżenia wywalił się. Spróbowałem otworzyć projekt jeszcze raz ale tym razem nawet to było niemożliwe. Usunąłem, więc wszelkie stworzone pliki tymczasowe i spróbowałem jeszcze raz otworzyć projekt. Tym razem udało się ale tak czy inaczej kompilacja znowu się nie powiodła. Kilka kolejnych prób zakończyło się tak samo. W logu systemowym nie znalazłem żadnych błędów.

Zacząłem więc dokładnie przyglądać się konfiguracji LEd'a i okazało się, że przeoczyłem jedną opcję Configuration->Options->Application->DVI Viewer->TeX distribution. Ustawiona była na MiKTex2.5 co wydało mi się podejrzane. Na liście nie widziałem jednak opcji MiKTeX2.9 ale za to znalazłem opcję based on MiKTeX. Spróbowałem i zadziałało.

Mam nadzieję, że to oszczędzi komuś czasu i nerwów.

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

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.

Konferencja wewnątrz-firmowa 2

Home

Ostatnio napisałem o zorganizowanej przez siebie konferencji wewnątrz-firmowej. Teraz należy napisać o czym można było posłuchać. Oto lista 12 przygotowanych prezentacji, wszystkie moim zdaniem stały na wysokim poziomie. O jakości prezentacji niech świadczą bardzo dobre wyniki ankiet. Średnia ocena to 8.3 w skali od 1 do 10!

Albert Skłodowski - F# as a functional language for the .NET platform

An introduction to functional programming in .NET using F# language. Write simple code to solve complex problems!

Damiarz Orzechowski - Is C++ dead? What was added into C++ x11 standard in comparison to C# and .NET features

Summary of history behind latest C++ standard. Presentation of highlights of latest standard and comparison of features between C++ and C#/.NET.

Daniel Celeda - Software Project Survival Guide

Quick induction to the main factors of a successful software project.“Software projects succeed or fail based on how carefully they are planned and how deliberately they are executed. The vast majority of software projects can be run in a deterministic way that virtually assures success. If a project’s stakeholders understand the major issues that determine project success, they can ensure that their project reaches a successful conclusion.”

Kamil Langowski - Paradoxes and idiosyncrasies of probability

Simple math problems that are outstandingly controversial, but are nonetheless facts.

Marcin Wierzbicki - Financial instruments for dummies

The talk covers basic subjects from financial engineering field, starting with present value, fixed income securities, bond pricing, immunization and arbitrage, and finishing... after 1 hour :)

Marek Ryński - An introduction to the basics of Web Application Security - theoretical lecture

A review of available mechanisms used to ensure confidentiality, integrity and availability of information in Web Applications. The talk will cover different approaches to authentication, highlighting strong and weak solutions. A few words will be said about smart cards and biometrics. Hacking, injection attacks and social engineering are only buzz words to attract your attention on this abstract, but none of these things will be discussed.

Michał Komorowski - RavenDB as an example of document oriented databases. A history of application in my pet project.

NoSQL databases are a relatively new idea which is becoming more and more popular. In this presentation, I’ll focus on document oriented databases. I’ll discuss the topic on the example of RavenDB and my pet project LanguageTrainer which supports learning foreign languages.

Michał Rzeszutko - Dependency Injection patterns and best practices

An introduction to the subject of DI. The talk covers basic subjects - what it is DI and what are the benefits of using it, as well as the more advanced ones – how to use it properly (patterns) and what to avoid (anti-patterns).

Mikołaj Barwicki - Do IT the Toyota Way?

Toyota is an enterprise built on unique philosophy focused on manufacturing and process quality that is summarized in a set of statements referred to as “Toyota Way”. Is this what made Toyota the world’s largest car manufacturer? Are these statements applicable to software development organizations?

Paweł Kupis - Aspect-oriented programming on the example of PostSharp.

Short introduction to aspect-oriented programming concept, fast review of .NET aspect frameworks and PostSharp in action.

Przemek Wasylko - Command-query responsibility segregation: can we successfully separate read from write parts of the system?

Exploration of design pattern where different (often in a radical way) model and approach is used to update information than model used to read information. I will try to show how this affects system architecture and user interface experience. But does it really make engineer’s life easier? And software less prone to errors?

Tomasz Moska - Configuring SQL Server Instance for optimal performance

The talk will cover some good practices regarding configuration of SQL Server instance.

Konferencja wewnątrz-firmowa

Home

W jednym z ostatnich postów pisałem o zorganizowanym przez siebie Quiz'ie. Dzisiaj napiszę o innym pomyśle na powiew świeżości w pracy, czyli o konferencji wewnątrz-firmowej. Konferencję taką zorganizowałem pod koniec czerwca (jej pierwotnym pomysłodawcą był mój przełożony Mikołaj).

Trochę uprzedzając, był to strzał w dziesiątkę pod każdym względem, a więc czym prędzej biegnijcie do swoich przełożonych z propozycją zorganizowania takiego wydarzenia ;) Zacznijmy od spraw organziacyjnych, czyli jak się do tego zabrałem.

• Na początek ustaliłem szczegóły z przełożonymi, czyli kiedy taka konferencja może się odbyć i ile czasu można na nią poświęcić. My wybraliśmy ostatni tydzień czerwca i na każdą prezentację przeznaczyliśmy godzinę. W konferencji mógł wsiąść udział każdy i mógł zobaczyć dowolną ilość prezentacji, przy czym było jasno powiedziane, że praca ma priorytet, czyli jeśli jest pilne zgłoszenie to trzeba je obsłużyć.
• 4 miesiące przed konferencją rozesłałem prośbę o zgłaszanie tematów wraz z krótkim opisem. Na zastanowienie się dałem 1 miesiąc.
• Co bardzo ważne, tematyka prezentacji mogła być dowolna, również nietechniczna. Jedynym warunkiem było, że prelegent:
• Ma interesować się tematem.
• Musi mieć przynajmniej trochę przekonania :), że dla innych temat również będzie interesujący.
• W regularnych odstępach (to bardzo ważne) rozsyłałem przypomnienie, że zostało tyle, a tyle czasu na  zgłoszenia.
• Po zebraniu propozycji (około 30 prezentacji, ale każdy mógł zgłosić więcej niż 1) zorganizowałem głosowanie. Na oddanie głosu były 2 tygodnie i znowu należy o tym przypominać.
• Na konferencję wybrałem 12 najlepszych prezentacji, ale każdy prelegent miał przygotować tylko 1.
• Poinformowałem kolegów o wyniku głosowania.
• Aby prelegenci nie czekali do ostatniej chwili z przygotowaniami poprosiłem ich aby przesłali mi agendę miesiąc przed konferencją.
• Zarezerwowałem salę, rzutnik, laptop itp.
• Poprosiłem prelegentów o preferencje kiedy chcą wygłosić swoje prezentacje i przygotowałem harmonogram.
• Dwa tygodnie przed konferencją rozesłałem do wszystkich w firmie zaproszenie na poszczególne prezentacje.
• Tuż przed samą konferencją przygotowałem ankiety, wydrukowałem je i pociąłem.
• Sprawdziłem również czy laptop działa, czy współpracuje z rzutnikiem i co jest na nim zainstalowane. Oczywiście poinformowałem również prelegentów czego mogą się spodziewać po sprzęcie. Pomimo to, zgodnie z prawem Murphy'ego, nie obyło się bez niewielkich problemów technicznych.
• Na każdej prezentacji na stołach czekały długopisy i anonimowe ankiety. Ich wypełnienie było obowiązkowe.
• Po konferencji zebrałem od prelegentów materiały i umieściłem je na Wiki.
• Podliczyłem ankiety i rozesłałem je do prelegentów. Przy okazji zapytałem czy zgadzają się na publikację wyników. Wszyscy się zgodzili więc udostępniłem również wyniki ankiet.

Przed godziną zero wszystko było więc zapięte na ostatni guzik. Konferencja spodobała się chyba wszystkim. Ja jestem z niej bardzo zadowolony, zarówno jako organizator jak i prelegent. To wspaniała okazja do integracji zespołu, nauki nowych rzeczy i potrenowania swoich umiejętności prelegenta w sprzyjającym środowisku.

Za jakiś czas napiszę o czym można było posłuchać na konferencji.

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.

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.

Quiz - coś do poduszki

Home

W poprzednim poście napisałem o zorganizowanym przez siebie Quiz'ie wiedzy o .NET i szeroko pojętym programowaniu. Jeden z czytelników poprosił o udostępnienie pytań i odpowiedzi. Nie zrobiłem tego od razu ale w ostatni weekend znalazłem chwilę czasu na zebranie wszystkich pytań/odpowiedzi do kupy, ujednolicenie formatowania itp. Dokument w formacie PDF dostępny jest na moim dysku SkyDrive:



Przy okazji będę wdzięczny ze wszelkie komentarze. Czy treść pytań jest zrozumiała? Czy pytania były łatwe, trudne, a może w sam raz? Czy ich tematyka podoba się Wam? Czy wzięlibyście udział w takim Quiz'ie? Zwróćcie również uwagę na pytanie 23 przy którym niestety zaliczyłem wpadkę i zdecydowałem się je anulować. Jeśli ktoś z Was potrafi wyjaśnić moje wątpliwości zapraszam do komentowania.

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?

Quiz - rozruszaj towarzystwo

Home

Czy Wasza praca jest zawsze ciekawa i pełna wyznań, a może czasami Was nuży i zastanawiacie się jak ją urozmaicić?

Byłoby super gdyby każdy z nas mógł odpowiedzieć na to pytanie "Tak moja praca jest bardzo ciekawa i nigdy mnie nie nuży", ale w rzeczywistości bywa różnie. Zawsze można zmienić pracę, ale można również próbować zmienić coś w obecnej. Sceptycy pewnie powiedzą, a co ja mały trybik w wielkiej machinie mogę zrobić. Dużo zależy od firmy i bywają przypadki beznadziejne. Ja na rozruszanie zespołu proponuję zorganizować Quiz.

Ja postanowiłem coś takiego zrobić już po raz drugi w swojej karierze i jestem bardzo zadowolony z efektów. Odgórnym celem Quiz'u była zabawa i nauka. Zasady były proste:

• 10 tur po 3 pytania (łatwe, średnie i trudne) dotyczące szeroko pojętego programowania.
• Pytania przygotowałem za wczasu, tak aby nie musieć ich wymyślać co tydzień.
• Starałem się, aby odpowiedzi można było udzielić w jednym zdaniu, czasem wręcz jednym słowem, ewentualnie napisać kilka linijek kodu.
• Pytania rozsyłałem w poniedziałek rano i czekałem na odpowiedzi do końca dnia. Następnego dnia oceniałem wyniki, rozsyłałem odpowiedzi z komentarzami i aktualną statystykę (anonimowa lista).
• Udział był dobrowolny.
• Udział był anonimowy, każdy uczestnik miał przypisany identyfikator i tylko ja znałem mapowanie.
• Zwycięzca mógł wybrać sobie nagrodę ufundowaną przez firmę (wybrał przenośny dysk).

Do Quiz'u zgłosiło się 20 osób. Łącznie zadałem 9 łatwych pytań, 12 średnich oraz 9 trudnych za łącznie 60 punktów. Zwycięzca zdobył 52.5 punkty i walka trwała do ostatniej tury ponieważ druga osoba w rankingu miała 52 punkty, a trzecia i czwarta 51. Zebrane w całości pytania i odpowiedzi utworzyły 22 stronicowy dokument!

Quiz spodobał się i spotkał się z bardzo dobrym odbiorem również ze strony przełożonego, który dał pieniądze na nagrodę. Najbardziej cieszy mnie jednak to, że już kilkukrotnie słyszałem od kolegów, że w trakcie Quiz'u nauczyli się czegoś nowego.

Organizacja Quiz'u to również nauka dla mnie. Aby przygotować pytania i nie zaliczyć wpadki wiele zagadnień musiałem przestudiować dużo dokładniej. Nauczyłem się również jak, wbrew pozorom, trudne jest układanie pytań w taki sposób, aby były zrozumiałe dla wszystkich. Pomimo, że każde zadanie czytałem wielokrotnie zdarzało się, że musiałem odpowiadać na pytania i rozsyłać dodatkowe informacje.

Na koniec kilka przykładów pytań:

Łatwe

We have to measure an execution time with the maximum possible resolution/precision. It was implemented in the following way. Does this code meet this requirement? If yes, why? If not, propose a better solution.

var start = DateTime.Now;
//...
var end = DateTime.Now;

Średnie

.NET 4.5 introduces a new, easy and elegant way to retrieve a name of a method (caller) which executed/called a given method (calle).

public void Fun()
{
//Here, I want to get a name of a method that executed/called Fun method
}

Trudne

We want to use a class called  Fun, that  is defined in an external library. Unfortunately, a constructor of this class contains a bug which causes an exception. In other words, we can't create a new instance of Fun class, but we have to. You have to find a workaround. You mustn't modify Fun class.

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

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.

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.

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

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.

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.

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.

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:

Szczecin	Gdańsk	Kołobrzeg
Gdańsk	Kołobrzeg	Gdańsk
Kołobrzeg	Kołobrzeg	Szczecin
	Szczecin	Gdań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ńsk	Szczecin	Kołobrzeg
Szczecin	Kołobrzeg	Szczecin
Gdańsk	Gdańsk	Kołobrzeg
Kołobrzeg	Gdańsk	Szczecin
Szczecin	Kołobrzeg	Szczecin
Gdańsk	Gdańsk	Kołobrzeg
Kołobrzeg	Gdańsk	Szczecin

Codility

Home

Jestem wielkim zwolennikiem sprawdzania kandydatów na programistów przy pomocy zadań wymagających napisania kodu. Sam również byłem egzaminowany w ten sposób nie raz i nie dwa. W pamięci zapadły mi jednak rekrutacje z udziałem portalu Codility, który weryfikuje nie tylko poprawność kodu ale również jego wydajność, za każdym razem było to dla mnie ciekawe wyzwanie.

Postanowiłem więc skontaktować się z Codility i zapytać czy w ofercie mają produkt pozwalający programistom ćwiczyć ich umiejętności. Odpowiedź na zapytanie dostałem bardzo szybko i niestety okazała się negatywna, ale zostałem zaproszony do ich biura w Warszawie aby porozmawiać o tym pomyśle.

Trochę to trwało zanim udało się nam ustalić termin spotkania, ale w końcu pewnego popołudnia wsiadłem w tramwaj i pojechałem na Plac Bankowy. Na miejscu przywitała mnie przemiła Czeszka Zuzana, miałem okazję poznać zespół pracujący nad rozwojem Codility oraz porozmawiać o ich pracy. Ponieważ nie miałem wcześniej okazji korzystać z portalu od strony rekrutera pokazano mi jak to wygląda.

Na koniec wręczono mi upominek w postaci książki Looking For a Challenge? z opisem kilkudziesięciu ciekawych zadań programistycznych, przygotowanych przez zwycięzców międzynarodowych konkursów programistycznych.

À propos problemów algorytmicznych, dowiedziałem się również, że część zadań Codility dostępna jest w Internecie dla każdego programisty, ale nie wszystkie łatwo znaleźć. Poniżej, dzięki uprzejmości Codility, macie ich pełną listę. Lista ta z czasem będzie z czasem rozszerzana o tzw. zadania well known czyli takie, które są dobrze znane i nie ma sensu przy ich pomocy testować kandydatów ale idealnie nadają się do ćwiczeń.

• psi2012
• phi2012
• chi2012
• upsilon2012
• tau2012
• sigma2012
• rho2012
• pi2012
• omicron2012
• xi2012
• nu2011
• mu2011
• lambda2011
• kappa2011
• iota2011
• theta2011
• eta2011
• zeta2011
• epsilon2011
• delta2011
• gamma2011
• beta2010
• alpha2010

Wizytę wspominam bardzo miło. Tym bardziej, że Codility odwiedziłem nie jako klient, ale jako "człowiek z ulicy". Cieszy również, że to polski start-up odnoszący sukcesy na świecie.

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?

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.

Coursera

Home

Ponad rok temu pisałem o możliwości wzięcia udziału w kursach online dotyczących uczenia maszynowego czy baz danych prowadzonych przez Uniwersytet Stanforda. Kursy te okazały się strzałem w dziesiątkę i na przykład na ten dotyczący uczenia maszynowego zapisało się około 100 tysięcy osób!

Wracam do tego tematu ponieważ ostatnio kolega wspomniał mi o projekcie/firmie Coursera, która oferuje każdemu, bezpłatnie, możliwość wzięcia udziału w ponad 300 kursach online, z różnych dziedzin, które zostały przygotowane przez uczelnie z całego świata. Interesują cię kompilatory? A może gra na gitarze lub system monetarny Chin? Każdy powinien znaleźć coś dla siebie. Projekt dopinguję tym bardziej, że założycieli jest profesor nadzwyczajny z Uniwersytetu Stanforda Andrew Ng, który przygotował i poprowadził wspomniany kurs uczenia maszynowego.

Na bieżącą chwilę Coursera ma już 2 mln 700 tysięcy użytkowników. Nieźle jak na projekt, który wystartował niecały rok temu. W każdym razie uważam, że to wspaniała inicjatywa, tym bardziej warta docenienia, że daje dostęp do rzetelnej wiedzy za darmo, co w obecnych czasach jest coraz mniej oczywiste. Żeby tylko znaleźć na to czas ;)

Co to jest dobre oprogramowanie?

Home

Pytanie jak powyżej pojawiło się w rozmowie w jakiej ostatnio uczestniczyłem. Każdy z nas ma na pewno swoje zdanie na temat cech, które powinien posiadać dobry program/system. Nie inaczej było w tym przypadku i padło wiele odpowiedzi. Po bliższym przyjrzeniu się, okazało się jednak, że odpowiedzi te można pogrupować w raptem cztery kategorie, co było dla mnie pewnym zaskoczeniem. Dodam, że w rozmowie uczestniczyło pięć osób, wszystkie techniczne, ale o różnym doświadczeniu, które pracowały przy różnych projektach i w różnych firmach. Te cztery kategorie to począwszy od najpopularniejszej:

• Program/system powinien być łatwy oraz tani w utrzymaniu i rozwoju. Do tej kategorii można wrzucić bardzo wiele rzeczy: odpowiednia architektura, obecność testów jednostkowych, dobra dokumentacja wymagań, stosowanie wzorców projektowych itd. Pojawienie się tej kategorii jednoznacznie wskazuje na programistyczny background osób biorących udział w rozmowie.
• Program/system powinien spełniać wymagania i oczekiwania klienta, rozwiązywać jego problemy.
• Program/system powinien spełniać wymagania i oczekiwania użytkownika, być ergonomiczny i łatwy w użyciu. Kategoria ta może wydawać się podobna do drugiej kategorii, ale kładzie nacisk na użytkownika końcowego, który w wielu przypadkach nie jest tożsamy z zamawiającym oprogramowanie (klientem).
• Program/system powinien przynosić firmie tworzącej oprogramowanie zyski, dobrze się sprzedawać. Bez tego też nie da się obejść. Nawet jeśli oprogramowanie zostało napisane z zachowaniem wszystkich zasad i jest cudeńkiem inżynierii, ale się nie sprzedaje, to nie można nazwać go dobrym.

Sądzę, że zestawienie to, pomimo, że krótkie, jest kompletne. Udało się w nim uchwycić interesy różnych grup ludzi, którzy uczestniczą w przedsięwzięciu informatycznym czyli: firmy informatycznej, zespołu tworzącego produkt, klienta/firmy zamawiającej oraz użytkowników końcowych. Interesy tych czterech grup są nierzadko ze sobą sprzeczne ale dopiero kompromis pomiędzy nimi pozwala stworzyć naprawdę dobry system informatyczny.

Po zakończeniu tego posta zacząłem się zastanawiać ile projektów, o których słyszałem, rozmawiałem lub przy których pracowałem spełnia powyższe wymagania. W większości przypadków, które przyszły mi do głowy, mogę gdzieś wsadzić szpilkę. A to system co prawda przynosi kupę kasy ale jest napisany w taki sposób, że woła o pomstę do nieba... Inny z kolei to kawał dobrej programistycznej roboty, ale z jego urynkowieniem jest już gorzej... O wiele łatwiej jest mi znaleźć oprogramowanie wystarczająco dobre, czyli spełniające tylko niektóre z tych wymagań.

A jakie są Wasze doświadczenia?

WolframAlpha

Home

WolframAlpha to ambitny projekt stworzenia silnika, który umiałby odpowiadać na pytania wyrażone w języku naturalnym, a co więcej odpowiedzią nie byłaby sucha lista stron w Internecie, ale zbiór faktów stanowiących odpowiedź na pytanie. O tym przedsięwzięciu wiedziałem już od dłuższego czasu, ale traktowałem je raczej jako nowinkę i go nie używałem.

Ostatnio kolega zwrócił mi jednak uwagę na możliwość rozwiązywania równań przy pomocy tego silnika. Od tej pory przestałem traktować go tylko jako ciekawostkę i jest pod ogromnym wrażeniem tego projektu, zastosowanych w nim algorytmów, no i oczywiście umiejętności programistów.

Może mały przykład. Jakiś czas temu inny kolega wysłał mail'a z zaproszeniem do poczęstunku z okazji urodzin, ale swój wiek podał w taki oto sposób:



Prawa część równania nie stworzy chyba nikomu problemów. Gorzej jednak z tą całką i sumą szeregu matematycznego, chociaż wyglądają znajomo. Kiedy byłem świeżo po kursie analizy matematycznej pewnie obudzony w środku nocy, po libacji alkoholowej, podałbym wynik bez zastanowienia ;) Teraz jednak, zamiast przypominać sobie wzory, wklepałem to równanie do WolframAlpha:

sum x = 1 to infinity 1/x^2)/(integral from -1 to 1 (1-x^2)^0.5)^2*(2^2^3 - 2^2^2)/2^2

i w mgnieniu oka uzyskałem wynik. Silnik potrafi również rysować wykresy, rozpoznaje rodzaje funkcji np.: powie, że zadane równanie to paraboloida, liczy pochodne, wyznacza nie tylko wartość całki oznaczonej, ale również potrafi policzyć całkę nieoznaczoną, rozwiązuje równania różniczkowe oraz robi pewnie setki innych rzeczy, o których jeszcze nie mam pojęcia. W każdym razie WolframAlpha na stałe zagości w moim przyborniku.

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.

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.

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.