Optimalizační historka

Jednoho dne mi kamarád položil zdánlivě jednoduchou otázku: "Jaký je nejlepší způsob převodu seznamu celých čísel na řetězec, pokud každé číslo vyjadřuje ASCII hodnotou nějakého znaku?". Například, seznam [97,98,99]? by měl být převeden na řetězec 'abc'. Předpokládejme, že k tomu chceme vytvořit jedinou funkci.

První verze, se kterou jsem přišel, byla naprosto přímočará:

def f1(seznam):
      retezec = ""
      for polozka in seznam:
          retezec = retezec + chr(polozka)
      return retezec
"Tohle ale nemůže být ten nejrychlejší způsob", namítl kamarád. "Co třeba toto:"
def f2(seznam):
      return reduce(lambda retezec, polozka: retezec + chr(polozka), seznam, "")

Tato verze vykonává zcela stejné řetězcové operace, jako verze první, ale dokáže se vyhnout zbytečným režijním nákladům smyčky for pomocí rychlejší smyčky ve funkci reduce().

"Samozřejmě", odpověděl jsem, "ale moc si nepomůžeme - cena volání funkcí (lambda funkce) pro každou položku obsaženou v seznamu je poměrně vysoká. Vsadím se, že to bude pomalejší, režije volání funkcí v Pythonu je větší než režije smyčky for".

(Ok, udělal jsem porovnání a f2() trvá o 60% déle než f1(). Takže asi tak :-) )

"Hmm", odvětil kamarád. "Ale já to potřebuji mít ještě rychlejší". Nabídl jsem mu tedy následující verzi:

def f3(seznam):
    retezec = ""
    for znak in map(chr, seznam):
        retezec = retezec + znak
    return retezec

K překvapení nás obou byla funkce f3() dvakrát rychlejší než funkce f1()! Důvody, proč nás to tak překvapilo byly dva: za prvé, funkce používá více paměti (výsledkem map(chr,seznam) je další seznam stejné délky); a za druhé, funkce obsahuje dvě smyčky oproti jediné v f1() (jedna smyčka je zahrnuta ve funkci map() a druhá je smyčka for).

Jasně, správné použití prostoru versus času je dobře známá věc, takže první důvod by nás tak překvapit neměl. Jak je ale možné, že dvě smyčky jsou rychlejší než jedna? Vysvětlením jsou dva důvody.

První, v f1() je funkce chr() vyhledávána Pythonem během každé jednotlivé iterace, kdežto v f3() se vyhledá pouze jednou (a to jako argument pro map()). "Toto vyhledávání je docela náročné", řekl jsem kamarádovi, "pravidla dynamického prostoru v Pythonu říkají, že nejdříve se vyhledává (neúspěšně) v globálním slovníku současného modulu a teprve potom ve vestavěných funkcích (kde bude funkce opravdu nalezena). A navíc, kvůli způsobu hashování, je neúspěšné vyhledávání ve slovníku (v průměru) o trošku pomalejší než úspěšné."

Druhý důvod proč je f3() rychlejší než f1() je, že funkce chr(polozka) spuštěná přímo bytecode interpretem je obvykle pomalejší než spuštění pomocí map() - bytecode interpret musí vykonat tři instrukce pro každé volání (nahrát 'chr', nahrát 'polozka', zavolat), zatímco funkce map() dělá vše přímo v C.

To nás přivádí ke kompromisu, který nevyžaduje tolik paměti, ale dokáže značně urychlit vyhledávání funkce chr():

def f4(seznam):
    retezec = ""
    vyhledane_chr = chr
    for polozka in seznam:
        retezec = retezec + vyhledane_chr(polozka)
    return retezec

Jak jsem předpokládali, f4() byla pomalejší než f3(), ale pouze o 25%; tzn. byla stále o 40% rychlejší než f1(). Vyhledávání lokálních proměnných je mnohem rychlejší než vyhledávání globálních nebo vestavěných proměnných: "kompilátor" Pythonu optimalizuje většinu funkcí tak, aby pro lokální proměnné nebylo potřeba vyhledávat ve slovníku, ale aby stačila jednoduchá indexovaná pole. Relativní rychlost f4() porovnaná s f1() a f2() ukazuje, že k rychlosti f3() přispívají oba dva zmíněné důvody, ale první (méně vyhledávání) je o trošku důležitější. (Abychom dostali přesnější data, museli bychom upravit interpret.)

Zatím naše nejlepší verze f3() je jenom dvakrát rychlejší než přímočará verze f1(). Můžeme být lepší?

