Krahasimi i dy qasjeve

E njëjta punë, dy mënyra për ta bërë

Sapo e di se Big-O mat formën e rritjes, mund ta përdorësh për të zgjidhur një grindje krejt të zakonshme: kur ke dy programe që të dyja e bëjnë punën, cilin duhet të mbash? "Funksionon" nuk është përgjigjja, sepse funksionojnë të dyja. Pyetja e dobishme është si sillet secili kur hyrja pushon së qeni e vogël.

Përfytyro një ngjarje në komunitet. Ke një listë të ftuarish me të gjithë ata që u ftuan, dhe teksa mbrëmja ecën, njerëzit shfaqen te dera një nga një. Për çdo person që vjen do një përgjigje të shpejtë po ose jo: a është ky në listë? Do të shkruajmë dy versione dhe pastaj do të arsyetojmë mbi to.

Qasja e parë: kalo listën çdo herë

Ideja më e drejtpërdrejtë është ta mbash listën e të ftuarve si një listë të thjeshtë Python dhe, për çdo person që vjen, ta shfletosh atë.

def kontrollo_ardhjet_ngadale(te_ftuar, ardhje):
    pranuar = []
    for person in ardhje:
        if person in te_ftuar:    # kjo kalon tërë listën
            pranuar.append(person)
    return pranuar

Testi in mbi një listë nuk është falas. Python duhet të ecë nëpër emrat derisa gjen një përputhje ose arrin fundin. Nëse lista ka n emra dhe vijnë m persona, çdo ardhje mund të kushtojë deri në n krahasime, ndaj e gjitha është rreth m * n punë. Kur të dyja listat rriten bashkë, kjo është zonë O(n²).

Qasja e dytë: ndërto një set fillimisht

Tani bëj një çikë përgatitje. Para se të hapen dyert, derdhe listën e të ftuarve në një set (bashkësi), i cili është bërë për t'iu përgjigjur pyetjes "a ndodhet ky brenda?" thuajse menjëherë.

def kontrollo_ardhjet_shpejt(te_ftuar, ardhje):
    set_te_ftuar = set(te_ftuar)  # një kalim për ta ndërtuar
    pranuar = []
    for person in ardhje:
        if person in set_te_ftuar:  # afërsisht një hap
            pranuar.append(person)
    return pranuar

Ndërtimi i set-it është një kalim mbi listën e të ftuarve, pra n hapa. Pas kësaj, secila nga m ardhjet kushton afërsisht një hap në vend të n. Totali është rreth n + m, që është O(n) kur listat rriten bashkë.

Të arsyetosh se cila shkallëzon më mirë

Të dy funksionet kthejnë të njëjtën listë të pranuarish, ndaj t'i provosh me dhjetë emra nuk të thotë asgjë. Ndryshimi shfaqet vetëm te madhësia. Le të themi se lista e të ftuarve dhe ardhjet janë secila 500 veta. Qasja e parë bën rreth 500 × 500 = 250.000 krahasime. E dyta bën rreth 500 + 500 = 1.000 hapa. E njëjta përgjigje, dhe njëra ka mbaruar para se tjetra të jetë ngrohur.

Versioni i dytë e paguan një çmim të vogël: set-i është një kopje më vete e emrave, ndaj përdor memorie shtesë. Për një listë të ftuarish kjo është pazar i mbarë. Ai këmbim, pak më shumë memorie për ta kthyer punën n² në n, është një këmbim që do ta bësh sërish e sërish, dhe Big-O është ai që të lejon ta shohësh qartë para se të vendosësh.

Para se të vazhdosh, kthehu te çdo cikël që ke shkruar që bën një test in mbi një listë: a do ta ndryshonte Big-O-në kthimi i asaj liste në një set, dhe sa do të të kushtonte kjo shpejtësi në memorie?

Provo veten

1. Të dy funksionet nxjerrin saktësisht të njëjtën listë të pranuarish. Pse kjo nuk mjafton për të vendosur cilin të mbash, dhe cilën pyetje bën në vend të saj?
2. Te qasja e parë, nga vjen kostoja e fshehur, dhe pse e kthen një cikël të vetëm mbi ardhjet në rreth n² punë gjithsej?
3. Versioni i shpejtë ndërton një set, që përdor memorie shtesë. Përshkruaj si do t'ia shpjegoje dikujt pse ia vlen ta shpenzosh atë memorie këtu.