Algorithmau Sy'n Gorffen Mewn Pryd: Gwiriad Cymplethdod yn y Bol

Rydych chi'n ysgrifennu swyddogaeth, yn ei rhedeg ar eich data prawf, ac mae'n gweithio'n dda. Yna mae'n taro data cynhyrchu — 500,000 o resi yn lle 500 — ac mae'r cais yn dod i ben. Mae hyn yn digwydd yn gyson, a bron bob amser mae'n broblem gymhlethdod yn cuddio y tu ôl i god a edrychai'n rhesymol ar raddfa fach.

Pam y dywedodd eich laptop gelwydd i chi

Algorithm O(n²) yn rhedeg ar 100 eitem yn gwneud 10,000 o weithrediadau. Mae hynny'n syth ar unrhyw beiriant. Rhedwch yr un algorithm ar 100,000 eitem ac rydych chi ar 10 biliwn o weithrediadau — funudau neu oriau yn lle millisecondau. Nid yw'r naid o n i n² yn teimlo'n beryglon tan fod n yn dod yn fawr, a dyna'n union pam mae'n llithro trwy adolygiad cod a phrawf lleol.

Enghraifft glasurol: gwirio am ddyblygu gyda dolenni nythu.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Dyma O(n²). Cymerwch y lle gyda set:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Nawr mae'n O(n). Mae chwiliadau set yn O(1) ar gyfartaledd, felly mae'r swyddogaeth gyfan yn graddio'n llinol yn lle'n gwadratig. Ar 10,000 eitem mae hynny'n y gwahaniaeth rhwng oddeutu 100 miliwn o gymhariaethau a 10,000.

Mesur cyn i chi optimeiddio

Na dyfalu. Defnyddiwch timeit ar gyfer microbenchmarciau:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Ar gyfer swyddogaethau mwy, proffil gyda cProfile:

python -m cProfile -s cumulative myscript.py

Edrychwch ar y golofn cumtime. Os yw un swyddogaeth yn bwyta 90% o amser rhediad, dyna eich targed. Mae optimeiddio cod nad yw'n y botel-wddf yn gwastraffu eich amser ac yn ychwanegu cymhlethdod heb yr un llog.

Patrymau cyffredin sy'n dod yn araf yn dawel

Gwiriadau aelodaeth rhestr ailadroddus. Mae if x in my_list yn O(n) ar gyfer rhestr ond O(1) ar gyfartaledd ar gyfer set neu dict. Os ydych chi'n gwirio aelodaeth y tu mewn i ddolen, mae'r gwiriad O(n) hwnnw y tu mewn i ddolen O(n) yn rhoi O(n²) i chi yn gyffredinol. Cymerwch y rhestr ar gyfer set a rydych chi nôl i O(n).

Concatenation llinyn mewn dolen. Yn Python, mae result += chunk y tu mewn i ddolen ar draws llinynau yn O(n²) yn y digwyddiad gwaethaf oherwydd bod llinynau'n annewidiol ac mae pob concatenation yn copïo'r peth cyfan. Defnyddiwch ''.join(chunks) yn ei le — mae'n adeiladu'r llinyn unwaith.

Didoli pan nad oes angen i chi. Mae sorted() yn O(n log n). Os ydych chi'n ei alw y tu mewn i ddolen i ganfod y max neu min pob iteriad yn unig, defnyddiwch max()/min() (O(n)) neu well, heap (heapq) os oes angen yr eithaf rhedeg arnoch chi dro ar ôl tro. Mae heapq.nlargest(k, data) yn O(n log k), llawer yn rhatach na didoli'r rhestr gyfan pan fod k yn fach.

Swyddogaethau ailadroddus heb memoization. Mae Fibonacci ailadroddus naïf yn O(2ⁿ) oherwydd mae'n aildyfynnu'r un is-broblemau dro ar ôl tro. Ychwanegwch functools.lru_cache ac mae'n disgyn i O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Darllen Big O oddi ar god go iawn, yn gyflym

Cyfrwch dolenni nythu dros yr un mewnbwn — dyna yw eich esboniwr fel arfer. Dolen sengl yw O(n). Dolen y tu mewn i ddolen yw O(n²) oni bai fod ystod y ddolen fewnol yn crebachu (fel yn ffurf optimeiddio didoli swigod, O(n²) yn y digwyddiad gwaethaf o hyd ond llai o gymhariaethau). Galwadau ailadroddus sy'n rhannu'r broblem yn ei hanner, fel chwiliad deuol neu didoli uno, yn pwyntio at O(log n) neu O(n log n). Galwadau ailadroddus sy'n canghennu i mewn i alwadau lluosog fesul lefel, fel Fibonacci naïf, yn pwyntio at amser esbonyddol — signal cryf fod angen memoization neu ailysgrifennu iteratif arnoch chi.

Arferiad da: cyn i chi ysgrifennu dolenni nythu neu ailadroddiad dros ddata wynebu'r defnyddiwr, gofynnwch beth y gallai n ei fod yn gynhyrchiadol, nid yn eich ffeil prawf. Os y gallai n daro chwe ffigur, mae angen ail olwg ar ddatrysiad O(n²) cyn iddo gael ei rhyddhau.

Am ragor am ddadansoddiad cymhlethdod, algorithmau didoli, ac offer proffilio, gwiriwch y segmentau Python a Gwyddoniaeth Gyfrifiadur ar Korra Studio.