Weitere Optimierung möglich?

[Slag]

Da ich bezüglich python noch nicht soviel Ahnung habe und dies mit eines meiner ersten Skripte ist, wüsste ich gerne eure Meinung dazu.
Das ganze ist aus Codestückchen aus der Doku, dem Forum und eigenen Gedankengängen zusammengesetzt:

Ziel des Skripts ist, eine Datenreihe aus einer Datei auszulesen und diese zur Basis 224 zu codieren.

Code: Alles auswählen

#! /usr/lib/python
#-*- coding:utf-8 -*-

import array

name1=dict()
name2=dict()
name3=dict()
name4=dict()
name5=dict()

liste_von_dicts=[name1, name2, name3, name4, name5]

def umwandler(zeile):

    zeile.strip('\n')
    datenliste=zeile.split('|')
    result=""
    for index, eintrag in enumerate(datenliste):
        if eintrag in liste_von_dicts[index]:
            result+=liste_von_dicts[index][eintrag]
        else:
# Die ersten beiden koennen Werte groesser als 224 haben, deshalb 2 Eintraege. Die ersten 32 Zeichen sind zudem Steuerungszeichen, deshalb ausgeschlossen.
            if index in range(2):
                liste_von_dicts[index][eintrag] = array.array('B', [len(liste_von_dicts[index])/224+32, len(liste_von_dicts[index])%224+32]).tostring()

            else:
                liste_von_dicts[index][eintrag] = array.array('B',[len(liste_von_dicts[index])+32]).tostring()

            result+=liste_von_dicts[index][eintrag]

with open("/tmp/datendatei","r") as daten:
    with open("/tmp/codedatei","w") as datei
        for line in daten:
            datei.write(umwandler(line))

Eine Zeile Daten sind also ungefähr so aus: Tim|Struppi|Was|Auch|immer
und wird dann zB zu !" (a.!
Falls Tippfehler enthalten sind gehen die auf meine Kappe und sind im Original nicht enthalten, da aus diversen Gründen direktes kopieren nicht möglich war. In einer späteren Version des Skripts wird sich natürlich auch der Inhalt der Dictionaries gemerkt, damit man die Daten auch wieder rekonstruieren kann, mir geht es aber erstmal nur um meine Implementierung für das Umwandeln.

[Hyperion]

Also das hier sieht ziemlich schlimm aus:

Code: Alles auswählen

name1=dict()
name2=dict()
name3=dict()
name4=dict()
name5=dict()

liste_von_dicts=[name1, name2, name3, name4, name5]

Das geht doch viel einfacher:

Code: Alles auswählen

In [1]: liste_von_dicts = [dict() for _ in range(5)]

In [2]: liste_von_dicts
Out[2]: [{}, {}, {}, {}, {}]

Falls Tippfehler enthalten sind gehen die auf meine Kappe und sind im Original nicht enthalten, da aus diversen Gründen direktes kopieren nicht möglich war.

Da muss die Frage einfach sein: Was sind denn die div. Gründe? Generell ist es bei längeren Snippets wenig sinnvoll diese hier zu posten, wenn die nicht lauffähig sind.

Generell sieht die Funktion ziemlich überladen aus. Neben den grausigen Namen (`liste_von_dicts` ) fällt auf, dass Du einen Ergebnisstring per "+" zusammenbaust. Sinnvoller ist es, eine Liste aufzubauen und diese dann per `"".join()` zusammen zu setzen.

Mir fehlt es an Doku und Grundverständnis für das, was Du überhaupt tun willst! Sicherlich könnte man das aus dem Code ablesen, aber dafür bin ich zu faul

[deets]

Noch ein paar mehr Anmerkungen: du solltest das base-224-encoding als Funktion trennen vom Prozessieren der Daten - dann kannst du das unabhaengig davon pruefen, ob es funktioniert. Dann greifst du auch nicht immer mit diesem Endlos-Ausdruck auf liste_von_dicts[index] zu.

if index in range(2)

ist auch nicht so dolle, wenn es wie hier um ein wirklich simple index < 2 geht, dann schreib das doch so. Alternativ mach halt eine globale Variable, die sowas wie "EXCLUDED_INDICES" heisst, und darin sind dann alle exkludierten indizes - dann ist das wenigstens als klare Deklaration verstehbar.

