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.

Desktop Heap

Home

W swojej pracy bardzo lubię dowiadywać się o zupełnie nowych rzeczach, o których jeszcze nigdy nie słyszałem. Ostatnio taką nowością dla mnie było pojęcie desktop heap (sterta pulpitu???). Jest to coś, czym 99% z nas przez 99% czasu nie ma potrzeby się zajmować, a zainteresujemy się tym dopiero, jak to często bywa, kiedy pojawią się kłopoty.

Ja spotkałem się z desktop heap przy okazji problemów z usługami systemowymi tj. jeszcze kilka minut temu nie było kłopotów i nagle przestały się uruchamiać. W logu systemowym pojawił się natomiast komunikat podobny do poniższego:

Could not find file ‘C:\WINDOWS\TEMP\ayui23kj.dll’

Kolega znalazł artykuł, który jako winowajcę wskazywał właśnie desktop heap i było to strzałem w dziesiątkę. Pojęcie to zostało dobrze opisane w tym artykule, dlatego tutaj opiszę je tylko pokrótce. Zacznijmy od tego, że w systemie Windows mamy pojęcie sesji (ang. session) pod którym kryje się ogół zasobów powiązanych z pojedynczym zalogowanym użytkownikiem.

W ramach sesji może istnieć wiele window station. Obsługują one schowek i zawierają w sobie różne procesy oraz pulpity (ang. desktop). Warto zapamiętać, że tylko jedna stacja może komunikować się z użytkownikiem i nazywa się ona Winsta0.  Co okaże się ważne później, wszystkie usługi systemowe działające na tym samym koncie zostają przydzielone do tej samej stacji.

To dość daleka analogia, ale stacja przypomina mi domeny aplikacyjne znane z platformy .NET. Domeny aplikacyjne to takie małe procesy, które służą zwiększeniu bezpieczeństwa przez separację różnych zadań od siebie, a więc oba pojęcia mają podobną rolę.

Wspomniane pulpity zawierają w sobie wirtualną/logiczną przestrzeń, na której można coś wyświetlić. To również pojemniki na obiekty interfejsu użytkownika takie, jak okna i menu. Dokładniej obiekty te przechowywane są w części pulpitu zwanej właśnie stertą. Problem polega na tym, że sterta ma ograniczoną wielkość i może się zapełnić, i tak było w moim przypadku.

Wielkością sterty można co prawda sterować (patrz tutaj oraz tutaj), ale pytanie brzmi co spowodowało jej przepełnienie. W moim przypadku problemem okazała się zła obsługa niezarządzanych zasobów przez jedną z usług. Zasoby te nie były poprawnie zwalniane i wypełniały stertę, dodatkowo blokując inne usługi. Po wprowadzeniu poprawki problem z uruchomieniem usług ustąpił.

Na koniec chcę zwrócić uwagę na jedną rzecz. Ta jedna usługa blokowała inne bo wszystkie działały na tym samym koncie. W związku z tym korzystały z tej samej stacji, pulpitu i sterty. To co potwierdziło przepełnienie sterty był fakt, że zmiana konta używanego przez usługę powodowała, że można ją było poprawnie uruchomić. Innymi słowy zmiana konta powodowała przeskoczenie do innej stacji, a więc również do innej, nie wypełnionej sterty.

Czy użycie if zamiast else if ma znaczenie?

Home

Historia zaczyna się od prostego fragmentu kodu pokazanego poniżej. Kod ten to fragment walidatora, ktory ma za zadanie określić, czy dane są prawidłowe. Jeśli nie, to zmienna isValid powinna zostać ustawiona na false.

var isValid = true;

if (condition_1)
   isValid = false;

if (condition_2)
   isValid = false;

Kod ten działał do momentu, kiedy wprowadzono do niego małą zmianę pokazaną poniżej. Było to pewne uszczegółowienie logiki walidacji danych wejściowych.

var isValid= true;

if (condition_1)
   isValid = false;

if (condition_2)
   isValid = false;
//Wprowadzona zmiana
else 
{
   if (condition_3)
      isValid = true;
   else if (condition_4)
      isValid = false;
}

Po zastanowieniu się z pewnością stwierdzicie, że coś tutaj nie pasuje. Problem polega na tym, że w określonych warunkach zmienna isValid może zostać z powrotem ustawiona na true nawet jeśli wcześniej stwierdzono, że dane są błędne i ustawiono ją na false!

Może są jakieś rzadkie i dziwne przypadki kiedy błędne dane mogą stać się nagle poprawne, ale w przypadku, z jakim się spotkałem, był to ewidentny błąd i przeoczenie albo brak zrozumienia działania kodu. Moim zdaniem błąd tkwi jednak w jeszcze jednym miejscu tj. w użyciu wielu if'ów zamiast konstrukcji else if w kodzie pokazanym na samym początku. Gdyby początkowy kod wyglądał w ten sposób:

var isValid = true;

if (condition_1)
   isValid = false;
// else if zamiast if
else if (condition_2)
   isValid = false;

To nawet jego modyfikacja w opisany wcześniej sposób nie spowodowałaby, że walidator pozwolił na kontynuację przetwarzania pomimo błędnych danych. Może wydawać się, że kilka if'ów zamiast użycia else if nie robi różnicy bo to przecież oczywiste jak ten kod działa. Może i oczywiste, ale tu i teraz. Za kilka tygodni lub miesięcy, dla kogoś innego, może już nie być takie oczywiste. Ktoś inny może również to po prostu przeoczyć.

Tworząc kod trzeba się starać, aby był możliwie łatwy do zrozumienia, rozszerzania i wprowadzania zmian, a w tym celu w przypadkach podobnych do opisanego wystarczy po prostu użycie trochę inne konstrukcji językowej, która lepiej wyrazi nasze zamiary innym.