PR0GR4M470R5K4 UL0H4

V poslednom čase sa v reálnom živote, ale aj na internete rozpútala zúrivá reklamná kampaň, ktorá má okrem iného osloviť aj programátorov. Nemohol som si ju nevšimnúť, pretože každý deň chodím okolo veľkého reklamného nápisu:

BUĎTE LEPŠÍ AKO VŠETCI HACKERI SVETA.

Všimol som si, že táto reklama obsahuje aj malú programátorskú úlohu. A keďže každý programátor bez výnimky si myslí, že je najlepší na svete, tak ani ja som nemohol odolať a musel som ju kvôli spokojnému spánku vyriešiť.

Znenie úlohy je možné nájsť tu http://www.3537.sk/programator.html, citujem:

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.

Úlohu som rozdelil na dve časti:

1. načítanie celého súboru do pamäte a rozparsovanie obsahu do vhodnej dátovej štruktúry
2. algoritmus, ktorý počíta požadované hodnoty nad touto dátovou štruktúrou

Ďalej sa bodom 1 nebudem zaoberať, pretože ho nepovažujem za dôležitý. Predpokladajme, že máme už celý obsah súboru uložený v List<FileDescription>, kde FileDescription vyzerá takto:

public class FileDescription {
    private String name;
    private List<Long> signature = new ArrayList<Long>();

    public String getName() { return name; }
    public void setName(String name) { this.name = name; }
    public int getSignatureSize() { return signature.size(); }
    public Long getSignature(int index) { return signature.get(index); }
    public void addSignature(long signature) { this.signature.add(signature); }
}

Je to obyčajný value object, ktorý obsahuje meno súboru, a podpis, ktorý je List Long-ov, pretože do Java int-u sa 32-bitové číslo nezmestí. (kvôli znamienku)

Riešenie 1 (Java):

Najjednoduchšie riešenie spočíva v tom, že najprv zoradíme FileDescription prvky v Liste podľa veľkosti podpisu od najväčšieho po najmenší a potom prejdeme každý prvok v Liste od začiatku a skontrolujeme, či má nejaké duplikáty. Ak na nejaký duplikát narazíme, proste ho z Listu vymažeme. Na konci metódy nám v Liste ostanú iba unikátne (jedinečné) súbory.

    private static class FileDescriptionComparatorLargestFirst implements Comparator<FileDescription>, Serializable {
        public int compare(FileDescription fileDescription1, FileDescription fileDescription2) {
            if (fileDescription1.getSignatureSize() < fileDescription2.getSignatureSize()) return 1;
            if (fileDescription1.getSignatureSize() > fileDescription2.getSignatureSize()) return -1;
            return 0;
        }
    }

    public int calculateNumberOfUnique1P(List<FileDescription> fileDescriptions) {
        Collections.sort(fileDescriptions, new FileDescriptionComparatorLargestFirst());
        for (int i = 0; i < fileDescriptions.size(); i++) {
            FileDescription outerFileDescription = fileDescriptions.get(i);
            for (int j = i + 1; j < fileDescriptions.size(); j++) {
                FileDescription innerFileDescription = fileDescriptions.get(j);
                if (outerFileDescription.getSignatureSize() > innerFileDescription.getSignatureSize()) {
                    boolean equal = true;
                    for (int k = 0; k < innerFileDescription.getSignatureSize(); k++) {
                        if (!innerFileDescription.getSignature(k).equals(outerFileDescription.getSignature(k))) {
                            equal = false;
                            break;
                        }
                    }
                    if (equal) {
                        fileDescriptions.remove(innerFileDescription);
                        j--;
                    }
                }
            }
        }
        return fileDescriptions.size();
    }