Und natuerlich ist die nahezu 100%ige doppelung von dem ganzen encodieren umstaendlich, aber dazu wie gesagt die Funktion.

[Slag]

@ Hyperion:
Das Skript liegt auf einem anderen Rechner, der streng vom Rest der Welt getrennt ist, daher war abtippen die einzige Möglichkeit. Auf diesem Rechner von dem ich jetzt schreibe habe ich zudem kein Python. Das Skript ist übrigens lauffähig, ich habe es nur dazu geschrieben, falls ich mich doch irgendwo vertippt habe, damit man sich nicht darüber wundert.

Der Name 'liste_von_dicts' hat mir als sprechender Name eigentlich ganz gut gefallen, sagt halt genau aus was es ist.
Deine Variante mit der Liste wäre auch eine Idee, mache ich evtl. ganz am Ende, momentan haben die dictionaries sprechende Namen, damit ich nicht durcheinander komme und die Reihenfolge einhalte.

Was das Programm machen soll, habe ich nochmal darunter geschrieben, eine Datei mit Zeilen der Form:
Tim|Struppi|Was|Auch|immer
in eine Datei mit Zeilen der Form:
!" (a.!
umwandeln.
Das ganze also stark verkürzen, indem es statt den ganzen Wörtern nur 1-2 Zeichen pro Wort speichert, ich kenne also zu Beginn nicht alle möglichen Wörter, nur Obergrenzen für die Anzahl der verschiedenen Wörter (genauer gesagt hat Tim sehr viele 'Namensvetter' und braucht mehr als ein Zeichen).

Das mit dem .join() werde ich mal ausprobieren, mal sehen ob es dann schneller oder langsamer als die bisherige Variante ist.

@Deeds:
Das mit dem <2 ist wohl ein typischer Fall von Betriebsblindheit, danke dafür.
Das Encoding übernimmt ja eh das array-Modul und ich will das ganze ja auf Geschwindigkeit optimieren, da würde ich mir doch selber ein Bein stellen, wenn ich das erst auf eine lokale Variable zwischenspeichere, diese an eine weitere Funktion übergebe, die nichts anderes tut als die array.tostring() Funktion aufzurufen. (ausser ich habe dich jetzt komplett missverstanden)
Ich werde aber mal prüfen ob meine Vermutung stimmt, dass zweimal len(dictvariable) aufzurufen schneller geht, als nur einmal und als lokale Variable speichern.

[deets]

@slag

Ganz ehrlich: ich bezweifele sehr, sehr stark, dass das, was du da tust, von einer solchen Optimierung geschwindigkeitsmaessig profitieren wuerde. Ein Funktionsaufruf bringt dich nicht um. Wenn du da wirklich am Ende Performance-Probleme bekommst, dann profile das, und schau, wo das wirkliche Problem liegt. Aber Dinge, die ein paar micro-Sekunden besser laufen koennen wegen lokalem Variablen-Lookup sind eher selten...

[nomnom]

Das Skript ist übrigens lauffähig

Nein, das stimmt nicht

[BlackJack]

@Slag: Vergiss erst mal die Geschwindigkeitsoptimierung jenseits von Komplexitätsklassen. Schreib das so dass man es leicht lesen und verstehen kann. Erst wenn es korrekt läuft und dann *nachweislich*, *gemessen* zu langsam ist, solltest Du Dir um solche Mikrooptimierungen wie „inlining“ von Funktionen gedanken machen.

Weder `name1` bis `name5` noch `liste_von_dicts` sind sprechende Bezeichner. Ein guter Bezeichner sagt nicht was das für Typen sind, sondern was für eine Bedeutung für das Programm die Objekte haben, die sich hinter dem Namen verbergen. Wenn man Typen in den Namen aufnimmt, kann man die Typen auch nicht mehr so einfach ändern ohne dass man den Namen überall ändern muss.

Funktionsnamen sollten zudem Tätigkeiten beschreiben, also zum Beispiel `umwandeln()` statt `umwandler()`. Letzteres wäre eher ein Name für ein Objekt vom Typ `Umwandler`.

