PR0GR4M470R5K4 UL0H4

Tento blogový príspevok je čisto o programovaní a matematike. Koho tieto oblasti nezaujímajú, odporúčam nečítať ;) Málokto z programátorskej komunity mohol prehliadnuť Esetácku domácu úlohu. Úlohu dali na web a ak ju pošleš dobre vyriešenú Esetu tak máš šancu u nich na zamestnanie. Nie že by som sa uchádzal u nich o zamestnanie, to zatiaľ nie. Dlho som odolával, ale po tom čo som videl ako sa s ňou trápi moje okolie, tak som neodolal a venoval som jej jeden večer. Ale musím priznať, že treba pripočítať takú hodinku až dve, ktoré som využil na rozmyslenie si ako na to. Zadanie Máte zoznam súborov, v ktorom je každý súbor identifikovaný menom a podpisom. Meno je ľubovoľný reťazec v úvodzovkách a podpis je postupnosť nezáporných 32-bitových čísiel v šestnástkovej sústave ako môžete vidieť na obr. 01. "test_name" 3a 45ffa2 236da0 34cc 21 "/usr/stdio.h" 456fa 34dd 28ab9 457e ".other.txt" 5623d ff3a21 783d 22456 Obr. 01: formát zoznamu súborov Vašou úlohou je nájsť počet jedinečných súborov v zozname. Súbor je považovaný za jedinečný, ak jeho podpis nie je riadnym prefixom podpisu akéhokoľvek iného súboru v zozname. Podpis s1 je považovaný za riadny prefix podpisu s2 vtedy (a len vtedy), keď s2 začína s s1 a podpisy majú rôzne dĺžky. V prípade, že viaceré súbory majú rovnaký podpis, započítajte ich všetky. Viac sa môžete dozvedieť na linke http://www.3537.sk/programator.html. Riešenie V prvom rade si musíme rozmyslieť ako budeme uchovávať údaje. Najjednoduchší spôsob by asi bol, načítať všetko do pamäte do poľa . V danom prípade by sme sa mohli hrať s tým poľom rôznym spôsobom. Napríklad utriediť ho a potom porovnávať iba susediace prvky a prefixové podpisy označovať. Nakoniec jednoducho spočítať neoznačené prvky. V tomto prípade by bolo sortovanie časovo najdlhšou operáciou. Využitie pamäte by bolo dosť obrovské, ale viac na záver v časti úvah. Spôsob, akým ja chcem ukladať údaje je les - teda viac stromov. Prvé číslo podpisu by bol koreň stromu. Nasledujúce číslo by bolo jeho dieťa a ďalšie číslo dieťa dieťaťa, a tak ďalej. Každý prvok stromu by mal smerník na prvého syna a zároveň smerník na ďalšieho syna otcovského uzla. Každý uzol okrem týchto dvoch smerníkov obsahuje aj DWORD hodnotu uzla a koľko krát bol už uzol započítaný. O poslednej premennej si povieme viac za chvíľku pri popise akým spôsobom budeme napĺňať strom. Naplňanie stromu bude prebiehať nasledujúcim spôsobom:

while (fileReader.ReadNext())
   memory.AddSignature(fileReader.CurrentItems(), fileReader.CurrentItemsCount());

Pričom fileReader je trieda, ktorá načítava údaje riadok po riadku a fileReader.CurrentItems() je smerník na pole DWORDov aktuálneho riadku fileReader.CurrentItemsCount() je počet DWORDov získaných z predchádzajúcej funkcie Fungovanie AddSignature vidno na obrázku

obr.2

