DateTime.Parse vs DateTime.ParseExact

Home

Ostatnio spotkałem się z taka sytuacją. Ktoś zdefiniował sobie dość specyficzny format daty na swoje potrzebny. Wszystko było ok kiedy był on używany do zamiany typu DateTime na ciąg znaków. Problemy zaczęły się przy próbie wykonania operacji odwrotnej. Okazało się, że rodzina metod DateTime.(Try)Parse sobie z tym nie radzi. Rozwiązaniem okazało się użycie metod z rodziny DateTime.(Try)ParseExact, która od tych wcześniejszych różni się tym, że jawnie wymaga podania formatu, który ma zostać użyty przy parsowaniu.

Postawione pytanie brzmiało czemu DateTime.(Try)Parse nie działa w tym przypadku, a w innych tak? Moja odpowiedź jest taka. Nie wiem czemu podjęto taką decyzję, ale DateTime.(Try)Parse nie obsługuje wszystkich możliwych formatów i to nawet jeśli kultura używana przez aplikację zawiera wszystkie potrzebne informacje. Oto fragment z dokumetnacji:

If you parse a date and time string generated for a custom culture, use the ParseExact method instead of the Parse method to improve the probability that the parse operation will succeed. A custom culture date and time string can be complicated, and therefore difficult to parse. The Parse method attempts to parse a string with several implicit parse patterns, all of which might fail.

A to jeszcze jeden:

The Parse and TryParse methods do not fully iterate all strings in patterns when parsing the string representation of a date and time. If you require a date and time string to have particular formats in a parsing operation, you should pass the array of valid formats to the DateTime.ParseExact...

W skrócie DateTime.(Try)Parse jest z założenia "upośledzone" i nie umie wszystkiego. Dlaczego? Może dlatego, że obsłużenie wszystkich możliwych przypadków jest bardzo trudne? A może dlatego, że gdyby napisano kombajn obsługujący wszystko to działałby wolno? To tylko zgadywanie, ale trzeba pamiętać, że:

Jeśli używamy własnych formatów daty i czasu to zaleca się użycie DateTime.(Try)ParseExact.

Czy sposób pisania pętli for ma wpływ na wydajność?

Home

Przy okazji codziennej prasówki natknąłem się na ten artykuł na temat wydajności pętli for w JavaScript'cie dla różnych przeglądarek. W skrócie chodzi o to czy powinniśmy pisać pętlą for tak:

for (int i = 0; i < array.Length; i++)
   ...

A może raczej tak, czyli zapamiętać długości tablicy w zmiennej pomocniczej i nie odczytywać jej przy każdym przebiegu pętli:

for (int i = 0, len = array.Length; i < len; i++)
   ...

Z ciekawości sprawdziłem czy taka mikro optymalizacja ma jakiekolwiek znaczenie w przypadku programowania na platformę .NET. Do zmierzenia czasu użyłem takiej metody pomocniczej:

public static void MeasureIt<T>(Action<T> action, T arg, int noOfIterations)
{
   var sw = new Stopwatch();
   sw.Start();

   for (var i = 0; i < noOfIterations; ++i)
      action(arg);

   sw.Stop();
   Console.WriteLine("Total time: " + sw.ElapsedMilliseconds);
}

Następnie wykonałem następujący test:

var noOfIterations = 100000;
var noOfElements = 10000;
var array = Enumerable.Repeat(1, noOfElements).ToArray();
//Przypadek 1
MeasureIt(arg =>
{
   var total = 0;
   for (var i = 0; i < arg.Length; i++)
      total += a[i];  
}, array, noOfIterations);
//Przypadek 2
MeasureIt(arg =>
{
   var total = 0;
   for (int i = 0, len = arg.Length; i < len; i++)
      total += a[i];
}, array, noOfIterations);

Dla rzetelności testy uruchomiłem wielokrotnie. Czas wykonywania obliczeń w obu przypadkach wynosił około 320ms z dokładnością do kilku milisekund. Czasami pierwsze podejście było szybsze, a czasami drugie. Z jednej strony czegoś takiego się spodziewałem. Z drugiej strony sądziłem, że jednak zaobserwuję pewien zysk w drugim przypadku. Dlaczego?

Otóż jeśli spojrzymy na kod pośredni wygenerowany przez kompilator to te dwie implementacje bynajmniej nie są identyczne. W pierwszym przypadku długość tablicy odczytywana jest wielokrotnie na koniec pętli, a w drugim tylko raz przed właściwą pętlą. Najwidoczniej jest to jednak tak szybka operacja, że się nie liczy (w IL do odczytania długości jednowymiarowej tablicy istnieje dedykowana instrukcja ldlen).

Dodatkowo przeprowadziłem podobny test dla użycia listy generycznej List<T>. Tym razem różnice były już zauważalne i wynosiły około 27% na rzecz zapamiętania liczby elementów listy w dodatkowej zmiennej. Średnio pierwsza wersja wykonywała się 957ms, a druga 752ms. Wynika to z tego, że aby odczytać liczbę elementów w liście należy odczytać właściwość Count czyli metodę get_Count. Na poziomie IL jest to robione przy pomocy instrukcji callvirt (w telegraficznym skrócie służącej do wołania metod na rzecz obiektów), a nie dedykowanej (i pewnie zoptymalizowanej) instrukcji ldlen jak ma to miejsce w przypadku tablic. Pomimo tych różnic uważam jednak, że w codziennej praktyce programistycznej nie należy się tym przejmować gdyż różnice w czasach obliczeń, w porównaniu do dużej liczby iteracji (100000), są zbyt małe.

Zabawy z domenami aplikacyjnymi

Home

Proponuję zabawę z serii co zostanie wypisana na ekran. Mamy dwie klasy jak poniżej. Pierwsza z nich przekazywana jest pomiędzy domenami przez referencję, a druga przez wartość. Interfejs ITest ma charakter pomocniczy i nie ma znaczenia.