Obával jsem se, že kvadratické povaha algoritmu pro nás bude smrtící. Jako testovací data jsme zatím používali seznam 256 celých čísel, protože přesně k tomu kamarád tuto funkci potřeboval. Ale co se stane, když ji použijeme na seznam s dvěma tisíci znaky? V každé iteraci bychom zvětšovali stále delší a delší řetězce o jediný znak. Je jasně vidět, že vytvoření seznamu o délce N tímto způsobem vyžaduje, kromě nutné režije, celkově zkopírování 1 + 2 + 3 + ... + (N-1) znaků, neboli N*(N-1)/2 nebo 0.5*N**2 - 0.5*N. Dále se provede N paměťových alokací řetězce, ale pro dostatečně vysoké N, výraz obsahující N**2 naprosto převládne. A opravdu, pro osmkrát delší seznam (2048 položek) trvá funkce mnohem déle než jen osmkrát, je téměř šestnáctkrát delší. Ani jsem se neodvážil zkusit seznam 64 krát delší.

Existuje obecná technika, jak se takovémuto kvadratickému algoritmu vyhnout. Následující kód jsem napsal pro přesně 256 položek dlouhý seznam:

def f5(seznam):
    retezec = ""
    for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
        r = ""
        for znak in map(chr, seznam[i:i+16]):
            r = r + znak
        retezec = retezec + r
    return string

Bohužel, pro seznam 256 položek běžela tato verze o něco pomaleji (skoro o 20%) než f3(). Jelikož vytvoření obecné verze by funkci ještě více zpomalilo, nezatěžovali jsme se dále s jejím vývojem (kromě porovnání s variantou bez použití map(), která byla samozřejmě zase pomalejší).

Nakonec jsem zkusil úplně odlišný přístup: použít jenom vestavěné smyčky. Poznamenejme, že celá operace může být popsána takto: použij chr() na každou položku seznamu a pak spoj výsledné znaky. Vestavěné smyčky jsme už používali v první části: map(). Naštěstí modul string obsahuje i funkce na spojování řetězců implementované v C. Konkrétně string.joinfields(seznam_retezcu,oddelovac) spojí seznam řetězců vložením oddělovače, podle našeho výběru, mezi každé dvě sousední položky. Teď už nás nic nemůže zastavit od spojení seznamu znaků (řetězců o délce jedna), použitím prázdného řetězce jako oddělovače. Pohleďme:

import string
    def f6(list):
        return string.joinfields(map(chr, list), "")

Tato funkce běží čtyřikrát až pětkrát rychleji než dosavadní nejrychlejší soutěžící f3(). A dokonce funkce ani nemá kvadratické chování, jako předchozí verze.

A vítězem se stává ...

Druhý den jsem si vzpomněl na trochu netypickou část Pythonu: modul array. Modul má operace pro vytvoření pole jedno-bytových celých čísel ze seznamu Pythonovských čísel a každé pole umí zapsat do souboru nebo konvertovat na řetězec jako binární datovou strukturu. Takhle vypadá naše funkce vytvořená použitím zmíněných operací:

import array
    def f7(list):
        return array.array('B', list).tostring()

Tohle je zhruba třikrát rychlejší než f6() a 12 až 15 krát rychlejší než f3()! Používá se také méně přechodné paměti - pouze alokuje 2 objekty o N bytech (plus pevné režije), zatímco f6() začíná alokováním seznamu o N položkách, které obvykle zabírají 4N bytů (8N bytů na 64-bit počítačích) - za předpokladu, že objekty reprezentující znaky jsou sdílené s obdobnými objekty kdekoliv jinde v programu (podobně jako malá celá čísla, jsou i řetězce délky jedna většinou Pythonem kešovány).

"Zastav", řekl kamarád, "než se dostaneš do záporných časů - tohle je pro můj program již dostatečně rychlé". Souhlasil jsem, ačkoliv jsem chtěl vyzkoušet ještě jeden způsob: napsat celou funkci v C. Taková funkce by měla minimum paměťových nároků (alokovala by řetězec délky N hned na začátku) a ušetřila by několik instrukcí v C kódu, které jsou v modulu array kvůli potřebné obecnosti (podporuje celá čísla o 1,2 a 4 bytech). Funkce by se však nemohla vyhnout převodu Pythonovských celých čísel ze seznamu na celočíselné typy v C, což je časově docela náročná operace v Python-C API, a tudíž očekávané zlepšení výkonu bylo asi nepodstatné. Když jsem vzal v úvahu úsilí na napsání a otestování tohoto rozšíření (v porovnání s předešlými jednořádkovými funkcemi) a stejně tak závislost na nestandardním Pythonovském funkci, rozhodl jsem se tím dále nezabývat.

Závěr