• algoritmus využíva 3 vnorené for cykly, čo na prvý pohľad naznačuje, že nebude príliš výkonný, ale malý test súbor set_small.dat spracuje bez problémov v zlomku sekundy
• taktiež výsledok zahŕňa List s unikátnymi súbormi a nielen ich počet (aj keď metóda vracia iba číslo)
• vyskúšal som metódu aj na veľkom súbore set_large.dat, ale aby sa súbor vôbec načítal do pamäte je potrebné pridať pamäť pre JVM oproti štandardnému nastaveniu, napríklad takto -Xms128m -Xmx1024m
• kým sa algoritmus dopracoval k výsledku prešlo viac než 20 minút, takže "Tudy cesta nevede." :)

Riešenie 2 (Java):

Druhý algoritmus rozdelí súbory z Listu do Mapy Listov podľa ich podpisu, najprv podľa prvého čísla v podpise a potom odstráni na tej úrovni všetky duplikáty a unikátne súbory z Listu a opakuje tú istú procedúru pre všetky Listy v Mape rekurzívne. Týmto spôsobom sa dá dosiahnuť minimalizácia porovnávania podpisov jednotlivých súborov.

    public int calculateNumberOfUnique2P(List<FileDescription> fileDescriptions) {
        List<FileDescription> uniques = new ArrayList<FileDescription>();
        List<FileDescription> duplicates = new ArrayList<FileDescription>();

        recurseFileDescriptionListP(fileDescriptions, 0, uniques, duplicates);

        return uniques.size();
    }

    private void recurseFileDescriptionListP(List<FileDescription> fileDescriptions, Integer level, List<FileDescription> uniques, List<FileDescription> duplicates) {
        if (level > 0) {
            if (fileDescriptions.size() == 1) {
                uniques.add(fileDescriptions.get(0));
                return;
            }
            if (fileDescriptions.size() > 0) {
                List<FileDescription> cleanCandidates = new ArrayList<FileDescription>();
                Integer largestSizeInList = 0;
                for (FileDescription fileDescription : fileDescriptions) {
                    if (fileDescription.getSignatureSize() == level) {
                        cleanCandidates.add(fileDescription);
                    }
                    if (fileDescription.getSignatureSize() > largestSizeInList) {
                        largestSizeInList = fileDescription.getSignatureSize();
                    }
                }
                if (cleanCandidates.size() > 0) {
                    if (largestSizeInList.equals(level)) {
                        uniques.addAll(cleanCandidates);
                        return;
                    }
                     if (largestSizeInList > level) {
                        duplicates.addAll(cleanCandidates);
                        fileDescriptions.removeAll(cleanCandidates);
                    }
                }
            }
        }

        Map<Long, List<FileDescription>> longFileDescriptionMap = new HashMap<Long, List<FileDescription>>();

        for (FileDescription fileDescription : fileDescriptions) {
            Long key = fileDescription.getSignature(level);
            List<FileDescription> fileDescriptionList = longFileDescriptionMap.get(key);
            if (fileDescriptionList == null) {
                fileDescriptionList = new ArrayList<FileDescription>();
                longFileDescriptionMap.put(key, fileDescriptionList);
            }
            fileDescriptionList.add(fileDescription);
        }

        for (List<FileDescription> fileDescriptionList : longFileDescriptionMap.values()) {
            recurseFileDescriptionList(fileDescriptionList, level + 1, uniques, duplicates);
        }
    }

• aby sme zabránili pretečeniu zásobníka pri tejto metóde je potrebné upraviť parametre JVM, napríklad takto -Xms128m -Xmx1024m -Xss64m
• výsledkom algoritmu sú 2 nové Listy, jeden obsahuje unikátne súbory a druhý duplicitné
• beh programu pre veľký testovací súbor set_large.dat trvá menej ako jednu sekundu
• pomerne ľahko by sa dal prepísať aby bežal vo viacerých threadoch

Riešenie 3 (C++):

Toto riešenie je prepisom riešenia 2 do iteratívnej podoby, teda ten istý algoritmus, ale bez rekurzie a pretože je napísaný v C++, tak opakujem aj triedu FileDescription.