public interface ITest
{
   int Value { get; set; }
   void Start();
}

public class MarshalByRefObjectClass : MarshalByRefObject, ITest
{
   public int Value { get; set; }

   public void Start()
   {
      Console.WriteLine(AppDomain.CurrentDomain.FriendlyName);
      Value++;
   }
}

[Serializable]
public class MarshalByValueClass : ITest
{
   public int Value { get; set; }

   public void Start()
   {
      Console.WriteLine(AppDomain.CurrentDomain.FriendlyName);
      Value++;
   }
}

Mamy również następujący kod, w którym testuję jak zachowuja się:

• Obiekty przekazywane przez wartość i przez referencję.
• Utworzone w bieżącej (przy pomocy konstruktora) oraz w innej domenie (przy pomocy AppDomain.CreateInstanceFromAndUnwrap).
• Przy wywołaniu na nich metody bezpośrednio oraz przy pomocy AppDomain.Callback.

Co daje łączenie 2 x 2 x 2 = 8 możliwości. Do testowania używam takiej metody pomocniczej:

private static void Test(AppDomain app, ITest test, bool doCallBack)
{
   if (doCallBack)
      app.DoCallBack(test.Start);
   else
      test.Start();

   Console.WriteLine(test.Value);
}

A to właściwy test, w którym najpierw tworzę obiekty przekazywane przez wartość/referencję lokalnie i w nowej domenie. Następnie wywołuję dla nich metodę Start i odczytuję właściwość Value.

var app = AppDomain.CreateDomain("TestDomain");

var asm = Assembly.GetExecutingAssembly();
var byRef = new MarshalByRefObjectClass();
var byRef1 = new MarshalByRefObjectClass();
var byRef2 = (MarshalByRefObjectClass)app.CreateInstanceFromAndUnwrap(asm.CodeBase, typeof(MarshalByRefObjectClass).FullName);
var byRef3 = (MarshalByRefObjectClass)app.CreateInstanceFromAndUnwrap(asm.CodeBase, typeof(MarshalByRefObjectClass).FullName);

var byValue = new MarshalByValueClass();
var byValue1 = new MarshalByValueClass();
var byValue2 = (MarshalByValueClass)app.CreateInstanceFromAndUnwrap(asm.CodeBase, typeof(MarshalByValueClass).FullName);
var byValue3 = (MarshalByValueClass)app.CreateInstanceFromAndUnwrap(asm.CodeBase, typeof(MarshalByValueClass).FullName);

Test(app, byRef, true);
Test(app, byRef1, false);
Test(app, byRef2, true);
Test(app, byRef3, false);

Test(app, byValue, true);
Test(app, byValue1, false);
Test(app, byValue2, true);
Test(app, byValue3, false);

Pytanie brzmi co zostanie wypisane na ekranie? Pokaż/Ukryj odpowiedź

Obiekty przekazywane przez referencję wypiszą na ekran nazwę domeny w jakiej zostały utworzone. Nawet jeśli wywołanie jest inicjowane w innej domenie to zostanie przekazne do domeny orginalej ponieważ pracujemy z proxy do obiektu. W przypadku obiektów przekazywanych przez wartość na ekran zostanie wypisana nazwa domeny w jakiej następuje wywołanie.

Jeśli chodzi o wartość wypisaną na ekran to obiekty przekazywane przez referencję zawsze wypiszą ten sam wynik = 1 ponieważ zarówno wywołanie metody Start jak i odczyt Value dotyczy tego samego obiektu. W przypadku obiektów przekazywanych przez wartość w niektórych przypadkach możemy otrzymać zero. Stanie się tak kiedy wywołanie Start nastąpi w innej domenie niż ta, w której odczytujemy właściwość Value. A dzieje sie tak ponieważ obie czynność dotyczą de facto innych obiektów.

Sandbox.vshost.exe
1
Sandbox.vshost.exe
1
TestDomain
1
TestDomain
1
TestDomain
0
Sandbox.vshost.exe
1
TestDomain
0
Sandbox.vshost.exe
1

Domeny aplikacyjne i wątki

Home

Jakiś czas temu odpowiedziałem na pytanie na stackoverflow.com dotyczące kończenia pracy wątków z zewnętrznej biblioteki w sytuacji kiedy powinny już zakończyć pracę, a jednak tego nie zrobiły. Moja odpowiedź została co prawda skrytykowana, zresztą słusznie, ale dzięki temu dowiedziałem się rzeczy, która mi wcześniej umknęła.

W mojej odpowiedzi zasugerowałem, że skoro z jakiegoś powodu musimy użyć zewnętrznej biblioteki i ona nie działa to ja bym ją załadował do oddzielnej domeny aplikacyjnej i w tej nowej domenie uruchomił też obliczenia (wątki). Taką domeną można natomiast w dowolnym momencie "odładować" przy pomocy AppDomain.Unload. Napisałem nawet przykład pokazujący, że to działa. W czym więc problem?

Otóż wywołanie AppDomain.Unload może się nie powieść i zostanie wtedy rzucony wyjątku CannotUnloadAppDomainException. Powodów mogą być trzy, ale nas interesuje jeden. Kiedy wołamy AppDomain.Unload i wewnątrz domeny są aktywne jakieś wątki to AppDomain.Unload spróbuje je ubić przy pomocy metody Thread.Abort. Jeśli się uda to ok, ale Thread.Abort może nie być w stanie ubić wątku i wtedy zostanie wygenerowany wzmiankowany powyżej wyjątek.

Kiedy Thread.Abort nie zadziała? Dokumentacja wspomina o dwóch przypadkach.

