poniedziałek, 28 maja 2012

Zrozumieć LinkedList

Klasa LinkedList jest w .NET Base Class Library od bardzo dawna (od wersji 2.0) i bardzo rzadko jest używana. Zawsze była dla mnie pewną tajemnicą, więc postanowiłem zrobić parę testów na tej klasie. Ogólny sposób działania linked listy można poczytać na stronie wikipedii. Poniżej przedstawiam w punktach krótką charakterystykę:

1) LinkedList występuje tylko w postaci generycznej (LinkedList<T>).

2) LinkedList nie jest "listą" - to znaczy, że nie implementuje interfejsu IList. Interfejsy z których implementuje LinkedList to:
  • ICollection<T>, ICollection
  • IEnumerable<T>, IEnumerable
  • ISerializable, IDeserializationCallback

Dla uproszczenia słownictwa przyjmujemy, że LinkedList<T> i List<T> będziemy nazywać listą.

3) Metody AddFirst i AddLast określają kolejność zapisywanych obiektów. Możemy w prosty sposób dodać obiekt na końcu listy jak i na początku
NP:
var linkedList = new LinkedList<int>();  
//tworzy LinkedList

            linkedList.AddFirst(1);    
//   1 

            linkedList.AddFirst(2);    
//   2, 1

            linkedList.AddFirst(3);    
//   3, 2, 1


            linkedList.AddLast(4);     
//   3, 2, 1, 4 

            linkedList.AddLast(5);     
//   3, 2, 1, 4, 5

            linkedList.AddLast(6);     
//   3, 2, 1, 4, 5, 6




4) Możemy dodać element do wyznaczonego węzła
var linkedList = new LinkedList<int>();            
//tworzy LinkedList

            var objOne= linkedList.AddFirst(1);                
// 1

            var objTwo =   linkedList.AddAfter(objOne, 2);     
// 1, 2

            var objThree = linkedList.AddBefore(objTwo, 3);    
// 1, 3, 2

            var objFour =  linkedList.AddAfter(objThree, 4);   
// 1, 3, 4, 2

            var objFive =  linkedList.AddAfter(objFour, 5);    
// 1, 3, 4, 5, 2



5) LinkedList nie stosuje się we wszystkich zagadnieniach. Poniżej przedstawiam wyniki czasu działa różnych operacji na LinkedList i List. Wyniki są przedstawiane w milisekundach dla tysiąca, 10 tysięcy, 100 tysięcy oraz miliona elementów w listach. Na początku implementacja:
            var list = new List<int>();
            var linkedList = new LinkedList<int>();
            Stopwatch watchLinkedList = new Stopwatch();
            Stopwatch watchList = new Stopwatch();

5a) Dodawanie elementu na końcu listy.
            watchList.Start();
            for (int i = 0; i < counts; i++)
            {
                list.Add(i);
            }
            watchList.Stop();

            watchLinkedList.Start();
            for (int i = 0; i < counts; i++)
            {
                linkedList.AddLast(i);
            }
            watchLinkedList.Stop();


Wykres jest przedstawiony w skali liniowej. Poniżej tabela z wynikami:

Add Last
 LinkedListList
1,00000
10,00000
100,00091
1,000,00010613
10,000,0002770256

Bardzo dokładnie widać, że czas dodawania elementu na koniec listy dla LinkedList jest większy niż dla List.

5b) Dodawanie elementu na początku listy
            watchList.Start();
            for (int i = 0; i < counts; i++)
            {
                list.Insert(0,i);
            }
            watchList.Stop();

            watchLinkedList.Start();
            for (int i = 0; i < counts; i++)
            {
                linkedList.AddFirst(i);
            }
            watchLinkedList.Stop();


Add First
 LinkedListList
1,00000
10,000025
100,00082347
1,000,00097274540

Wykres jest przedstawiony w skali logarytmicznej. Tutaj dokładnie widać, że czas dla List jest dużo większy od LinkedList. Dla 100 tys. jest około 300 razy większy, a dla miliona elementów jest z 3 000 razy większy.