Die Verwendung von `array` ist IMHO zu umständlich. Das kann man auch mit `chr()` lösen.

Ich würde das wahrscheinlich mit einem eigenen Datentypen lösen, der Eingaben kodiert, statt dafür ein Wörterbuch direkt zu verwenden.

[Slag]

Danke erstmal für die ganzen Vorschläge

Ich habe mittlerweile ein paar Tests gemacht:
Die Methode mit .join() statt str1+str2 habe ich verworfen, es machte das Skript um ~25% langsamer.
Auf die Idee mit der Umwandlung per array-Modul bin ich übrigens hier drüber gekommen: http://www.python.org/doc/essays/list2str.html daher werde ich auch dabei bleiben.
Umbenannt habe ich aber mal die Funktion, die Liste meiner dicts und ich habe eine Variable mehr definiert, in der ich die Länge des Dictionaries speichere, damit sollte der Code besser zu lesen sein.
Aktuell schafft der Code somit um die 200k Zeilen pro Sekunde, wobei der Rechner nicht der schnellste ist.
Hier mal der aktuelle Code des Skripts für den Speedtest (das schreiben in eine Datei ist entfernt, die umwandeln-Funktion wird 10mal pro Zeile aufgerufen und die Zeit zur Ausführung des Skripts gemessen), die Dicts haben im Original aussagekräftigere Namen als name1-5:

Code: Alles auswählen

#! /usr/lib/python
#-*- coding:utf-8 -*-

import array
import time

name1=dict()
name2=dict()
name3=dict()
name4=dict()
name5=dict()

dict_sammler=[name1, name2, name3, name4, name5]

def umwandeln(zeile):

    zeile.strip('\n')
    datenliste=zeile.split('|')
    result=""
    for index, eintrag in enumerate(datenliste):
        if eintrag in dict_sammler[index]:
            result+=dict_sammler[index][eintrag]
        else:
# Von den ersten beiden gibt es mehr als 224 verschiedene, deshalb mit 2 Char-Zeichen codiert. Die ersten 32 char-Zeichen sind zudem Steuerungszeichen, deshalb ausgeschlossen, weil problematisch.
            neueintrag=len(dict_sammler[index])
            if index < 2:
                dict_sammler[index][eintrag] = array.array('B', [neueintrag/224+32, neueintrag%224+32]).tostring()

            else:
                dict_sammler[index][eintrag] = array.array('B',[neueintrag+32]).tostring()

            result+=dict_sammler[index][eintrag]

t1= time.clock()
with open("/tmp/datendatei","r") as daten:
    for line in daten:
        umwandeln(line); umwandeln(line); umwandeln(line); umwandeln(line); umwandeln(line)
        umwandeln(line); umwandeln(line); umwandeln(line); umwandeln(line); umwandeln(line)

t2=time.clock()
print t2-t1

Namensvorschläge oder andere Verbesserungen sind gerne gesehen, mir fiel leider bisher noch nichts besseres als dict_sammler ein

[/me]

Code: Alles auswählen

    [...]
    zeile.strip('\n')
    [...]

Du versuchst um jede Microsekunde zu kämpfen und führst dann trotzdem Aufrufe durch, die keine Auswirkungen auf den Programmablauf haben?

Die Methode strip() gibt einen geänderten String zurück, sie ändert nicht das bestehende Objekt.

[Slag]

Da sieht man mal, wie gut es ist hier gefragt zu haben
Die Zeile zu entfernen hat zwar 10% gebracht, nur leider enthält der letzte Eintrag dann jeweils \n.
Hätte ja darauf gehofft, dass "for line in datei" das für mich schon entfernt, aber dem war nicht so (ist bei genauerem nachdenken natürlich auch sinnvoll, dass es nicht entfernt wird).
Habe den Code daher jetzt auf

Code: Alles auswählen

datenliste=zeile.strip('\n').split('|')

verbessert.

[Hyperion]

Also als erstes fällt mir auf, dass Du meine Ratschläge zur Generierung Deines Dicts komplett ignoriert hast.