• Kiedy wątek wykonuje kod niezarządzany.
• Kiedy wątek wykonuje właśnie kod wewnątrz bloku finally. To można bardzo łatwo symulować przez umieszczenie wywołania Thread.Sleep(100000) wewnątrz bloku finally.

Co wyróżnia bardzo dobrego programistę (2)?

Home

Pewnie słyszeliście o strumieniach (ang. stream) w .NET. O tym, że się je otwiera, a po użyciu zamyka. Zresztą w innych technologiach jest podobnie. Sprawa stara jak świat i wydawałoby się, że każdy o tym wie. Ja w każdym razie z definicji tak robię.

Dziwi mnie więc, że po tylu latach istnienia .NET ciągle pojawiają się pytanie z tym związane, jak na przykład to na stackoverflow.com. Dziwi mnie również, że przy okazji tego rodzaju pytań często pojawiają się najróżniejsze koncepcje / pomysły / odpowiedzi i to od użytkowników, którzy wcale nie są początkujący. Tymczasem wystarczy wrócić do podstaw, aby rozwiązać problem.

A może jest tak, że kiedy na co dzień pracujemy z skomplikowanymi algorytmami / trudnymi problemami biznesowymi / strukturami danych (niepotrzebne skreślić) to w pewnym momencie tracimy perspektywę i każdy napotkany problem od razu wydaje się nam skomplikowany.

Kolejny czynnik powodujący tą utratę perspektywy to chyba również mnogość różnych technologii i bibliotek, jakie są u obecnie używane. Ta biblioteka do tego, tamta ułatwia to, ta automatyzuje tamto itd. W ten sposób przyzwyczajamy się do tego, że wiele rzeczy coś robi za nas i my nie wnikamy w szczegóły i równocześnie zapominamy również o podstawach.

Nie mówię, że nie należy używać bibliotek, framework'ów czyli ułatwiać sobie pracy, ale bardzo dobry programista powinien również wiedzieć co, się za tym wszystkim kryje i nie zapominać o podstawach.

OxyPlot i nieciągłe przedziały

Home

Od dłuższego czasu używam biblioteki OxyPlot i bardzo ją sobie chwalę. Ostatnio zamarzyło mi się stworzenie wykresu przedziałowego. Na początek stwierdziłem, że wystarczy zastosować zwykły wykres liniowy czyli klasę LineSeries. Załóżmy, że chcemy zaprezentować na wykresy przedziały tj.; (2,3), (4,6) oraz (8,10). Spróbujmy, więc czegoś takiego:

var s = new LineSeries();
s.Title = "Nieciągłe przedziały";
s.Points.Add(new DataPoint(2, 1));
s.Points.Add(new DataPoint(3, 1));
           
s.Points.Add(new DataPoint(4, 1));
s.Points.Add(new DataPoint(6, 1));
        
s.Points.Add(new DataPoint(8, 1));
s.Points.Add(new DataPoint(10, 1));

To jednak nie zadziała gdyż w rezultacie otrzymamy linię ciągłą, czego zresztą należało się spodziewać ponieważ LineSeries po prostu łączy kolejne punkty. Wypróbowałem więc inne rodzaje wykresów, bawiłem się ustawieniami, ale bez rezultatów. Rozwiązanie okazało się jednak bardzo proste. Jeśli nie chcemy, aby dwa punkty zostały połączone linią to pomiędzy nimi należy umieścić punkt o współrzędnych (Double.Nan, Double.NaN).

var s = new LineSeries();
s.Title = "Nieciągłe przedziały";
s.Points.Add(new DataPoint(2, 1));
s.Points.Add(new DataPoint(3, 1));
s.Points.Add(new DataPoint(Double.NaN, Double.NaN));            
s.Points.Add(new DataPoint(4, 1));
s.Points.Add(new DataPoint(6, 1));
s.Points.Add(new DataPoint(Double.NaN, Double.NaN));       
s.Points.Add(new DataPoint(8, 1));
s.Points.Add(new DataPoint(10, 1));

Na koniec jeszcze przykład tak skonstruowanego wykresu:

Token Content in state Epilog would result in an invalid XML document

Home

To kolejny post z serii ku pamięci aby oszczędzić innym bólu. Otóż po wprowadzeniu zmian do logiki pewnego web service'u i napisaniu testów jednostkowych, postanowiłem go jeszcze przetestować integracyjnie przy pomocy skądinąd fajnego narzędzia SoapUI. Zacząłem od przygotowałem komunikatu XML do wysłania do usługi. Poszło szybko i myślałem, że to już prawie koniec mojej pracy. Niestety był to dopiero początek, gdyż okazało się, że po wysłaniu komunikatu serwer zwraca błąd jak poniżej:

Token Content in state Epilog would result in an invalid XML document.

Zdziwiłem się ponieważ to nie był pierwszy raz kiedy przechodziłem przez tą procedurę i nigdy z czymś takim się nie spotkałem. Początkowo pomyślałem, że to wina moich zmian, ale testy przy użyciu starej wersji kodu dały ten sam wynik. W następnej kolejności sprawdziłem, wiec czy używane przeze mnie wcześniej komunikaty/żądania dają ten sam błąd, ale działały poprawnie. W tym momencie wiedziałem już, że coś jest nie tak z tym konkretnym żądaniem. Zacząłem z niego wycinać kolejne elementy, aż pozostał prawie pusty, a błąd wciąż występował. W tym momencie mnie oświeciło i postanowiłem podejrzeć to czego nie widać gołym okiem czyli białe znaki. Kiedy to zrobiłem zakląłem szpetnie ponieważ przyczyną problemu okazał się znak nowej linii na końcu komunikatu - tuż po tagu zamykającym.

10000 UserObjects

Home