Sprawdźmy co się stanie, gdy porównamy dla LinkedList metodę AddFirst (dodawanie elementu na początek listy) z metodą AddLast (dodawanie elementu na koniec listy). Okazuje się, że czasy dla tych operacji są bardzo zbliżone.


Add FirstAdd Last
1,00000
10,00000
100,00089
1,000,00097106
10,000,00027752770


5c) Usuwanie podanego elementu z gotowej listy (za pomocą metody Remove(int))

Remove
 LinkedListList
1,00000
10,000024
100,00022370
1,000,00030283608

Czas dla List<T> przy operacji usunięcia elementów jest bardzo duży. Wiąże się to z koniecznością "przebudowania" listy (klasa List<T> jest zaimplementowania za pomocą Array).

5d) Sortujemy elementy. Do tego zastosujemy metodę rozszerzającą OrderBy

OrderBy
 LinkedListList
1,00004
10,00011
100,0001819
1,000,000212233
10,000,00033353092

Czas poświęcony na sortowanie listy dla obu klas jest bardzo podobny.

5e) Dodawanie elementu w sam środek listy
Kod dla List:
for (int i = 0 ; i < counts ; i++)
{
  int center = (int)
        Math.Floor( (double)list.Count / 2 );
  list.Insert( center, i );
}

Kod dla LinkedList:
bool addBefore = false;
LinkedListNode<int> centerNode = linkedList.AddFirst(0); ;
for (int i = 1; i < counts; i++)
{
if (addBefore)
{
  centerNode = linkedList.AddBefore( centerNode, i );
  addBefore = false;
}
else
{
  centerNode = linkedList.AddAfter( centerNode, i );
  addBefore = true;
}
}


Add Inner
 LinkedListList
1,00010
10,000015
100,00091467
1,000,000155148823
10,000,000273619992188

Wykres jest przedstawiony w skali logarytmicznej. Operacja na 10 milionach elementach w LinkedList jest podobnie czasochłonna co operacja na 100 tysiącach dla List. W tym eksperymencie ewidentnie widać, że lepiej jest zastosować LinkedList.

Poniżej jest porównanie 3 operacji. Dodawanie elementu na początek listy, w środek i na koniec list. Wyniki są prawie identyczne.
Add FirstAdd InnerAdd Last
1,000010
10,000000
100,000899
1,000,00097155106
10,000,000277527362770


5f) Przechodzenie po liście. Dla uproszenie sprawdzę wykonania operacji foreach oraz znajdę liczbę maksymalną.

ForeachMax
 LinkedListListLinkedLIstList
1,0000000
10,0000000
100,0001011
1,000,000951511
10,000,0009666165118

Wnioski: LinkedList<T> bardzo dobrze sprawuje się przy modyfikacji (dodawanie i usuwanie) obiektów w liście, natomiast List<T> dobrze sprawdza się przy dodawaniu elementu na końcu listy. Z racja, że LinkedList<T> nie ma indeksu to przechodzenie po liście jest kosztowniejsze niż dla List<T>.


środa, 23 maja 2012

Starter.bat

Każdego dni rozpoczynam pracę od uruchamiania tych samych programów, przeglądania tych samych stron, czytania tej samej poczty. Aby zautomatyzować proces klikania po wszystkich ikonkach i wpisywania tych samych nazw, stworzyłem mały .bat plik



Poniżej przedstawiam skrypt w pliku Starter.bat:
:: uruchamia pocztę outlook i zaznacza kalendarz
start outlook.exe /select outlook:calendar

:: wchodzi na strony za pomocą domyślnej przeglądarki
start http://arekonsoftware.blogspot.com  
start https://mail.google.com/mail/#inbox 

:: startuje aplikacje (devenv to visual studio)
start devenv  "C:\Users\I\Documents\Visual Studio 11\Projects\MyBigSolution.sln" /projectconfig Debug 

:: otwiera plik
start /D "C:\Users\I\Documents\" ToDo.xls  

Skrypt zawiera przykładowe programy do uruchomienia. Największą zaletą takiego skryptu jest prostota. Za pomocą polecenia start uruchamiamy daną aplikację. Wiem, że ta technika nie jest czymś odkrywczym, ale dla mnie taki mały pliczek pozwala mi na zautomatyzowanie powtarzalnych czynności. Ta technika jest przydatna, jeżeli masz więcej niż 5 aplikacji do uruchomienia.


