pondělí 28. listopadu 2011

Složitost O(n)

Pokud softwarový designer navrhuje celý aplikační systém a vytváří vlastnosti tohoto systému jen z případu užití - Use cases, očekává od systému něco co navrhl. Dle mého názoru by si ale měl i designér, který není programátorem měl uvědomit, že jeho návrhy mohou významně ovlivnit většinu algoritmů v systému. Výsledkem čehož je pomalejší provádění všech algoritmů a větší čas potřebný ke zpracování. Vezměme si například geniální myšlenku využívání dynamických datových struktur namísto statických. A k tomu si přidejme navíc využívání multihodnot namísto jednohodnotových položek.

Poznámka:
Příkladem multihodnoty z běžného života je telefon. Mohu mít více telefonních čísel, proto se hodnota telefon v dynamické struktuře vyskytuje vícekrát.

Podívejme se na to, jak se změní v celém systému složitosti algorimu po zavedení dynamických datových struktur. Pro zjednodušení neuvažujeme že hodnotou u dynamické datové struktury může být jakýkoliv datový typ, vliv variantního typu a nutnosti přetypování je zanedbán.

A . Máme statickou datovou strukturu
LibraryElement
• elementID
• Artist[50]
• Title[50]

B. Máme dynamickou datovou strukturu
LibraryElement – je pole
Item[1] – elementID
Item[2] – Artist
Item[3] – Artist
.
.
.
Item[10] – Title
Zpracování jedno údaje ve struktuře má složitost O(1).
Zpracování jedné informace
Příklad 1. Abych zobrazil jednu položku např. Artist potřebuji složitost
M – počet atributů nebo chceteli počet položek ve struktůře
A. O(1)
B. O(2) – obecně O(M)

Zpracování pole informací – zpracování celé knihovny
Příklad 2. Zobrazení knihovny o N prvcích
A – počet zobrazovaných atributů
A. O(N*A)
B. O(N*A*M)
Příklad 3.Třídění informací – quicksort O(N log2 N)
A. O(N log2 N)
B. O((N*M) log2 (N *M))
Příklad 4. Přenos informací – složitost potřebná k serializaci a deserializaci

A. O(N) – u statické struktůry tedy mohu mluvit jednoduše o přenosu X KB/s
Vím, že chci úřenést (2b + 50+50) * N
B. O(N*M) - u statické struktury není správné mluvit o X KB/s … protože proces serializace a deserializace má mnohem větší složitost

WPF - Každé okno v aplikaci má vlastní vlákno - STA = Single threaded apartments, MTA = Multi-Threaded Apartments

Ve chvíli, kdy založíte nový projekt ve Visual Studio, vygeneruje se vám základní kostra aplikace. Která podle typu projektu WinForm nebo WPF vytvoří vstupní bod aplikace.

WinForm - funkce main
WPF - funkce main je skrytá, ale je možné ji přetížit a napsat si vlastní

Funkce main je vstupním bodem aplikace a je prováděna v hlavním vlákně aplikace (MainThread). Toto vlákno je nastaveno jako STA - Single thread apartments. Každé okno, které vytvoříme v aplikaci běží v rámci toho STA (kontejnéru na vlákna). Pokud budeme chtít vytvořit jiné vlákno, které bude provádět nějakou činnost, tak toto vlákno má nastaven apartments na MTA (multi-thread apartments). Data z tohoto vlákna můžeme synchronizovat do okna aplikace pomocí dispečeru.

myThread = new Thread(new ThreadStart(Execute));
myThread.Start();

V tomto vlákně máme nějaká omezení. Nemůžeme v něm vytvářet okna, ovládací prvky atd. Pokud chcete vytvořit nové okno v rámci jiného vlákna než je hlavní vlákno aplikace, vytvořte nové vlákno, ale nastavte mu apartments na STA.

myThread = new Thread(new ThreadStart(Execute));
myThread.Name = "Thread";
myThread.SetApartmentState(ApartmentState.STA);
myThread.IsBackground = true;
myThread.Start();

Nyní máme vytvořeno okno, ve kterém můžeme vytvořit nezávislé okno, ale aby okno fungovalo, musíme v rámci tohoto vlákna spustit dispečeram který se bude starat o případné synchronizace s jinými vlákny. Bez dispečera nebude okno fungovat.