10000 to limit User Objects jakie na moim sprzęcie mogła zaalokować aplikacja zanim się wywaliła. 10000 to w gruncie rzeczy bardzo duża liczba i jeśli osiągamy ten limit to z dużą pewnością mamy jakiś problem i tak było w przypadku aplikacji napisanej w WinForms jaką miałem naprawić.

Po podłączeniu się debugger'em do aplikacji szybko stwierdziłem, że problem dotyczy jednej z kontrolek, która była alokowana dynamcznie w pętli. Na menadżerze zadań bardzo ładnie było widać jak wzrasta liczba User Objects z każdą kolejną instancją tej kontrolki. Nie byłem natomiast pewny czemu te kontrolki nie były zwalniane pomimo, że były usuwane z UI i nie było na nich wskazań (jak się później okazało pozornie). Tutaj z pomocą przyszedł ANTS Memory Profiler. Jedno uruchomienie i już wiedziałem w czym tkwi problem. Mrówki pokazały, że nie zwolnione kontrolki wciąż są wskazywane przez obiekt klasy System.Windows.Forms.DropTarget.

To dość częsty błąd, a dzieje się tak jeśli kontrolka wspiera Paste & Copy i w związku z tym ma ustawioną właściwość AllowDrop na true. Powoduje to, że kontrolka wskazywana jest przez wspominany obiekt klasy DropTarget dopóki nie ustawimy AllowDrop z powrotem na false. Poprawka błędu okazała się więc trywialna. Wystarczyło, że przy usuwaniu kontrolki z UI ustawiłem tą właściwość na false. W sumie drobna rzecz, ale łatwa do pominięcia.

Jeszcze krótki komentarz odnośnie technologii WPF. Tutaj też mamy właściwość AllowDrop, ale opisany problem nie występuje ponieważ WPF ma zupełnie inne bebechy niż WinForms.

Od jakiej wartości zaczynają się indeksy tablic w C#?

Home

To post z serii ciekawostki. Większość z Was zapytana od jakiej wartości zaczynają się indeksy tablic w C# odpowie z pewnością, że od 0 i tego należy się trzymać, ale są pewne wyjątki. Oto przykład na jaki natknąłem się eksplorując czeluście platformy .NET pokazujący jak stworzyć tablicę 10x10 z indeksami zaczynającymi się od 5:

var array = Array.CreateInstance(typeof(int), new[] { 10, 10 }, new[] { 5, 5 });
var array2 = (int[,]) array;

A teraz mały przykład użycia:

array2[1,3] = 1 // Out of bounds array index
array2[5,6] = 1 // OK
array2[15,14] = 1 // Out of bounds array index
array2[14,14] = 1 // OK

Oczywiście nie byłbym sobą gdybym nie spróbował tego samego z tablicą jednowymiarową:

var array = Array.CreateInstance(typeof(int), new[] { 10 }, new[] { 5 });
var array2 = (int[]) array;

Taka próba rzutowania zakończy się niestety, a może na szczęście, wyjątkiem o treści:

Unable to cast object of type 'System.Int32[*]' to type 'System.Int32[]'.

Co oznacza zapis System.Int32[*]? Mówiąc szczerze nie jest do końca pewny. Bazując jednak na poniższym teście:

Console.WriteLine(new int[10].GetType()); 
Console.WriteLine(Array.CreateInstance(typeof(int), new[] { 10 }, new[] { 0 }).GetType());
Console.WriteLine(Array.CreateInstance(typeof(int), new[] { 10 }, new[] { 5 }).GetType()); 
Console.WriteLine(new int[10,10].GetType()); 
Console.WriteLine(Array.CreateInstance(typeof(int), new[] { 10, 10 }, new[] { 5, 5 }).GetType()); 

Który wypisze na ekran takie wyniki:

System.Int32[]
System.Int32[]
System.Int32[*]
System.Int32[,]
System.Int32[,]

Można stwierdzić, że nazwa typu TYP[*] oznacza po prostu tablicę jednowymiarową z indeksem nie zaczynającym się w zerze.

Na koniec jeszcze jedna ciekawostka. Rzutowanie System.Int32[*] na System.Int32[] w kodzie programu nie powiedzie się, ale już w oknie Quick Watch albo Immediate Window już tak:

Zużycie procesora przez wskazany proces

Home

Potrzebowałem ustalić programowo bieżące zużycie procesora przez wskazany proces. Zacząłem od przyjrzenia się licznikom wydajności i szybko naklepałem coś takiego:

var p = Process.GetProcessById(id);
var counter = new PerformanceCounter("Process", "% Processor Time", myProcess.ProcessName);
Console.WriteLine("Processor %: {0}", counter.NextValue());

Przetestowałem i wyniki okazały się dziwne ponieważ czasami uzyskiwałem zużycie większe niż 100%. Chwila, ale przecież mam 8 rdzeniowy procesor. Spróbujmy więc czegoś takiego:

Console.WriteLine("Processor %: {0}", counter.NextValue() / Environment.ProcessorCount);

To już działało dobrze. Postanowiłem jednak poszukać alternatywnego sposobu i przyjrzałem się co oferuje klasa Process. Szybko znalazłem właściwość Process.TotalProcessorTime, która zgodnie ze swoją nazwą zwraca całkowity czas procesora zużyty przez dany proces począwszy od jego uruchomienia. Ja potrzebowałem natomiast aktualnego zużycia. Trochę myślenia, szukania w Internecie (na przykład tutaj) i szybko dopisałem coś takiego:

public class Utils
{
    public class ProcessorUtilizationInfo
    {
        public TimeSpan LastProcessorTime { get; set; }
        public DateTime LastCheck { get; set; }
        public double Value { get; set; }
        public Process Process { get; set; }
    }

