PALMA junior
Úloha o vyhodnocovaní predaja

Autorské riešenie
[stiahni predaj.py]

• Počet riešiteľov: 9 / 9 = 100 %

• Úspešnosť riešenia: 4,5 / 8 = 56 %

Zo zadania problému vyplýva, že potrebujeme v jednom zozname (záznamy z centrálneho systému) vyhľadávať položky, ktoré zodpovedajú hodnotám v druhom zozname (kódy výrobkov). Na to v princípe vieme navrhnúť jednoduchý algoritmus, napr.: 

def pocty_predanych_vyrobkov_0(kody, zaznamy):
    vysledky = []
    for kod in kody:
        for zaznam in zaznamy:
            if zaznam[0] == kod:
                vysledky.append(zaznam)
                break
        else:
            vysledky.append([kod, 0])
    return vysledky

Problémom je, že "prístup do samotných záznamov o predaji je časovo náročný". Ak máme pre každý kód výrobku prehľadať všetky záznamy o predaji, výsledné riešenie bude veľmi pomalé. Vylepšime riešenie tak, že záznamami o predaji budeme prechádzať len raz: 

def pocty_predanych_vyrobkov_1(kody, zaznamy):
    kody = kody.copy()
    vysledky = []
    for zaznam in zaznamy:
        if zaznam[0] in kody:
            vysledky.append(zaznam)
            kody.remove(zaznam[0])
            if kody == []:
                return vysledky
    for kod in kody:
        vysledky.append([kod, 0])
    return vysledky

Pre každý záznam zistíme, či obsahuje niektorý z hľadaných kódov. Ak áno, pridáme ho do výsledku a zo zoznamu hľadaných kódov ho odstránime. Ak by to bol posledný z hľadaných kódov, prehľadávanie môžeme ukončiť a vrátiť výsledok. Nakoniec zistíme, či zostali nejaké nenájdené kódy. Pre tieto kódy pridáme do výsledku nulové počty predaných kusov.

Toto riešenie je síce šikovnejšie, ale zatiaľ sme nevyužili jednu z vlastností záznamov o predaji. Tieto záznamy sú usporiadané podľa kódov výrobkov. Ak chceme nájsť záznam pre daný kód, nemusíme záznamy prehľadávať po jednom. Môžeme sa pozrieť na záznam, ktorý je v strede. Podľa kódu v tomto zázname vieme, či náš hľadaný záznam bude v prvej alebo v druhej polovici. Takto môžeme pokračovať na štvrtinu, osminu ... až kým nedostaneme časť len s jedným záznamom. Toto riešenie môže vyzerať nasledovne: 

def najdi_poziciu(data, hodnota, od, do):
    while od < do:
        stred = (od + do) // 2
        if hodnota > data[stred][0]:
            od = stred + 1
        else:
            do = stred
    return od


def pocty_predanych_vyrobkov_2(kody, zaznamy):
    vysledky = []
    for kod in kody:
        pozicia = najdi_poziciu(zaznamy, kod, 0, len(zaznamy))
        if pozicia < len(zaznamy):
            if zaznamy[pozicia][0] == kod:
                vysledky.append(zaznamy[pozicia])
            else:
                vysledky.append([kod, 0])
        else:
            vysledky.append([kod, 0])
    return vysledky

Pre samotné hľadanie pozície v záznamoch sme si vytvorili funkciu najdi_poziciu.

Zamyslime sa aj nad tým, akú pozíciu nájde funkcia pre kód, ktorý v záznamoch neexistuje. Nájde pozíciu, kde by tento záznam mal byť, ak by tam bol. Ak hľadaný kód je väčší ako ktorýkoľvek z existujúcich kódov, skončíme za posledným prvkom. Inak skončíme na mieste, kde je nejaký iný záznam. V oboch prípadoch vieme, že záznam pre hľadaný kód neexistuje a preto do výsledku pridáme nulovú hodnotu o predaji.

Toto riešenie je v skutočnosti výrazne lepšie ako tie predchádzajúce. Napriek tomu sa dá ešte vylepšiť. Ak by sme si hľadané kódy vopred usporiadali tak vieme, že záznam pre každý ďalší kód bude až za pozíciou ostatného nájdeného záznamu. Nemusíme teda prehľadávať všetky záznamy, ale len zvyšok do konca. 

def najdi_poziciu(zaznamy, kod, od, do):
    while od < do:
        stred = (od + do) // 2
        if kod > zaznamy[stred][0]:
            od = stred + 1
        else:
            do = stred
    return od


def pocty_predanych_vyrobkov_3(kody, zaznamy):
    vysledky = []
    od = 0
    kody = sorted(kody)
    for kod in kody:
        pozicia = najdi_poziciu(zaznamy, kod, od, len(zaznamy))
        if pozicia < len(zaznamy):
            if zaznamy[pozicia][0] == kod:
                vysledky.append(zaznamy[pozicia])
            else:
                vysledky.append([kod, 0])
        else:
            vysledky.append([kod, 0])
        od = pozicia
    return vysledky

Počiatočnú pozíciu od priebežne upravujeme podľa toho, kde sme našli predchádzajúci kód. Môžeme sa ešte zamyslieť nad tým, koľko času a kde stratíme usporiadaním zoznamu kódov a koľko času a kde týmto naopak získame.

Samotné usporiadanie zoznamu kódov, ktorý obsahuje niekoľko desiatok prvkov je pomerne rýchle. Prístup do samotných záznamov je však pomalý. Tým, že neprehľadávame všetky záznamy, ale len ich časť, pomerne výrazne eliminujeme tieto časové straty.

Aj toto riešenie je ešte možné vylepšiť:

• kódy, ktorých záznamy by mali byť pred prvým alebo za posledným záznamom nemusíme hľadať a do výsledku ich môžeme vložiť s nulovými hodnotami,

• ak by v hľadaných kódoch boli duplicity, záznamy pre rovnaké kódy už nemusíme vyhľadávať,

• ak sme hodnotu kódu v nejakom zázname našli, novú hodnotu od môžeme nastaviť na pozicia + 1.

Implementáciu týchto vylepšení už ponecháme na vás :-)

Vaše zaujímavé riešenia a najčastejšie chyby

Táto úloha bola zameraná na nájdenie efektívneho vyhľadávania. Niektorí z vás zabudli ošetriť alebo korektne ošetriť situáciu, keď hľadaný kód v záznamoch neexistuje. Väčšina z vás použila nejakú verziu lineárneho vyhľadávania. Pokiaľ sú prehľadávané dáta usporiadané, tento prístup nie je veľmi efektívny. Len tri tímy (bobalky_sk guru, file-open guru, oliverseman guru ) sa pokúsili implementovať nejakú verziu binárneho vyhľadávania.

Niektorí z vás "prehodili" záznamy do slovníka. Vyhľadávanie v slovníku je síce veľmi efektívne, ale samotné prehadzovanie záznamov do slovníka je príliš pomalé. Podľa zadania "prístup do samotných záznamov o predaji je časovo náročný". Cieľom teda bolo minimalizovať počet prístupov k záznamom centrálneho systému.