changed:
-
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/



From stibi Sat Oct 3 17:44:00 +0200 2009
From: stibi
Date: Sat, 03 Oct 2009 17:44:00 +0200
Subject: díky
Message-ID: <20091003174400+0200@www.py.cz>

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

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, "")

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

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

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

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

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

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)

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

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