oid Execute()
{
  MyWindow win = new MyWindow();
  win.Show();

  System.Windows.Threading.Dispatcher.Run();
}

Nezávislé okno máme hotovo.

Závěr
Hledal jsem příčinu, proč jsou takto pod .NETem vlákna řešena. Toto řešení se mi zdálo zbytečně komplikované. Ve většině článků bylo odůvodnění, že je to z důvodů zpětné kompatibility s COM objekty. Do hlubšího zkoumání jsem se už nepouštěl!

čtvrtek 24. listopadu 2011

1. Paralerní programování - Datový paralelismus

V .NET frameworku 4 můžeme využívat tzv. datový paralelismus. Pokud máme v aplikaci nějaký sekvenční algoritmus, který například prochází nějaké velké pole (vřádu desítek tisíc položek), tak může operace trvat dlouho, což může mít za následek výtuhnutí (zaneprázdnění) hlavního vlákna.

1. Příklad - Potřebujeme setřídit data, ale třídíme velké množství položek - sekvenčně pomocí LINQ

public void Sort()
{            
 _log.Debug("Begin Sort!"); 
 var elements = (from val in this select val).OrderBy(a => a, _comparer);
 List<LibraryElement> sort_list = elements.ToList();
 base.Clear();
 base.AddRange(sort_list); 
 _log.Debug("End Sort!"); 
}

Stejný příklad pomocí datového paralelizmu
2. Příklad - Potřebujeme setřídit data - paralelně pomocí PLINQ

public void Sort()
{            
 _log.Debug("Begin Sort!"); 
 var elements = (from val in this.AsParallel() select val).OrderBy(a => a, _comparer);
 List<LibraryElement> sort_list = elements.ToList();
 base.Clear();
 base.AddRange(sort_list); 
 _log.Debug("End Sort!"); 
}

Data jsme setřídili mnohem rychleji, protože TPL nabízí jednoduchý způsob, jak v aplikaci umožnit paralelní zpracování – tedy co nejefektivnější zpracování dat s využitím všech dostupných jader procesoru.

středa 23. listopadu 2011

Paralelní programování v .NET

Knihovna TPL je rozhraní API ze jmenných prostorů System.Threding, System.Threading.Tasks v .net frameworku 4. Knihovna umožňuje paralelně zpracovávat úlohy (tasks), která úkoly rozkládá dyamicky na všechny procesory. Použití TPL rozloží požadovaný úkol na části, které naplánuje do vláken a spouští s využitím fondu vláken ThreadPool (design pattern). Při provádění úlohy máme požnost sledovat stav provádění nebo úlohu přerušit.

Knihovna TPL se dělí:
Datový paralelizmus
Úkolový paralelizmus
PLINQ

SyntaxColor Highlighter

Konečně jsem si sehnal obarvovač zdrojového kódu, abych zde mohl uveřejňovat zdrojové kódy.
Inspiroval jsem se na stránkách:
http://xtractpro.com/tools/CSharp-Highlighter.aspx


Test:


    
    
    public partial class App : Application
    {
        

        protected override void OnStartup(StartupEventArgs e)
        {
            base.OnStartup(e);
            ModulesManager bootstrapper = new ModulesManager();            
            bootstrapper.Run();
            bootstrapper.PostCreate();            
        }

        public void ApplyLocalSkin(Uri skinDictionaryUri)
        {
            
            ResourceDictionary skinDict = Application.LoadComponent(skinDictionaryUri) as ResourceDictionary;

            Collection<ResourceDictionary> mergedDicts = base.Resources.MergedDictionaries;
            
            
            
            
            if (mergedDicts.Count > 0)
                mergedDicts.Clear();

            
            
            mergedDicts.Add(skinDict);
        }

        public void ApplyFileSkin(string file)
        {
            using (FileStream fs = new FileStream(file, FileMode.Open))
            {
                ResourceDictionary dic = (ResourceDictionary)XamlReader.Load(fs);
                Resources.MergedDictionaries.Clear();
                Resources.MergedDictionaries.Add(dic);
            }
        }

    }