Pokud cítíte potřebu po zvyšování rychlosti, používejte vestavěné funkce - nikdy nemůžete být lepší než smyčky napsané v C. Pro nalezení vhodných vestavěných funkcí používejte manuál k základním knihovnám a pokud takovou funkci nenajdete, držte se následujících základních pravidel pro optimalizaci smyček:

  • Pravidlo jedna: optimalizujte jen pokud máte nějak prokázané, že je funkce opravdu pomalá. Optimalizujte vždy jen nejhlouběji vnořenou smyčku. (Toto pravidlo neplatí jen pro Python, ale opakování základů nikomu neublíží, zvlášť když může ušetřit množství zbytečné práce.)
  • Co je malé, to je hezké. Kvůli množství instrukcí v pythonovském bytecodu a vyhledání proměnných, se málokdy vyplatí přidávat extra testy na ušetření trochy práce.
  • Používejte vnitřní operace. Smyčka ve funkci map() je mnohem rychlejší než explicitní smyčka for. Konstrukce while s počítadlem smyček je dokonce ještě pomalejší.
  • Uvnitř smyček se vyhněte volání funkcí napsaných v Pythonu (včetně volání lambda funkcí). Jednořádkové smyčky nám mohou šetřit nemalé množství času.
  • Lokální proměnné jsou rychlejší než globální. Pokud používáte globální konstanty ve smyčkách, zkopírujte je do lokálních těsně předtím, než smyčka začne. Jména funkcí v Pythonu (globální nebo vestavěné) jsou také globální konstanty!
  • Zkuste pomocí map(), filter() nebo reduce() nahradit explicitní smyčky for, ale jen v případě, že můžete použít vestavěné funkce: map s vestavěnou funkcí je rychlejší než smyčka for, ale smyčka for s in-line kódem překoná map s lambda funkcí!
  • Zkontrolujte zda váš algoritmus nemá kvadratické chování. Komplexní algoritmus pro odstranění kvadraticity se vyplatí jen pro velká N - pro malá N bývá komplexní algoritmus zbytečný. V našem případě bylo 256 dostatečně malé, takže jednodušší verze byla pořád o trošku rychlejší. Vaše hraniční hodnota N se může lišit a je rozhodně vhodné ji řádně otestovat.
  • A v neposlední řadě: shormážděte si potřebná data. Excelentní Pythonovský profile modul může rychle ukázat na slabá místa vašeho kódu. Když přemýšlíte nad jinou verzí algoritmu, otestujte ji ve smyčce s použitím funkce time.clock().

Mimochodem, tady je funkce, kterou na testování používám já. Testovanou funkci f() volám n*10 krát s argumentem a a následně vypíšu jméno funkce a použitý čas zaokrouhlený na milisekundy. Desetinásobné volání minimalizuje zkreslení potřebného času kvůli režiji smyčky. Samozřejmě můžete jít i dále a udělat stonásobné volání ... I výraz range(n) je vykonán před začátkem měření času, aby náš časový výsledek byl co nejvěrohodnější. Pokud vám ještě pořád přijde, že režije smyčky bude výsledek příliš zkreslovat, můžete vše kalibrovat pomocí prázdné funkce.

import time
def timing(f, n, a):
    print f.__name__,
    r = range(n)
    t1 = time.clock()
    for i in r:
        f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
    t2 = time.clock()
    print round(t2-t1, 3)

Doslov

Po pár dnech se kamarád vrátil s další otázkou: "Jak udělat obrácenou operaci?. Jak z řetězce vytvořit seznam ASCII hodnot?". "Ale ne, jsem zase na začátku", proběhlo mi hlavou ...

Tentokrát to však bylo docela bezbolestné. Máme dva kandidáty, jeden zcela očividný:

def g1(string):
    return map(ord, string)

a druhý, už ne tak zřejmý:

import array
def g2(string):
    return array.array('b', string).tolist()

Testování odhalilo, že funkce g2() je zhruba pětkrát rychlejší než g1(). Je tady však jedno ale: g2() vrací seznam celých čísel v rozsahu -128...127, kdežto g1() vrací celá čísla mezi 0..255. Pokud chceme pouze kladná čísla, pak g1() je rychlejší než jakákoliv transformace výstupu funkce g2(). (Pozn. po napsání této eseje byl v modulu array přidán parametr 'B', který uchovává bezznaménkové byty, takže teď už není žádný rozumný důvod k preferování funkce g1().)


Copyright Python Software Foundation

Přeloženo se svolením autora - Guida van Rossuma z http://www.python.org/doc/essays/list2str/

díky --stibi, Sat, 03 Oct 2009 17:44:00 +0200 reply

Moc díky za překlad. Velmi zajímavé .. pro mě takový další level, musím to znovu důkladněji prostudovat.




subject:
  ( 112 subscribers )