Aggregate - One Method to rule them all

LINQ w C# wywarł ma mnie ogromny wpływ. Za pomocą tej technologii mogłem operować na obiektach tak jak za pomocą SQLa. Na przykład przy użyciu metod Where i Sum mogłem prosto i szybko sumować liczby, które są parzyste. Problem pojawia się kiedy chciałbym wykonać coś bardziej skomplikowanego lub złożonego, na przykład obliczyć odchylenie standardowe. Pierwsze rozwiązanie jakie przychodzi mi do głowy to stworzenie metody do obliczenia. Takie rozwiązanie jest dobre, więc kiedyś stworzyłem projekt z samymi extension metods. Projekt można pobrać z codeplex.com. Ale czy za każdym razem należy tworzyć nową metodę? Czy nie możemy zastosować już dostępnych metod do manipulacji kolekcją danych? Z pomocą przychodzi nam niedoceniana metoda Aggregate. Ta funkcja jest do agregacji elementów. Poniżej przedstawiam jej zastosowanie.



Na początku zastąpię proste metody jak suma, count, all i concat za pomocą aggregate.

var ints = Enumerable.Range(0, 10);
var sum1 = ints.Sum();
var sum2 = ints.Aggregate( ( agg, item ) => agg + item );


var count1 = ints.Count();
var count2 = ints.Aggregate(0,(agg, item) => agg + 1, x=>x);

var median1 = ints.ElementAt(ints.Count()/2);
var median2 = ints.Aggregate( 0, ( info, item ) => info = info + 1,
                             x => ints.ElementAt( x / 2 ) );

var all1 = ints.All(x => x > -1);
var all2 = ints.Aggregate( true,
               ( info, item ) =>
               {
               if (info == true && item > -1)
               {
                  return true;
               }
                  return false;
               },
               x => x);


var secondInts = Enumerable.Range(12, 3);
var concat1 = ints.Concat( secondInts );
var concat2 = secondInts.Aggregate( new List<int>( ints ),
              ( list, i )=> { list.Add( i ); return list; },
               list => list );
                     
Ok, to teraz bardziej statystyczne funkcje.
var range1 = ints.Max() - ints.Min();
var range2 = ints.Aggregate( new
{ Max = ints.First(), Min = ints.First() },
( x_range, item ) =>{
     var max = x_range.Max;
     var min = x_range.Min;
     if (max < item)
         max = item;
     
     if (min > item)
         min = item;
     
     return new {Max = max, Min = min}; },
     x_range => x_range.Max - x_range.Min);



var intsRepeatable = ints.Concat( new List<int> { 1, 2, 2, 5, 6 } );
var mode1 = intsRepeatable
            .ToLookup( x => x )
            .OrderByDescending( x => x.Count() )
            .Select( x => x.Key ).First();

var mode2 = intsRepeatable.Aggregate( new Dictionary<int, int>(),
                          ( dic, item ) =>
                          { if (dic.Keys.Contains( item ))
                                dic[item]++; 
                           else
                                dic.Add( item, 1 ); 
                           return dic;
                          },
                          dic => 
                              dic.OrderByDescending( x => x.Value )
                                 .First())
                          .Key;

        

A na koniec ciekawsze smaczki, czyli średnia krocząca dla 3 okresów i odchylenie standardowe.
int movingMeanCounter = 3;
var movingMean3 = ints.Aggregate(
                    new
                    {
                    List = new List<List<int>>(),
                    Counter = 0
                    },
                    ( info, item ) =>
                    {
                        info.List.Add( new List<int>() );
                        for (int i = 0 ; 
                        i < movingMeanCounter 
                            && info.Counter - i >= 0 ; 
                        i++)
                        {
                        var vList = info.List[info.Counter - i];
                        vList.Add( item );
                        }

                        return new
                        {
                        List = info.List,
                        Counter = info.Counter + 1
                        };
                    },
                    x => x.List.Select( item => item.Average() ));