Zudem hat Dir BlackJack ja generell empfohlen, das ganze erst einmal leserlich zu gestalten. Dein Code ist ziemlich unübersichtlich und unpythonisch.

Als letztes misst Du die Zeit falsch. Du solltest Dir mal das `timeit`-Modul angucken!

[Slag]

Auf deinen Ratschlag zur Generierung habe ich sogar mehrfach reagiert:

Deine Variante mit der Liste wäre auch eine Idee, mache ich evtl. ganz am Ende, momentan haben die dictionaries sprechende Namen, damit ich nicht durcheinander komme und die Reihenfolge einhalte.

die Dicts haben im Original aussagekräftigere Namen als name1-5

Das wäre daher eine kontraproduktive Änderung, zumindest im momentanen Stadium. Ich habe es aber im Hinterkopf, wenn ich also später feststelle, dass ich die Dictionaries nicht per Name brauche, so werde ich das abändern

Die Anregungen von BlackJack habe ich auch versucht umzusetzen, er hatte die Namen und das verwenden vom array-Modul zur Aufgabenlösung bemängelt. Ersteres habe ich geändert, letzteres begründet.
Zur größerer Übersichtlichkeit wäre vielleicht eine weitere Verbesserung der Auswahlstruktur möglich, aber da hatte ich bisher noch keinen cleveren Gedanken: Wenn das Wort schonmal vorkam kann er es sofort codieren, ist es neu muss er den Code bestimmen, wobei es 2 Möglichkeiten gibt: 2-char und 1-char-Codierung. Welche gewählt wird, liegt am verwendeten dictionary...

Mit dem timeit-Modul habe ich auch mal rumgespielt, aber bisher scheitert er am Funktionsaufruf, selbst wenn ich '\n' am Zeilenende weglasse, da er wohl im timeit-Modul encoden will und deshalb die globalen Variablen die ich in der Funktion benutze nicht kennt. Vielleicht fällt mir dafür später noch eine Lösung ein.

Hier noch einmal der Code, ausführlicher kommentiert, die if-Anweisung weiter entschlackt, den Tippfehler das nichts zurück gegeben wurde verbessert (spielt für dieses Skript aber natürlich keine Rolle)

Code: Alles auswählen

#! /usr/lib/python
#-*- coding:utf-8 -*-

import array
import time

name1=dict()
name2=dict()
name3=dict()
name4=dict()
name5=dict()

dict_sammler=[name1, name2, name3, name4, name5]

def umwandeln(zeile):
# Erhält eine Zeile der Form a|b\n und wandelt diese per zur Laufzeit bestimmte Codierung um.

# Entfernt das \n am Ende der Zeile und teilt den String in eine Liste von strings, das trennzeichen ist '|'
  
    datenliste=zeile.strip('\n').split('|')
    result=""
# Prüft für jeden String der oben erzeugten Liste: ist er an dieser Position schon einmal aufgetreten, falls nicht, wird er neu codiert.
# Für jeden String wird dann sein Code in den Ergebnisstring geschrieben.
    for index, eintrag in enumerate(datenliste):
        if eintrag not in dict_sammler[index]:
# Von den ersten beiden gibt es mehr als 224 verschiedene, deshalb mit 2 Char-Zeichen codiert. Die ersten 32 char-Zeichen sind zudem Steuerungszeichen, deshalb ausgeschlossen, weil problematisch.
            neueintrag=len(dict_sammler[index])
            if index < 2:
                dict_sammler[index][eintrag] = array.array('B', [neueintrag/224+32, neueintrag%224+32]).tostring()

            else:
                dict_sammler[index][eintrag] = array.array('B',[neueintrag+32]).tostring()

        result+=dict_sammler[index][eintrag]
    
    return result

# hier beginnt der eigentliche Handlungsblock: Eine Datei wird zeilenweise eingelesen und die Zeilen einzeln codiert.
t1= time.clock()
with open("/tmp/datendatei","r") as daten:
    for line in daten:
        umwandeln(line); umwandeln(line); umwandeln(line); umwandeln(line); umwandeln(line)
        umwandeln(line); umwandeln(line); umwandeln(line); umwandeln(line); umwandeln(line)