    public static ProcessorUtilizationInfo GetProcessorUtilization(ProcessorUtilizationInfo info)
    {
        info.Process.Refresh();

        var now = DateTime.Now;
        var elapsed = now - info.LastCheck;
        var processorTime = (info.Process.TotalProcessorTime - info.LastProcessorTime);

        info.LastProcessorTime = info.Process.TotalProcessorTime;
        info.LastCheck = now;
        info.Value = processorTime.TotalMilliseconds / elapsed.TotalMilliseconds / Environment.ProcessorCount;

        return info;
    }
}

Dla przejrzystości pominąłem walidację danych. Klasa pomocnicza ProcessorUtilizationInfo jest potrzebna gdybyśmy chcieli wołać metodę GetProcessorUtilization wielokrotnie dla tego samego procesu. Ktoś może marudzić, że używam DateTime.Now, że wynik może być nieprecyzyjny, ale moje testy pokazały, że zastosowanie licznika wydajności i metody GetProcessorUtilization daje podobny rezultaty. Przykład użycia metody GetProcessorUtilization wygląda następująco:

var p = Process.GetProcessById(id);
var info = new Utils.ProcessorUtilizationInfo {Process = p};
Console.WriteLine("Processor %: {0}", Utils.GetProcessorUtilization(info).Value * 100);

Do opisanych 2 sposobów uzyskania aktualnego zużycia procesora dla wskazanego procesu mam jedno zastrzeżenie. Otóż oba rozwiązania dają co prawda bardzo zbliżone wyniki (zaobserwowałem różnice rzędu 0.1 - 0.2%), ale wyniki te różniły się nawet o 1% od tego co pokazywał menadżer zadań. Ktoś wie dlaczego? Może znacie lepsze rozwiązanie postawionego problemu?

Sortowanie w czasie liniowym

Home

Teoria mówi, że optymalna złożoność obliczeniowa dla algorytmów sortowania opartych o porównywanie wynosi O(nlogn), czyli, innymi słowy, szybciej być już nie może. Taką złożoność optymistyczną ma na przykład używany w .NET algorytm sortowania szybkiego. Ale chwila, co to znaczy sortowanie oparte o porównywanie? To w ogóle istnieje inna możliwość? Przecież, aby posortować na przykład listę liczb całkowitych, to trzeba je porównywać!

Okazuje się, że do problemu można podejść inaczej. Jeśli zrezygnujemy z porównywania, to, pod pewnymi warunkami, osiągniemy złożoność liniową O(n). Niby szybciej, ale czy rzeczywiście warto się tym przejmować? Postanowiłem to sprawdzić i porównałem zachowanie algorytmu sortowania używanego przez .NET, naiwnej rekurencyjnej implementacji sortowania szybkiego oraz algorytmu sortowania w czasie liniowym o nazwie sortowanie przez zliczanie.

Sortowanie przez zliczanie zostało opisane choćby na Wikipedii, dlatego tutaj przybliżę tylko jego ideę. Zacznijmy od tego, że algorytm ten bardzo dobrze nadaje się do sortowania liczb całkowitych z zadanego zakresu, powiedzmy od K do N. Im N mniejsze tym lepiej i jest to oczywiście istotne jego ograniczenie. Jego działanie opiera się na policzeniu, ile razy w tablicy do posortowania pojawiła się liczba K, ile razy liczba K + 1 ... i ile razy liczba N. W tym celu wystarczy odwiedzić każdy element tablicy tylko raz. Kiedy mamy już te informacje, sortowanie właściwie jest zakończone. Na przykład: jeśli liczba 0 wystąpiła 10 razy, a liczba 3 wystąpiła 2 itd., to jako wynik wypiszemy najpierw 10 razy 0, potem 2 razy 3 itd.

Wyniki porównania wspomnianych 3 algorytmów zaprezentowałem na 2 wykresach poniżej. Oś X pokazuje liczbę elementów do posortowania, a oś Y czas sortowania w ms. Pierwszy wykres pokazuje przypadek, kiedy dane do posortowania zawierały liczby z zakresu od 0 do 100, a drugi od 0 do 100 tysięcy.



Wnioski są następujące, niektóre bardzo ciekawe:

• Dla małego zakresu liczb naiwna implementacja sortowania szybkiego działa bardzo słabo (mamy tutaj pesymistyczny przypadek i złożoność O(n^2)).
• Nie widać tego na wykresie, lecz dla małego zakresu liczb sortowanie przez zliczanie jest nieznacznie szybsze od implementacji używanej przez .NET: dla 1 miliona elementów jest to 15 ms w porównaniu do 64 ms.
• W związku z tym pojawia się pytanie, czym różni się naiwna rekurencyjna implementacja sortowania szybkiego od tej używanej przez .NET? Można by o tym dużo napisać, więc tutaj tylko zasygnalizuję o co chodzi. Otóż w rzeczywistości .NET używa tzw. sortowanie introspektywnego, który stanowi połączenie "zwykłego" sortowania szybkiego, sortowania przez kopcowanie i sortowania przez wstawianie, przez co wyeliminowano przypadek pesymistyczny, kiedy QuickSort ma złożoność wielomianową.
• Dla dużego zakresu elementów różnica pomiędzy 3 porównywanymi algorytmami zaciera się chociaż rekurencyjna implementacja QuickSort jest wciąż najwolniejsza, a sortowanie przez zliczanie jest trochę szybsze od tego co oferuje .NET.
• Sprawdziłem czas sortowania dla maksymalnie 50 milionów elementów i trwało to 2 s dla sortowanie przez zliczanie oraz 5 s dla hybrydowego.
• Wniosek końcowy jest taki, że biorąc pod uwagę ograniczenia i wady sortowania przez zliczanie oraz to, jak dobrze działa implementacja hybrydowa w .NET należy jej po prostu używać i nie zastanawiać się specjalnie nad innymi wynalazkami.

Przydaś do rysowania wykresów

Home