var stdDev = ints.Aggregate( new
                    {
                    Mean = 0,
                    Sum = 0,
                    i = 0
                    },
                    ( info, item ) =>
                    {
                        var i = info.i + 1;
                        var delta = item - info.Mean;
                        var mean = delta / i;
                        var sum = info.Sum + delta * (item - mean);
                        return new
                        {
                            Mean = mean,
                            Sum = sum,
                            i = i
                        };
                    },
                    x => x.i < 2 
                        ? 0 
                        : Math.Sqrt( x.Sum / (x.i - 1) ));            

Możemy wiele ciekawych rzeczy zrobić za pomocą aggregate. Gdybyś miał pomysł na zastosowanie tej metody to jestem otwarty na propozycje. Więcej o niej można poczytać tutaj.

piątek, 11 maja 2012

Skyrim Videos

Ostatnimi czasy zająłem się grą Skyrim. Nie będę opisywał tej czasochłonnej gry, ale chciałbym zwrócić uwagę na pewne zjawisko związane z tą grą. Chodzi o filmiki instruktarzowe. Skyrim jest grą nieliniową, można wchodzić w interakcję z postaciami, każde zdarzenie wpływa na dalszą rozgrywkę, zadania w grze można wykonać na wiele sposobów, świat w grze jest bardzo duży, a naszą postać można dowolnie rozwijać. Te cechy spowodowały, że bardzo dużo graczy zamieszcza filmiki z prostymi wskazówkami.



Aby przybliżyć ci tą grę przedstawiam ci pierwszy filmik z pierwszymi 10 minutami gry. Spolszczenie Skyrim można uznać za bardzo dobre. Dobra obsada postaci.



Filmiki instruktarzowe pomagają, aby w łatwy sposób przejść grę. Aby przejść grę musisz wypełniać misje.Jedna z najciekawszych misji do wykonania jest przedstawiona poniżej:



A tutaj jest przedstawiony filmik jak uzyskać 81 poziom postaci (maksymalny poziom):



W tym filmiki jest przedstawiony sposób w jaki można zdobyć nieskończenie wiele pieniędzy:



Powstają też filmiki w jaki sposób można zdobyć wybrany przedmiot:



Świat Skyrim jest pełny niezliczonej liczby (może ktoś policzył) misji. Niektóre zadania są ukryte. Poniższy filmik przedstawia taką misje:



Filmik przedstawia jak można być niewidzialny:



Skyrim nie jest wolny od dziur. Błędy w grze można wykorzystać między innymi w uzyskaniu ponadprzeciętnych umiejętności:





Popularność wśród filmików instruktarzowych zdobywają speedrunery, w których to filmikach przedstawiona jest możliwość bardzo szybkiego przejścia całej gry. Skyrim można przejść w 2 godziny i 50 minut wykonując tylko zadania główne oraz unikając walki z przeciwnikami:



Teraz przestałem grać. Może w przyszłości będę kontynuował walkę ze smokami. Zapisałem grę na ogólnodostępnej przestrzeni. Moja postać ma 80 poziom oraz 20 punktów do wykorzystania na dowolne cechy w umiejętnościach. Poniżej save mojej postaci:



A gdybyś chciał poczytać więcej o Skyrim to polecam wiki's tutaj lub tutaj.

czwartek, 3 maja 2012

Algorytmy sortowania

Aby poćwiczyć algorytmikę napisałem parę algorytmów sortowania i sprawdziłem czasy ich działania. Porównałem 12 algorytmów sortowania (m.in. Bubble Sort, Cocktail, Counting Sort, Insert Sort, Merge Sort, ShellSort, Stooge Sort). Kod z algorytmami sortowania można pobrać z github.com/arekbee/SortEngines. Podczas pisania nie kierowałem się złożonością obliczeniową tych algorytmów, ale byłem ciekaw w jakim czasie mogę posortować tablicę z liczbami.