t2=time.clock()
print t2-t1

[jerch]

Ich muss gestehen, dass ich nicht verstehe, was Du da mit den dictionaries und Arrays anstellst und wo Du die eigentliche Umrechnung der 256 Bits auf 224 vornimmst. Wahrscheinlich liegt das daran, dass ich nicht weiss, wie base224 intern funktioniert, eine auf die Schnelle erstellte eigene Lösung kommt viel mathematischer daher:

Code: Alles auswählen

def _256_to_224(block):
    as_int = 0
    for i,v in enumerate(block):
        as_int += ord(v)*256**i
    as_int += 1 << (8*(i+1))
    result = ''
    while as_int/224:
        result += chr((as_int % 224) + 32)
        as_int /= 224
    return result + chr((as_int % 224) + 32)

def encode224(s):
    result = ''
    for i in xrange(len(s)/7+1):
        byteblock = s[7*i:7*(i+1)]
        if byteblock:
            result += _256_to_224(byteblock)
    return result

def _224_to_256(block):
    as_int = 0
    for i,v in enumerate(block):
        as_int += (ord(v)-32)*224**i
    result = ''
    while as_int/256:
        result += chr(as_int % 256)
        as_int /= 256
    return result

def decode224(s):
    result = ''
    for i in xrange(len(s)/8+1):
        byteblock = s[8*i:8*(i+1)]
        if byteblock:
            result += _224_to_256(byteblock)
    return result

if __name__ == '__main__':
    s = 'Tim|Struppi|Was|Auch|immer'
    s224 = '|'.join(encode224(i) for i in s.split('|'))
    s256 = '|'.join(decode224(i) for i in s224.split('|'))
    print s224.decode('cp850'), s256
    assert(s==s256)

Ausser der Aussparung der Bytewerte \x00-\x31 hat das sicher nichts mit base224 gemein. (Konnte keine Spec finden zu base224)

[Hyperion]

Auf deinen Ratschlag zur Generierung habe ich sogar mehrfach reagiert:

Deine Variante mit der Liste wäre auch eine Idee, mache ich evtl. ganz am Ende, momentan haben die dictionaries sprechende Namen, damit ich nicht durcheinander komme und die Reihenfolge einhalte.

die Dicts haben im Original aussagekräftigere Namen als name1-5

Das wäre daher eine kontraproduktive Änderung, zumindest im momentanen Stadium. Ich habe es aber im Hinterkopf, wenn ich also später feststelle, dass ich die Dictionaries nicht per Name brauche, so werde ich das abändern

Das hatte ich überlesen. Aber wenn dem so ist, dann wäre ein Dictionary von Dictionaries wohl sinnvoller

Die Anregungen von BlackJack habe ich auch versucht umzusetzen, er hatte die Namen und das verwenden vom array-Modul zur Aufgabenlösung bemängelt. Ersteres habe ich geändert, letzteres begründet.

Also für letzteres habe ich mal ein Testscript geschrieben:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf-8

from array import array
from random import randint


def generate_numbers(limit=100000):
    for _ in xrange(limit):
        yield randint(33, 255)


def encode_with_chr(iterable):
    return "".join(chr(value) for value in iterable)


def encode_with_array(iterable):
    return "".join(array("B", (value,)).tostring() for value in iterable)

    
if __name__ == "__main__":
    from timeit import Timer
    for func in [encode_with_chr, encode_with_array]:
        print '{0}:'.format(func.__name__),
        t = Timer("{}(generate_numbers())".format(func.__name__),
                  "from __main__ import {}, generate_numbers".format(func.__name__))
        print t.timeit(10)

Meine Messung:

Code: Alles auswählen

encode_with_chr: 3.21732401848
encode_with_array: 3.86245417595

Die Tendenz sagt hier klar, dass die Variante mit `chr` schneller ist. (Und das, obwohl ich ein Tupel statt einer Liste im array verwendet habe!)

Interessant wäre zudem noch eine Messung, ob das Zusammenbauen eines Strings per `+` wirklich schneller ist als mittels `join`.