Od jakiegoś czasu sporo pracuję z różnymi seriami danych numerycznych np.: sekwencje identyfikatorów metod wywołanych w programie. Serie takie mogą być bardzo długie i potrzebowałem narzędzia, które łatwo i szybko pozwoli mi je wizualizować czyli wygenerować wykres, tak abym mógł szybko ocenić co znajduje się w danym pliku. Kombajnów do rysowania wykresów jest dużo, choćby Excel, ale ja potrzebowałem czegoś jeszcze prostszego. Idealnie abym mógł po prostu zaznaczyć plik z danymi i z menu kontekstowego wybrać polecenie Narysuj wykres. Możliwe, że znalazłbym coś takiego, ale napisanie takie narzędzia samemu zajęło mi dosłownie chwilę.

Po pierwsze zdecydowałem się użyć biblioteki OxyPlot bo jest bardzo prosta w użyciu, a także radzi sobie z długimi seriami danych i pozwala narysować wiele różnych typów wykresów. W drugim kroku stworzyłem bardzo prostą aplikację z jednym oknem w WPF'ie. Do projektu dodałem referencje do bibliotek OxyPlot oraz OxyPlot.Wpf. XAML dla głównego i jedynego okna wygląda w następujący sposób:

<Window x:Class="DrawPlot.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" 
        xmlns:oxy="http://oxyplot.codeplex.com"
        xmlns:local="clr-namespace:DrawPlot"
        Title="DrawPlot" Height="350" Width="525">
    <Window.DataContext>
        <local:MainViewModel/>
    </Window.DataContext>
    <Grid>
        <oxy:Plot Model="{Binding MyModel}"/>
    </Grid>
</Window>

Trzeci krok to napisanie klasy MainViewModel, która stworzy i zainicjuje obiekt klasy PlotModel. Obiekt ten będzie zawierał informacje potrzebne do narysowania wykresu i przy pomocy binding'u zostanie przekazany do kontrolki Plot. W podstawowej wersji kod tej klasy jest bardziej niż prosty. Zakładam z góry określony format pliku wejściowego tj. każda linia zawiera jedną liczbę, a część ułamkowa musi być oddzielona od części całkowitej kropką. Użyłem klasy LineSeries czyli rysuję wykres liniowy. W poniższym kodzie celowo pominąłem również bardziej przyjazną obsługę błędów czyli jeśli coś się nie powiedzie to po prostu wyświetlam treść błędu i zamykam aplikację.

namespace DrawPlot
{
    public class MainViewModel
    {
        public PlotModel MyModel { get; private set; }

        public MainViewModel()
        {
            try
            {
                var args = Environment.GetCommandLineArgs();

                var lines = File.ReadAllLines(args[1]);

                var lineSeries = new LineSeries();
                for (var i = 0; i < lines.Length; ++i)
                    lineSeries.Points.Add(new DataPoint(i, Double.Parse(lines[i], CultureInfo.InvariantCulture)));

                var model = new PlotModel(Path.GetFileName(args[1]));
                model.Series.Add(lineSeries);
                MyModel = model;
            }
            catch (Exception ex)
            {
                MessageBox.Show(ex.ToString());
                Application.Current.Shutdown();
            }
        }
    }
}

Ostatni krok to dodanie nowej pozycji do menu kontekstowego. Uzyskałem to przy pomocy dodania odpowiedniego wpisu w rejestrze. W moim przypadku skompilowana aplikacja znajduje się w lokalizacji T:\bin\DrawPlot\DrawPlot.exe.

Windows Registry Editor Version 5.00

[HKEY_CLASSES_ROOT\*\Shell\Draw plot]

[HKEY_CLASSES_ROOT\*\Shell\Draw plot\command]
@="T:\\bin\\DrawPlot\\DrawPlot.exe \"%1\""

Narzędzie jest bardzo proste, ale spełnia swoje zadanie. Możne je również łatwo rozbudować na przykład użyć innego rodzaju serii aby narysować wykres kołowy, dodać obsługę innych formatów plików wejściowych itd.

SizeLimit, PageSize i dokumentacja

Home

W poście wspomniałem o właściwościach DirectorySearcher.SizeLimit oraz DirectorySearcher.PageSize, których poprawne ustawienie zapewnia, że z bazy danych AD można pobrać więcej obiektów niż ustawiony na serwerze limit. Tym razem chciałbym sprecyzować do czego służą obie właściwości bo moim zdaniem dokumentacja nie jest precyzyjna, co potwierdza zresztą spora liczba pytań w Internecie na ten temat.

Otóż SizeLimit określa maksymalną liczbę obiektów jaka może zostać zwrócona w wyniku wyszukiwania (zero oznacza brak limitu) przy czym limit ustawiony na serwerze ma priorytet. PageSize służy natomiast do skonfigurowania stronicowania i wartość różna od zera je włącza. Na przykład wartość 100 oznacza, że obiekty będą zwracane w paczkach po 100, przy czym .NET jest na tyle miły, że samemu obsługuje doczytywanie kolejnych stron.

Teraz spójrzmy na przykład. W bazie danych AD znajdowało się 1580 obiektów spełniających kryteria wyszukiwania, a limit ustawiony na serwerze wynosił 1500. Poniższa tabelka pokazuje ile obiektów zwróci zapytanie w zależności od ustawień.

SizeLimit	PageSize	Liczba obiektów w AD	Liczba zwróconych obiektów	Uwagi
0	0	1580	1500	Brak stronicowania + domyślny limit z serwera
100	0	1580	100	Brak stronicowania + limit określony przez nas
0	100	1580	1580	Stronicowanie włączone
200	100	1580	1580	Stronicowanie włączone + limit określony przez nas
100	200	1580	100	Stronicowanie włączone + limit określony przez nas