Jak wiadomo, czas sortowania zależny jest od danych. Dane do posortowania składały się z liczb naturalnych. Każdy z algorytmów został sprawdzony pod 6-ma rożnymi tablicami danych. Pierwszy typ danych składał się z liczb losowych (random). Dla każdego algorytmu były te same dane. Drugi typ składał się z tablicy, w której pierwsza liczba była maksymalną liczbą, a pozostałe elementy były już posortowane w sposób rosnący (increasing). Następnym typem danych był modyfikacją poprzedniej tablicy poprzez wprowadzenie powtórzeń wartości tej tablicy (increasing-repeated). Ilość powtórzeń wynosiła wartość pierwiastka z ilości elementów w tablicy (jeżeli elementów w tablicy było 10 000 to ilość powtórzeń jednego elementu wynosiła 100). Skoro już była tablica "prawie" posortowana w sposób rosnąco to następnym typem danych była tablica posortowana z sposób malejąco, ale pierwszy element wynosił 0 (decreasing). Analogicznie, do następnego typu danych wprowadzono modyfikację poprzez powtarzanie tych samych elementów (decreasing-repeated). Ostatnim typem danych była tablica składająca się z jedynki i samych zer (onezero). Algorytm o nazwie BuildInNet to standardowy algorytm sortowania listy przygotowany przez MS i jest on zaimplementowany jako agorytm Quicksort.

Poniżej jest przedstawiony wykres w skali logarytmicznej z czasem działania algorytmów dla losowo wygenerowanych danych. Oś odcięta stanowi grupę ilości danych ( odpowiednio 10, 100, 1 000, 10 000 i 100 000 elementów w tablicy), a oś rzędnych przedstawia czas działania algorytmu w milisekundach.



A poniżej są tablice z wynikami sortowania. Wartości czasu sortowania są przedstawione w milisekundach.


Jak widać w poniższej tablicy, wprowadzenie powtarzalnych elementów nie zmienia znacząco czasu działania algorytmów.





Jak widać na powyższych tabelkach, 3 algorytmy działają stosunkowo długo oraz nie mają znaczenia czy dane są posortowane w postaci rosnąco czy malejąco. Te algorytmy to: Odd-Even sort, Selection i Stooge sort. Takie algorytmy jak Quicksort, BuildInNet Counting i ShellSort działają równie szybko dla tablicy prawie posortowanej rosnąco jak i malejąco. Dla tablicy z jedną modyfikacją (onezero) oraz z prawie posortowaną tablicą (increasing), selection sort ma gorszy wynik czasu sortowania niż dla algorytmów bubble sort, comb sort czy sortowanie gnoma, mimo że dla innych danych te algorytmy są szybsze.
Algorytm Stooge sort ma najgorszą złożoność obliczeniową. Dla 10 000 elementów czas działania był o 3 rzędy wielkości większy niż dla słabych algorytmów. Sortowanie zostało zatrzymane dla 100 0000 elementów,gdyż czas sortowania wynosił 489 557 429 ms, a to jest ... strasznie długo. W przybliżeniu stanowi to 5 dni i 15 godzin. Gdy sprawdzałem dane, to okazało się, że dane zostały posortowane do 48 147 elementu. Dla tablicy liczącej do 1000 elementu nie ma znaczenia jaki algorytm zastosujesz z sortowaniu (za wyjątkiem nieszczęsnego stoogesorta).
Do dalszych testów wybrałem 6 najlepszych algorytmów. W śród nich są: Counting, Quicksort, Shellsort, Mergesort, Insertsort i dla porównania BuildInNet (algorytm Quicksort w BCL). Poniższy wykres przedstawia czas sortowania w skali logarytmicznej dla poszczególnej ilość danych (1000, 10 000, 100 000 i 1 000 000 elementów).





Z tego można wybrać 4 najlepsze algorytmy. Poniżej wykres dla tablicy z danymi losowymi (random) w skali liniowej (OY przedstawia czas działania algorytmu w milisekundach).




W trakcie przerwy w pisaniu algorytmów miałem możliwość zainteresowania się tańcami ludowymi:)








Bardzo mi się podobają filmiki przedstawiające algorytmy sortowania za pomocą tańców. Jestem bardzo ciekaw jak można by było przedstawić jakiś algorytm za pomocą ruedy z salsy :) Może problem ucztujących filozofów.