Fazit: Mit "Optimierungen" sollte man schon vorsichtig sein. Generell hast Du uns auch noch nicht überzeugt, ob dieser Aufwand in Deinem Anwendungsfall wirklich gerechtfertigt ist! Ich würde lieber einmalig 5 Minuten länger warten und dafür hübscheren Code haben

[Hyperion]

Ich muss gestehen, dass ich nicht verstehe, was Du da mit den dictionaries und Arrays anstellst und wo Du die eigentliche Umrechnung der 256 Bits auf 224 vornimmst.

Er rechnet nichts wirklich um, sondern legt ein Mapping an, welches Wörter beliebiger Länge auf einen Wertebereich von 224 abbildet. Quasi eine Art Hashing.

Struppi = 0
Tim = 1
usw.

Die Nummer wird sequentiell ansteigend nach dem Auftreten in der Datenreihe vergeben. Ist ein Wort also neu und hat noch keinen Schlüssel, so wird der bisher höchste Schlüsselwert ermittelt (Länge des Dictionaries) und als neuer Schlüssel genommen. Der Schlüsselbereich ist eben so definiert, dass die Zahlenwerte druckbaren ASCII-Codes entsprechen. (Meiner Meinung nach gibt es da aber noch einen Fehler bei der Berechnung... "Punkt- vor Strichrechnung"!)

Zusätzlich gibt es eben exakt fünf Spalten und zu jeder Spalte gehört ein eigenes, separates "Hashing". Die ersten beiden Spalten umfassen wohl mehr verschiedene Wörter als 224, weswegen dort eine 2Byte-Codierung vorgenommen wird.

So habe ich den Code zumindest bisher gelesen.

[jerch]

Hoppla, hab bei "...Basis 224..." und "...Datenreihe..." base224-encoding reingelesen. Danke für die Klarstellung.

[BlackJack]

Ungetestet:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class BaseEncoder(object):
    def __init__(self):
        self.word2code = dict()
    
    def __call__(self, word):
        result = self.word2code.get(word)
        if result is None:
            result = self._encode(len(self.word2code))
            self.word2code[word] = result
        return result
    
    def _encode(self, value):
        raise NotImplementedError


class SmallEncoder(BaseEncoder):
    def _encode(self, value):
        return chr(value + 32)


class LargeEncoder(BaseEncoder):
    def _encode(self, value):
        low, high = divmod(value, 224)
        return chr(low + 32) + chr(high + 32)


def encode_lines(lines):
    encoders = [
        (LargeEncoder if (i < 2) else SmallEncoder)() for i in xrange(5)
    ]
    for line in lines:
        words = line.strip('\n').split('|')
        for word, encoder in zip(words, encoders):
            yield encoder(word)


def main():
    with open('/tmp/datendatei', 'r') as lines:
        with open('/tmp/codedatei', 'w') as code_file:
            code_file.writelines(encode_lines(lines))


if __name__ == '__main__':
    main()

[Hyperion]

@BlackJack: Sieht sauber aus - wie immer

@Slag: Hier noch mal ein Test bezüglich der Stringkonkatenation:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf-8

from random import choice
from string import ascii_letters

def generate_chars(limit=100000):
    for _ in xrange(limit):
        yield choice(ascii_letters)

def concat_with_join(iterable):
    return "".join(iterable)

def concat_with_plus(iterable):
    res = ""
    for char in iterable:
        res += char
    return res

if __name__ == "__main__":
    from timeit import Timer
    for func in [concat_with_join, concat_with_plus]:
        print '{0}:'.format(func.__name__),
        t = Timer("{}(generate_chars())".format(func.__name__),
                  "from __main__ import {}, generate_chars".format(func.__name__))
        print t.timeit(10)

Hier meine Ergebnisse:

Code: Alles auswählen

concat_with_join: 1.61297798157
concat_with_plus: 1.69480490685

Auch hier gibt es eine kleine Tendenz in Richtung `join`. Selbst wenn das jetzt eher Zufall ist, so ist `join` sicherlich nicht signifikant langsamer als die andere Variante.

Eines tut es davon unabhängig aber eh: Es spart Speicher! Bei sehr großen Werten macht sich das Problem bei "+" sicherlich stärker bemerkbar.