04/08/2013

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.

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.

15/07/2013

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.

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?