Die erste Version, die mir einfiel, war völlig unkompliziert

    def f1(list):
        string = ""
        for item in list:
            string = string + chr(item)
        return string

Das kann nicht der schnellste Weg sein, sagte mein Freund. Wie wäre es mit dieser?

    def f2(list):
        return reduce(lambda string, item: string + chr(item), list, "")

Diese Version führt die gleiche Menge an Zeichenkettenoperationen wie die erste durch, verzichtet aber auf den Overhead der for-Schleife zugunsten der schnelleren, impliziten Schleife der reduce()-Funktion.

Sicher, erwiderte ich, aber das geschieht auf Kosten eines Funktionsaufrufs (der Lambda-Funktion) pro Listenelement. Ich wette, sie ist langsamer, da der Overhead von Funktionsaufrufen in Python größer ist als der von for-Schleifen.

(OK, die Vergleiche hatte ich schon gemacht. f2() brauchte 60% mehr Zeit als f1(). Also, da habt ihr's :-)

Hmm, sagte mein Freund. Ich brauche das schneller. OK, sagte ich, wie wäre es mit dieser Version?

    def f3(list):
        string = ""
        for character in map(chr, list):
            string = string + character
        return string

Zu unserer beider Überraschung war f3() doppelt so schnell wie f1()! Dass uns das überraschte, hatte zwei Gründe: Erstens verbraucht sie mehr Speicher (das Ergebnis von map(chr, list) ist eine weitere Liste gleicher Länge); zweitens enthält sie zwei Schleifen statt einer (die implizite Schleife der map()-Funktion und die for-Schleife).

Natürlich ist Speicher gegen Zeit ein bekannter Kompromiss, daher hätte uns der erste Punkt nicht überraschen sollen. Aber wie kommt es, dass zwei Schleifen schneller sind als eine? Zwei Gründe.

Erstens wird in f1() die eingebaute Funktion chr() bei jeder Iteration neu gesucht, während sie in f3() nur einmal gesucht wird (als Argument für map()). Diese Suche ist relativ teuer, sagte ich meinem Freund, da Python aufgrund seiner dynamischen Gültigkeitsregeln sie zuerst (erfolglos) im globalen Wörterbuch des aktuellen Moduls sucht und dann im Wörterbuch der eingebauten Funktionen (wo sie gefunden wird). Schlimmer noch, erfolglose Wörterbuchsuchen sind (im Durchschnitt) etwas langsamer als erfolgreiche, aufgrund der Art und Weise, wie das Hashing mit Verkettung funktioniert.

Der zweite Grund, warum f3() schneller ist als f1(), ist, dass der Aufruf von chr(item), wie er vom Bytecode-Interpreter ausgeführt wird, wahrscheinlich etwas langsamer ist, als wenn er von der map()-Funktion ausgeführt wird – der Bytecode-Interpreter muss drei Bytecode-Instruktionen für jeden Aufruf ausführen (lade 'chr', lade 'item', rufe auf), während die map()-Funktion das alles in C erledigt.

Das führte uns zu einem Kompromiss, der keinen zusätzlichen Speicher verschwendet, aber die Suche nach der chr()-Funktion beschleunigt.

    def f4(list):
        string = ""
        lchr = chr
        for item in list:
            string = string + lchr(item)
        return string

Wie erwartet war f4() langsamer als f3(), aber nur um 25%; sie war immer noch etwa 40% schneller als f1(). Das liegt daran, dass Lookups lokaler Variablen *viel* schneller sind als Lookups globaler oder eingebauter Variablen: Der Python-"Compiler" optimiert die meisten Funktionskörper so, dass für lokale Variablen keine Wörterbuchsuche erforderlich ist, sondern ein einfacher Array-Indexzugriff ausreicht. Die relative Geschwindigkeit von f4() im Vergleich zu f1() und f3() legt nahe, dass beide Gründe, warum f3() schneller ist, zutreffen, aber dass der erste Grund (weniger Lookups) etwas wichtiger ist. (Um genauere Daten zu erhalten, müssten wir den Interpreter instrumentieren.)

Dennoch war unsere beste Version, f3(), nur doppelt so schnell wie die geradlinigste Version, f1(). Können wir es besser machen?

Ich befürchtete, dass das quadratische Verhalten des Algorithmus uns zum Verhängnis wurde. Bisher hatten wir eine Liste von 256 Ganzzahlen als Testdaten verwendet, da mein Freund die Funktion dafür benötigte. Aber was, wenn sie auf eine Liste von zweitausend Zeichen angewendet würde? Wir würden immer längere Zeichenketten aneinanderreihen, ein Zeichen nach dem anderen. Es ist leicht zu erkennen, dass, abgesehen vom Overhead, um eine Liste der Länge N auf diese Weise zu erstellen, insgesamt 1 + 2 + 3 + ... + (N-1) Zeichen kopiert werden müssen, oder N*(N-1)/2, oder 0.5*N**2 - 0.5*N. Zusätzlich gibt es N Zeichenketten-Allokationsoperationen, aber für ausreichend große N wird der Term mit N**2 die Oberhand gewinnen. Tatsächlich dauert es für eine Liste, die 8-mal so lang ist (2048 Elemente), bei diesen Funktionen viel länger als 8-mal so lange; tatsächlich fast 16-mal so lange. Ich wagte es nicht, eine 64-mal längere Liste auszuprobieren.

Es gibt eine allgemeine Technik, um quadratisches Verhalten in solchen Algorithmen zu vermeiden. Ich habe sie wie folgt für Zeichenketten von genau 256 Elementen codiert.

    def f5(list):
        string = ""
        for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
            s = ""
            for character in map(chr, list[i:i+16]):
                s = s + character
            string = string + s
        return string

Leider war diese Version für eine Liste von 256 Elementen etwas langsamer (wenn auch innerhalb von 20%) als f3(). Da das Schreiben einer allgemeinen Version sie nur noch langsamer machen würde, haben wir diesen Weg nicht weiter verfolgt (außer dass wir sie auch mit einer Variante verglichen haben, die map() nicht verwendete, die natürlich wieder langsamer war).

Schließlich probierte ich einen radikal anderen Ansatz: Benutze *nur* implizite Schleifen. Beachten Sie, dass die gesamte Operation wie folgt beschrieben werden kann: wende chr() auf jedes Listenelement an; dann verketten Sie die resultierenden Zeichen. Wir benutzten bereits eine implizite Schleife für den ersten Teil: map(). Glücklicherweise gibt es im String-Modul einige Zeichenketten-Verkettungsfunktionen, die in C implementiert sind. Insbesondere verkettet string.joinfields(list_of_strings, delimiter) eine Liste von Zeichenketten und fügt zwischen jeder Zeichenkette ein beliebiges Trennzeichen ein. Nichts hindert uns daran, eine Liste von Zeichen (die in Python nur Zeichenketten der Länge eins sind) mit dem leeren String als Trennzeichen zu verketten. Und siehe da:

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

Diese Funktion war vier- bis fünfmal schneller als unser bisher schnellster Mitbewerber, f3(). Außerdem hat sie nicht das quadratische Verhalten der anderen Versionen.

Und der Gewinner ist...

Am nächsten Tag erinnerte ich mich an eine obskure Ecke von Python: das array-Modul. Dieses hat zufällig eine Operation, um aus einer Liste von Python-Ganzzahlen ein Array von 1-Byte breiten Ganzzahlen zu erstellen, und jedes Array kann als Binärdatenstruktur in eine Datei geschrieben oder in eine Zeichenkette umgewandelt werden. Hier ist unsere Funktion, die mit diesen Operationen implementiert wurde:

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

Das ist etwa dreimal so schnell wie f6(), oder 12- bis 15-mal so schnell wie f3! Es verbraucht auch weniger Zwischenspeicher – es werden nur 2 Objekte von N Bytes (plus fester Overhead) alloziert, während f6() zunächst eine Liste von N Elementen alloziert, was normalerweise 4N Bytes kostet (8N Bytes auf einem 64-Bit-System) – vorausgesetzt, die Zeichenobjekte werden mit ähnlichen Objekten an anderer Stelle im Programm geteilt (wie bei kleinen Ganzzahlen, Python zwischenspeichert Zeichen der Länge eins in den meisten Fällen).

Halt, sagte mein Freund, bevor du in negative Zeiten gerätst – das ist schnell genug für mein Programm. Ich stimmte zu, obwohl ich noch einen Ansatz ausprobieren wollte: die gesamte Funktion in C schreiben. Das hätte minimale Speicheranforderungen (es würde sofort eine Zeichenkette der Länge N alloziereeren) und würde ein paar Instruktionen im C-Code sparen, von denen ich wusste, dass sie im array-Modul aufgrund seiner Generizität vorhanden waren (es unterstützt Ganzzahlbreiten von 1, 2 und 4 Bytes). Es könnte jedoch nicht vermeiden, die Elemente nacheinander aus der Liste zu extrahieren und die C-Ganzzahl daraus zu extrahieren, beides sind ziemlich teure Operationen in der Python-C-API, daher erwartete ich nur eine mäßige Geschwindigkeitssteigerung im Vergleich zu f7(). Angesichts des Aufwands für das Schreiben und Testen einer Erweiterung (im Vergleich zum schnellen Erstellen dieser Python-One-Liner) sowie der Abhängigkeit von einer nicht standardmäßigen Python-Erweiterung entschied ich mich, diese Option nicht weiter zu verfolgen...

Schlussfolgerung

Wenn Sie nach Geschwindigkeit streben, greifen Sie zu eingebauten Funktionen – Sie können eine in C geschriebene Schleife nicht übertreffen. Schauen Sie im Bibliothekenhandbuch nach einer eingebauten Funktion, die das tut, was Sie wollen. Wenn es keine gibt, hier sind einige Richtlinien für die Schleifenoptimierung.

• Regel Nummer eins: optimieren Sie nur, wenn es einen nachgewiesenen Geschwindigkeitsengpass gibt. Optimieren Sie nur die innerste Schleife. (Diese Regel ist unabhängig von Python, aber es schadet nicht, sie zu wiederholen, da sie viel Arbeit sparen kann. :-)
• Klein ist schön. Angesichts von Pythons erheblichen Gebühren für Bytecode-Instruktionen und Variablensuchen lohnt es sich selten, zusätzliche Tests hinzuzufügen, um ein wenig Arbeit zu sparen.
• Verwenden Sie intrinsische Operationen. Eine implizite Schleife in map() ist schneller als eine explizite for-Schleife; eine while-Schleife mit einem expliziten Schleifenzähler ist noch langsamer.
• Vermeiden Sie das Aufrufen von in Python geschriebenen Funktionen in Ihrer inneren Schleife. Dazu gehören Lambdas. Das Inlining der inneren Schleife kann viel Zeit sparen.
• Lokale Variablen sind schneller als globale; wenn Sie eine globale Konstante in einer Schleife verwenden, kopieren Sie sie vor der Schleife in eine lokale Variable. Und in Python sind Funktionsnamen (global oder eingebaut) ebenfalls globale Konstanten!
• Versuchen Sie, map(), filter() oder reduce() zu verwenden, um eine explizite for-Schleife zu ersetzen, aber nur, wenn Sie eine eingebaute Funktion verwenden können: map mit einer eingebauten Funktion schlägt eine for-Schleife, aber eine for-Schleife mit Inline-Code schlägt map mit einer Lambda-Funktion!
• Überprüfen Sie Ihre Algorithmen auf quadratisches Verhalten. Beachten Sie jedoch, dass sich ein komplexerer Algorithmus nur für große N auszahlt – für kleine N zahlt sich die Komplexität nicht aus. In unserem Fall war 256 klein genug, dass die einfachere Version immer noch ein bisschen schneller war. Ihre Ergebnisse können variieren – das ist es wert, untersucht zu werden.
• Und zu guter Letzt: Sammeln Sie Daten. Pythons ausgezeichnetes Profilmodul kann schnell den Engpass in Ihrem Code aufzeigen. Wenn Sie verschiedene Versionen eines Algorithmus in Betracht ziehen, testen Sie ihn in einer engen Schleife mit der time.clock()-Funktion.

Übrigens, hier ist die Timing-Funktion, die ich verwendet habe. Sie ruft eine Funktion f n*10 Mal mit dem Argument a auf und gibt den Funktionsnamen gefolgt von der benötigten Zeit, gerundet auf Millisekunden, aus. Die 10 wiederholten Aufrufe minimieren den Schleifen-Overhead der Timing-Funktion selbst. Man könnte sogar noch weiter gehen und 100 Aufrufe machen... Beachten Sie auch, dass der Ausdruck range(n) außerhalb der Timing-Klammern berechnet wird – ein weiterer Trick zur Minimierung des Overheads der Timing-Funktion. Wenn Sie sich Sorgen über diesen Overhead machen, können Sie ihn kalibrieren, indem Sie die Timing-Funktion mit einer Nichtstun-Funktion aufrufen.

    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)

Epilog

Ein paar Tage später kam mein Freund mit der Frage zurück: Wie macht man die Umkehrung? D.h. eine Liste von Ganzzahl-ASCII-Werten aus einer Zeichenkette erstellen. Oh nein, hier geht es wieder los, blitzte es mir durch den Kopf...

Aber dieses Mal war es relativ schmerzlos. Es gibt zwei Kandidaten, das Offensichtliche

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

und das etwas weniger Offensichtliche

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

Das Timing dieser zeigt, dass g2() etwa fünfmal schneller ist als g1(). Es gibt jedoch einen Haken: g2() gibt Ganzzahlen im Bereich -128..127 zurück, während g1() Ganzzahlen im Bereich 0..255 zurückgibt. Wenn Sie die positiven Ganzzahlen benötigen, ist g1() schneller als jede Nachbearbeitung, die Sie am Ergebnis von g2() vornehmen könnten. (Hinweis: Seitdem dieser Aufsatz geschrieben wurde, wurde dem array-Modul der 'B'-Typcode hinzugefügt, der vorzeichenlose Bytes speichert, daher gibt es keinen Grund mehr, g1() zu bevorzugen.)

Beispielcode

• Timing von f1() bis f7()
• Timing von g1() und g2()