Dwa ostatnie scenariusze są trochę zagadkowe. W obu przypadkach obie właściwości są różne od zera, ale liczba zwróconych obiektów jest inna tj. jeśli SizeLimit > PageSize to z AD pobrano wszystkie dostępne obiekty, a w przeciwnym wypadku tyle ile wynosił SizeLimit. Przypuszczam, że DirectorySearcher działa tak, że pobiera dane póki nie zostanie przekroczony limit. W pierwszym przypadku przy pobieraniu kolejnych stron liczba pobieranych obiektów nie przekracza limitu, a więc udało się odczytać wszystko. W drugim wypadku już przy pobraniu pierwszej strony liczba obiektów przekroczyła limit i dalsze pobieranie zostało zakończone. Pewnie można było to zaimplementować inaczej, ale cóż zrobić i po prostu warto o tym wiedzieć.

Czy wyrażenie regularne może zawiesić naszą aplikację?

Home

Rozmawiałem dzisiaj z kumplem z zespołu na temat jednego z zadań i trochę od niechcenie rzuciłem, że można by zastosować tutaj wyrażenie regularne, które dodatkowo byłoby konfigurowalne. Ta z pozoru niewinna uwaga doprowadziła do ciekawej dyskusji. Otóż Tomek stwierdził, że nie jest dobrym pomysłem aby umieszczać wyrażenia regularne w konfiguracji, która może zostać zmieniona przez użytkownika. Dlaczego? W ten sposób umożliwiamy użytkownikowi zawieszenie naszej aplikacji i to nie dlatego, że wyrażenie będzie zawierało błędy składniowe. Aby zrozumieć o co chodzi przyjrzyjmy się takiemu prostemu przykładowi, w którym testuję dwa wyrażenie regularne:

private static void Main(string[] args)
{
   var input1 = "xxxxxxxxxxxxxxxxxxxxxxxxxy";
   var input2 = "xxxxxxxxxxxxxxxxxxxxxxxxx";

   var regex1 = "x+y";
   var regex2 = "(x+)+y";

   TestRegex(regex1, input1);
   TestRegex(regex2, input1);

   TestRegex(regex1, input2);
   TestRegex(regex2, input2);

   Console.WriteLine("Press any key...");
   Console.ReadLine();
}

private static void TestRegex(string r, string input)
{
   var regex = new Regex(r);
   var sw = new Stopwatch();

   sw.Start();

   regex.Match(input);

   sw.Stop();

   Console.WriteLine("{0} ms", sw.ElapsedMilliseconds);
}

Oba użyte wyrażenie są proste. Drugie jest "dziwne" bo po co stosować tutaj konstrukcję grupującą. Oczywiście nie ma to tutaj sensu, ale zrobiłem to aby pokazać ideę problemu. Teraz przejdźmy do setna. Na moim komputerze powyższy program wypisze takie czasy:

30 ticks 0 ms
13 ticks 0 ms
31 ticks 0 ms
21621843 ticks 9246 ms

Różnica jest porażająca. Z pozoru niewinne wyrażenie regularne (x+)+y w przypadku kiedy wejściowy dane do niego nie pasują (w drugim przypadku na końcu ciągu znaków brakuje litery y) jest o duże kilka rzędów wielkości wolniejsze niż wyrażenie x+y Co gorsze im więcej x'ów w danych wejściowych tym te czasy będą gorsze:

Liczba x'ów	Czas (ms)
10	0
14	4
15	9
18	71
20	291
22	1169
24	4685
26	18741
28	74078

Mamy tutaj do czynienia z złożonością wykładniczą! Problem tkwi natomiast w użyciu w drugim wyrażeniu backtracking'u, który powoduje, że silnik wyrażeń regularnych niepotrzebnie wielokrotnie (na)wraca do znalezionych wcześniej dopasowań. Do tego potrzebne są również odpowiednio dobrane dane. Można mówić, że przykład jest tendencyjny (jak to przykład), ale skoro jest to możliwe to kiedyś się zdarzy i dlatego trzeba być świadomym takich rzeczy.

Kilka uwag końcowych:

• Pewnym obejściem problemu jest wyłączenie backtracking'u dla danej grupy w taki sposób: (?>(x+)+)y
• Można również określić maksymalny dopuszczalny czas przetwarzania wyrażenia regularnego np.: new Regex(r, RegexOptions.None, new TimeSpan(0,0,0,1))
• Jeśli to możliwe to zamiast backtracking'u należy stosować tzw. lookahead/lookbehind assertions, które nie nawracają.
• Problem opisałem na przykładzie .NET, ale może od dotyczyć każdego silnika wyrażeń regularnych, który obsługuje backtracking i który domyślnie z niego korzysta.
• Jeśli chcecie pogłębić temat to polecam ten artykuł albo ten.

Jeszcze więcej szczegółów na temat IntelliTrace

Home

O IntelliTrace pisałem już wielokrotnie. Do tej pory nie wyjaśniłem jednak, że chociaż IntelliTrace nazywamy debugger'em historycznym to w rzeczywistości IntelliTrace jest profilerem. Dokładniej mówiąc jednym z komponentów składowych IntellITrace jest niezarządzana implementacja interfejsu ICorProfiler. Profiler ten komunikuje się z zarządzaną częścią IntelliTrace, czyli z programem IntellITrace.exe. IntellITrace.exe jest natomiast używane przez Visual Studio.

Ma to ciekawe skutki. Oznacza bowiem, że oprócz nagrywania działania aplikacji z poziomu Visual Studio albo bezpośrednio przy pomocy programu IntelliTrace.exe (jak to opisałem tutaj) dochodzi jeszcze jedna opcja. Otóż możemy skorzystać ze zmiennych środowiskowych COR_ENABLE_PROFILING oraz COR_PROFILER i monitorować przy pomocy IntelliTrace zarządzaną usługę systemową.

W tym celu znajdujemy w rejestrze klucz:

HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\<Nazwa_Usługi>

Dodajemy do niego nową wartość Environment o typie REG_MULTI_SZ i zawartości:

COR_PROFILER={b19f184a-cc62-4137-9a6f-af0f91730165}
COR_ENABLE_PROFILING=1
VSLOGGER_CPLAN=COLLECTION_PLAN_PATH

W pierwszeh linijce wskazujemy profiller, jaki ma zostać użyty do monitorowania usługi. W tym przypadku będzie to IntelliTrace dla VS 2012. Identyfikator profiler'a IntelliTrace dla VS 2010 jest inny tj. 301EC75B-AD5A-459C-A4C4-911C878FA196. Oczywiście, jeśli nie mamy zainstalowanej danej wersji Visual Studio, to profiler nie będzie zarejestrowany w systemie.

W drugiej linijce po prostu włączamy profilowanie, a w trzeciej wskazujemy ścieżkę to pliku XML z konfiguracją IntelliTrace. O tym, skąd wziąć ten plik, pisałem we wspomnianym już artykule oraz w innych postach z serii o IntelliTrace. Tutaj zaznaczę tylko, że należy w nim ustawić nazwę pliku z logiem oraz katalog roboczy np.:

<CollectionPlan xmlns="urn:schemas-microsoft-com:visualstudio:tracelog">
  <StartupInfo>
    <LogFileName>log.itrace</LogFileName>
    <LogFileDirectory>c:\Logs</LogFileDirectory>
    <MaximumLogFileSize>-1</MaximumLogFileSize>
  </StartupInfo>
  ...
</CollectionPlan>

Na koniec po prostu uruchamiamy naszą usługę, a kiedy wykona swoje zadanie zatrzymujemy i przeglądamy nagrany log na przykład w Visual Studio.

Niestety, ale to podejście nie zadziała dla zwykłych aplikacji uruchamianych z dwukliku. Sądzę, że w takich wypadkach IntelliTrace nie obsługuje zmiennej środowiskowej VSLOGGER_CPLAN, ale tego akurat nie jestem pewny. Istnieje jednak inna możliwość. W praktyce używana jest rzadko, gdyż jest mało wygodna, ale pokazuje jak IntelliTrace działa od środka. A więc uruchamiamy wiersz polecenia i wpisujemy następujące komendy:

rem Uruchamiamy instancję IntelliTrace o nazwie 'test' ale nie wskazujemy programu do monitorowania
%INTELLI_TRACE_PATH%\IntelliTrace.exe start /n:test /f:"D:\WorkingDir\IntelliTrace\IntelliTraceWorkingDir\Test.iTrace" /cp:%COLLECTION_PLAN%

rem Włączamy profilowanie
set COR_ENABLE_PROFILING=1

rem Ustawiamy profiler, który chcemy użyć do monitorowania naszego programu tj. IntelliTrace
set COR_PROFILER={b19f184a-cc62-4137-9a6f-af0f91730165}

rem Ustawiamy nazwę instancji IntelliTrace z jakiej chcemy skorzystać
set VSLOGGERNAME=test

rem Uruchamiamy program, który chcemy monitorować przy pomocy instancji IntelliTrace o nazwie 'test'
MyProgram.exe

rem Zamykamy instancję IntelliTrace o nazwie 'test'
%INTELLI_TRACE_PATH%\IntelliTrace.exe stop /n:test /cp:%COLLECTION_PLAN%

Podejście to różni się od standardowego tym, że tutaj instancja IntelliTrace czeka na uruchomienie programu, zamiast uruchomić go samemu.

Metody rozszerzające w .NET 2.0

Home

.NET 2.0 to stara rzecz, ale wciąż z różnych powodów używana, na przykład dlatego, że klient nie chce zainstalować nowej wersji platformy na maszynach wszystkich użytkowników systemu. A co, jeśli pomimo tego wymarzy się nam użycie na przykład LINQ to Objects? Metody takie jak Select, Take itd. łatwo zaimplementować samemu, ale bez extensions methods ich użycie nie będzie takie przyjemne.

Zastanówmy się, co z tym robić. Metody rozszerzające obsługiwane są począwszy od .NET w wersji 3.5. Wiemy też, że mając kompilator dla .NET w wersji X możemy skompilować projekt dla .NET w wersji Y jeśli Y <= X. Do tego dodajmy, że extensions methods są mechanizmem czasu kompilacji i jako takie są niezależne od wersji platformy. Idąc tym tokiem rozumowania powinno być możliwe ich wykorzystanie w projektach używających .NET 2.0 o ile do kompilacji użyjemy nowszego kompilatora. Szybki eksperyment, czyli próba zdefiniowania metody rozszerzającej dla projektu używającego .NET 2.0 pokaże jednak, że coś jest nie tak i otrzymamy taki błąd kompilacji:

Cannot define a new extension method because the compiler required type 'System.Runtime.CompilerServices.ExtensionAttribute' cannot be found. Are you missing a reference?

Nie wszystko jednak stracone. Okazuje się, że wystarczy zdefiniować w projekcie następujący atrybut aby kompilacja zakończyła się powodzeniem:

namespace System.Runtime.CompilerServices
{
    [AttributeUsage(AttributeTargets.Assembly | AttributeTargets.Class | AttributeTargets.Method)]
    public sealed class ExtensionAttribute : Attribute { }
}

Trochę to brzydkie, ale możemy cieszyć się metodami rozszerzającymi w projektach korzystających ze starej wersji platformy. Atrybut ten jest potrzebny, ponieważ kompilator wykorzystuje go do oznaczenia metod tak, aby było wiadomo, które metody z różnych bibliotek są metodami rozszerzającymi.

Sztuczkę tą wykorzystują projekty takie jak LINQ for .NET 2.0 lub LinqBridge

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.

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.

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?