[Python-de] Sortieren

Stefan Schwarzer sschwarzer at sschwarzer.net
Sam Jun 18 10:42:07 CEST 2005


Hallo Harald,

On 2005-06-17 09:47, Harald Armin Massa wrote:
> eine Vergleichsfunkion nur dann verwenden, wenn es ABSOLUT notwendig ist.
>
> Es ist nie absolut notwendig.
>
> Vergleichsfunktion macht das ganze viel viel langsamer,
>
> [Erklärung des DSU-Idioms]

das sehe ich nicht so kategorisch. Wenn die Geschwindigkeit des
Sortierens ohne DSU ausreicht, ist das ok. Wenn die Geschwindigkeit
ausreicht, gebe ich dem besser lesbaren Code den Vorzug, und ich finde

L.sort(compare)

besser lesbar als

decorated_L = [(decorate(item), item) for item in L]
decorated_L.sort()
L = [item[1] for item in decorated_L]

(wobei decorate(item) natürlich kein Funktionsaufruf sein muss, sondern
hier nur für einen geeigneten Ausdruck steht). Die DSU-Variante wird sich
umso mehr lohnen, je länger die Liste und je zeitaufwendiger die Vergleichs-
bzw. Dekorier-Funktion ist.

Zum Thema verfrühte Optimierung siehe auch
http://www.martinfowler.com/ieeeSoftware/yetOptimization.pdf

Netterweise gibt es seit Python 2.4 das DSU-Idiom in einer eingebauten
Variante, dem key-Parameter:

L.sort(key=decorate)

Aber, wie gesagt, erst seit Python 2.4. Das ist zu beachten bei Code, der
unverändert mit früheren Python-Versionen laufen soll.

Wer mag, kann also schreiben (ungetestet, bitte debuggen ;-) ):

def decorate_sort(a_list, decorate):
    """
    Sort `a_list` in-place with the DSU idiom (also known as
    Schwartzian transformation). See discussion of
    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234
    """
    # First check if `sort` supports the `key` parameter. If we used
    # the code from the else-branch (s. below) here, we would mask
    # `TypeError`s in the `decorate` callable.
    try:
        [].sort(key=lambda x: x)
    except TypeError:
        decorated_list = [(decorate(item), item) for item in a_list]
        decorated_list.sort()
        # modify `a_list` in-place
        a_list[:] = [item[1] for item in decorated_list]
    else:
        a_list.sort(key=decorate)

Viele Grüße
Stefan