class FileDescription {
private:
    string name;
    vector<unsigned int> signature;
public:
    string getName() const { return name; }
    void setName(string name) { this->name = name; }
    unsigned int getSignature(unsigned int level) const { return signature[level]; }
    void addSignature(unsigned int signature) { this->signature.push_back(signature); }
    unsigned int getSignatureSize() const { return this->signature.size(); }
};

unsigned int cleanFileDescriptions3P(list<FileDescription*>& fileDescriptions, unsigned int level, unsigned int& uniques, unsigned int& duplicates) {
    if (fileDescriptions.size() == 1) {
        uniques++;
        return 0;
    }
    if (fileDescriptions.size() > 1) {
        list<FileDescription*> toRemove;
        unsigned int largestSizeInList = 0;

        for (list<FileDescription*>::iterator iter = fileDescriptions.begin(); iter != fileDescriptions.end(); ++iter) {
            unsigned int signatureSize = (*iter)->getSignatureSize();
            if (signatureSize == level+1) {
                toRemove.push_back((*iter));
            }
            if (signatureSize > largestSizeInList) {
                largestSizeInList = signatureSize;
            }
        }
        if (toRemove.size() > 0) {
            if (largestSizeInList == level+1) {
                uniques += toRemove.size();
                return 0;
            }
            if (largestSizeInList > level+1) {
                duplicates += toRemove.size();

                for (list<FileDescription*>::const_iterator iter = toRemove.begin(); iter != toRemove.end(); ++iter) {
                    fileDescriptions.remove(*iter);
                }
            }
        }
    }
    return fileDescriptions.size();
}

void calculateNumberOfUnique3P(list<FileDescription*>& fileDescriptions, unsigned int& uniques, unsigned int& duplicates) {
    unsigned int level = 0;
    map<unsigned int, list<FileDescription*> > fileDescriptionMap;
    list<list<FileDescription*> > fileDescriptionsListOfLists;

    fileDescriptionsListOfLists.push_back(fileDescriptions);

    while (!fileDescriptionsListOfLists.empty()) {
        for (list<list<FileDescription*> >::const_iterator outerListIter = fileDescriptionsListOfLists.begin(); outerListIter != fileDescriptionsListOfLists.end(); ++outerListIter) {

            for (list<FileDescription*>::const_iterator innerListIter = (*outerListIter).begin(); innerListIter != (*outerListIter).end(); ++innerListIter) {
                unsigned int key = (*innerListIter)->getSignature(level);
                fileDescriptionMap[key].push_back((*innerListIter));
            }
        }
        fileDescriptionsListOfLists.clear();

        for (map<unsigned int, list<FileDescription*> >::const_iterator mapIter = fileDescriptionMap.begin(); mapIter != fileDescriptionMap.end(); ++mapIter) {
            list<FileDescription*> fileDescriptionsPart = mapIter->second;

            unsigned int unresolvedListFlag = cleanFileDescriptions3P(fileDescriptionsPart, level, uniques, duplicates);
            if (unresolvedListFlag>0) {
                fileDescriptionsListOfLists.push_back(fileDescriptionsPart);
            }
        }
        fileDescriptionMap.clear();
        level++;
    }
}

• výsledkom sú dve čísla a to počet duplicitných a počet unikátnych súborov
• výkon je porovnateľný s riešením číslo 2

Záver:

Moje výsledky:

• set_small.dat: spolu súborov 942, z toho unikátnych 851
• set_large.dat: spolu súborov 106020, z toho unikátnych 96312

Zadávatelia úlohy výsledky nezverejnili, takže nemám možnosť si skontrolovať či som zadanie pochopil správne. Každopádne pokiaľ problém niekto riešil, určite napíšte komentár ako Vám vyšiel, prípadne aj linku na Vaše riešenie.

Čo dodať ku koncu? Netrúfam si síce povedať, že som lepší ako najlepší hackeri sveta. Ale za predpokladu, že najlepší hackeri sveta sú z Číny, som lepší ako najlepší hackeri sveta v jedení lyžičkou. :)

A čo Vy? Ste lepší ako najlepší hackeri sveta?