Tento algoritmus zatiaľ len napĺňa les ale nedovolí nám vypočítať počet jedinečných súborov. V tomto momente by problém spôsobovali duplicitné podpisy. Ak by duplicitné podpisy neexistovali tak by stačilo spočítať počet listov stromu. Riešením by bolo v každom liste mať premennú ktorá by počítala početnosť. To by sa dalo počítať tak, že po ukončení algoritmu v danej funkcii zistiť, či posledne spracovávaný otec má nejaké dieťa a ak nie tak zvýšiť početnosť v danom otcovi. No a potom už nepočítať počet listov ale počítať s početnosťou listov, teda podpisov končiacich v danom liste. Tento postup by ale znamenal post-proces po vytvorení dát a ak by sa dalo tak by bolo dobré sa mu vyhnúť. Hlavne v prípade, že výsledok sa dá počítať priebežne bez veľkých nárokov na pamäť a procesor. A to sa jednoduchým spôsobom dá. Potrebujeme jednú premennú ktorá bude udržiavať aktuálnu hodnotu. Potom necháme počítanie početnosti listov, ale v momente ako zvyšujeme početnosť v liste tak zvýšime hodnotu aj v aktuálnej premennej. V tomto momente nám spôsobujú problém iba listy, ktoré prestanú byť listami pri pridaní nového podpisu. A to sa deje na jedinom mieste v algoritme a to je v oranžovom obdĺžniku na obr.2. Stačí nám pridať odpočítanie početnosti daného uzla (bývalého listu) od aktuálnej premennej. Ešte jednu vec treba popísať a to je zelený obdĺžnik - Inicializácia údajov. Potrebujeme inicializovať hodnoty otca a dieťaťa. Otec na začiatku neexistuje a teda je NULL. Problém je s dieťaťom. Les máme našťastie spravený tak ako keby to bol strom, len koreň je virtuálny, teda máme pospájané korene pomocou smerníkov Ďaľší. Okrem prvého podpisu keď je aj dieťa neexistujúce, stačí nastaviť dieťa ako prvý koreň. Algoritmus sa už postará o zvyšok prehľadaním všetkých koreňov. Druhý spôsob je vytvoriť si hashovaciu mapu. Kľúč by bola prvá hodnota podpisu. Hodnota by zas bol smerník na prislúchajúci koreň hodnoty kľúča. Rozdeľ v spracovaní je pri týchto dvoch postupoch markantný. Testy na Eseťáckom set_large.dat v prvom prípade trvali cca 150s a v druhom prípade iba 1.5s. Celá funkcia vyzerá potom takto

template<typename T>
void CMemory<T>::AddSignature(T * values, int count)
{
    if ( !count)
        return;

    MemoryItem<T> *child = NULL;
    MemoryItem<T> *parent = NULL;

    stdext::hash_map <T, MemoryItem<T> *>::iterator iter = m_TopItems.find(*values);

    if ( iter != m_TopItems.end())
        child = iter->second;

    bool topItem = true;

    for ( int i = 0; i < count; i++)
    {
        if ( !child)
        {
            MemoryItem<T> *newItem = Add( values[ i]);
            if ( topItem)
            {
                std::pair <T, MemoryItem<T> *> p( *values, newItem);
                m_TopItems.insert(p);
            }

            if (parent)
            {
                m_Counter -= parent->Count;
                parent->Count = 0;
                parent->Child = newItem;
            }

            parent = newItem;
            child = NULL;
        }
        else
        {
            T &curValue = values[ i];
            MemoryItem<T> *last = NULL;
            bool found = false;

            while (child)
            {
                last = child;

                if ( child->Value == curValue)
                {
                    parent = child;
                    child = parent->Child;
                    found = true;

                    break;
                }

                child = child->Next;
            }

            if ( !found)
            {
                MemoryItem<T> *newItem = Add( curValue);
                last->Next = newItem;
                parent = newItem;
                child = NULL;
            }
        }

        topItem = false;
    }

    if ( parent)
    {
        if ( !parent->Child)
        {
            parent->Count++;
            m_Counter++;
        }
    }
}

A zabudol som poznamenať, že dátová časť je spravená cez template funkcionalitu, takže miesto DWORDu sa dá použiť ľubovoľný typ ktorý podporuje porovnanie (==). Ďalším dôležitým faktorom rýchlosti je aj akým spôsobom sú ukladané dáta. Ja nealokujem jednotlive malé štruktúry ale mám list väčších polí, pričom ten list podla potreby rozširujem. A sme hotový. Stačí už len výpis:

std::wcout << L"Unique items : " << memory.GetCount() << std::endl << std::endl;

Záver No čo na záver? Výsledky pri Eseťáckych súboroch set_small.dat 851 set_large.dat 96312 Ešte budem musieť doplniť pár úvah o pamäťovej a procesorovej náročnosti. Do konca roka to snáď stihnem :) Zdrojový kód Môj kód som poslal do Esetu tak prosím nezneužite ho a nepošlite len jeho upravenú verziu. Eset.zip