Laufzeitprobleme bei Checksumberechnung

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Zap
User
Beiträge: 533
Registriert: Freitag 13. Oktober 2006, 10:56

Laufzeitprobleme bei Checksumberechnung

Beitragvon Zap » Freitag 13. Oktober 2006, 15:04

Hallo zusammen, kurz zum Hintergrund
Ich schreibe zzt ein Pythonskript in dem ich Binärdaten in Motorola-SRec format umwandle.
Dieses Format hat am Ende jeder Zeile eine Checksumme.

Diese setzt sich wie folgt zusammen:
- die Quersumme aller Bytewerte,
- von dieser Summe das einer Komplement bilden
- in diesem Wert steht das letzte byte für die gefragte Checksumme

ich habe diese Berechnung wie folgt umgesetzt:

Code: Alles auswählen

Beispiel für eine typische image_line
'S21404000018F09FE518F09FE518F09FE518F09FE5'


    def __appendChecksum(self,image_line):       
        bytesum = 0       
        # Durchläuft den String in 2er Schritten um jeweils das nächste byte zu addieren.
        for step in range(2, len(image_line), 2):
            bytesum += int(image_line[step:step+2], 16)
        # Diese Summe wird invertiert und wir filtern nur das letzte byte heraus
        checksum_int = ~bytesum & 0x000000FF

        # Abschliessend geben wir aus dem Hexstring beiden letzten chars zurück.
        # Bsp: '0x3A' -> '3A'
        return image_line + hex(checksum_int)[2:].zfill(2)


Mein Problem ist, dass bei einer Binärdatei von knapp 3 MB eine SRec-Liste von ca. 192000 image_line's zustande kommt.
Bei dem derzeitigen "Algorithmus" komme ich auf Berechnungszeiten, nur für diesen Block,
von über einer Minute. Das ist leider zu lange und ich habe noch keine andere Möglichkeit gefunden.

Fragen:
Gibt es in Python vielleicht fertige effiziente Funktionen zur Quersummenberechnung, zB einer aus Liste oder ähnlichem?
Oder hat einer eine Idee wie man diese Berechnung schneller machen könnte?

Ich hatte auch schon den Versuch gestartet, anstatt für jede Zeile die Funktion aufzurufen, die komplette Liste zu übergeben.
Aber das hat mir gerade mal (wenn überhaupt) 4 Sekunden unterschied gebracht.
Daran scheints also nicht zu liegen. Zudem brauche ich die Checksumberechnung noch vereinzelt in anderen Fällen und dann nur für eine Zeile. Deshalb bin ich "erstmal" bei der Struktur geblieben.
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Beitragvon murph » Freitag 13. Oktober 2006, 15:16

sowas ist was typisches für C/C++.
es wird wahrscheinlich eine schnellere möglichkeit in python geben,
aber sobald das mehrere mb sind, solltest du sowieso lieber etwas kompilierbares nehmen...
Zap
User
Beiträge: 533
Registriert: Freitag 13. Oktober 2006, 10:56

Beitragvon Zap » Freitag 13. Oktober 2006, 15:22

:wink: Das steht leider nicht zur Diskusion das in C oder C++ umzusetzen.
Das Skript soll seinen Platz in Python-Toolkette finden da möchte ich nicht nur wegen dem Problem aus der Reihe tanzen.
Und auch mit sowas wie nem Wrapper will ich eigentlich nicht anfangen.
BlackJack

Re: Laufzeitprobleme bei Checksumberechnung

Beitragvon BlackJack » Freitag 13. Oktober 2006, 17:00

Zap hat geschrieben:Mein Problem ist, dass bei einer Binärdatei von knapp 3 MB eine SRec-Liste von ca. 192000 image_line's zustande kommt.
Bei dem derzeitigen "Algorithmus" komme ich auf Berechnungszeiten, nur für diesen Block,
von über einer Minute. Das ist leider zu lange und ich habe noch keine andere Möglichkeit gefunden.


192000 mal die Beispielzeile durch Deine Funktion gejagt dauert auf einem 1 Ghz Athlon ca. 16 Sekunden. Entweder hast Du einen deutlich langsameren Rechner, die Beispielzeile ist nicht so repräsentativ, oder Du hast Dich bei der Anzahl der Zeilen verschätzt. Oder ein Grossteil der Zeit wird an anderer Stelle verbraucht.

Na egal hier eine Variante die bei mir ca. 30% schneller ist:

Code: Alles auswählen

HEX2INT = dict(('%02X' % i, i) for i in xrange(256))

def checksum_b(image_line):
    bytesum = 0
    for step in xrange(2, len(image_line), 2):
         bytesum += HEX2INT[image_line[step:step+2]]
   
    return '%s%02X' % (image_line, ~(bytesum & 0xFF))


Die Zeiten (checksum_a ist das Original):

checksum_a: 15.4356641769
checksum_b: 9.49234509468

Die einfachste Möglichkeit Pythonprogrammen, die was berechnen etwas Feuer unter'm Allerwertesten zu machen ist Psyco. Damit kommen diese Zeiten bei mir heraus:

checksum_a: 8.6174800396
checksum_b: 2.98888397217

Gibt es in Python vielleicht fertige effiziente Funktionen zur Quersummenberechnung, zB einer aus Liste oder ähnlichem?
Oder hat einer eine Idee wie man diese Berechnung schneller machen könnte?


Ein grosses Problem finde ich, ist diese Konvertiererei. Kannst Du nicht die Quersumme berechnen bevor eine Zeichenkette aus den Daten gemacht wird? Bytewerte in einem `array.array` kann man zum Beispiel ganz einfach mit der `sum()` Funktion aufsummieren.
Zap
User
Beiträge: 533
Registriert: Freitag 13. Oktober 2006, 10:56

Beitragvon Zap » Montag 16. Oktober 2006, 07:47

Hey super vielen dank, da hast dir ja richtig Arbeit gemacht.
Da bin ich dir wohl was Schuldig :roll:
In der interactive Shell hab ich das Skript noch nicht zum laufen gebracht, aber das finde ich sonst schon noch raus.(hoffe ich) Brauche ich dafür noch besondere Module? Bekomme diese Fehlermeldung bei der erstellung des dict: (Python-Version: 2.3 )

Code: Alles auswählen

>>> HEX2INT = dict(('%02X' % i, i) for i in xrange(256))
Could not run program because an error occurred:

invalid syntax: <string>, line 1, pos 34:

HEX2INT = dict(('%02X' % i, i) for i in xrange(256))


Traceback (innermost last):

File "<string>", line 1, in ?


Das mit den 192000 war schon richtig, es sind um genau zu sein 192.513 :)
Was meintest du mit wenig representativ? Ich wollte kein riesen Listing von Zeilen reinposten, ich glaube das gäbe Ärger :)

Bzgl der Rechnerleistung. Ich hab mal geguckt was ich hier für nen Rechner vorgesetzt bekommen habe. Ist tatsächlich nur ein 650 Mhz Ding :oops:, aber ich fand die Zeit doch sehr heftig. Hier im Betrieb werden nunmal hier und da noch so alte Schätzchen eingesetzt.
Der Zeitverbauch liegt/lag wirklich in diesem Bereich das kann ich schon soweit eingrenzen.

Mit dem Konvertieren hast du recht. Ich guck mal ob ich das anders machen kann. Das ich also die Werte nicht in str "1F" sondern als byte "\x1F" behalte. Wenn ich das richtig verstehe... Ich schau mal
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Beitragvon rayo » Montag 16. Oktober 2006, 08:21

Hi

Hier noch eine Version:

Code: Alles auswählen

import array
import binascii
def __appendChecksum(self, image_line):
    checksum_int = ~sum(array.array('b',binascii.unhexlify(i[2:]))) & 0xFF
    return '%s%02X' % (image_line,checksum_int)


Sollte eigentlich noch ein wenig schneller sein.
Falls du direkt den Binärstring bekommst einfach binascii.unhexlify weglassen

Gruss
Zap
User
Beiträge: 533
Registriert: Freitag 13. Oktober 2006, 10:56

Beitragvon Zap » Montag 16. Oktober 2006, 10:00

Danke rayo, das funktioniert sehr gut. Bin jetzt auf meiner Möhre auf 34 sec.
Runter. Das mit den Zeilen in Binärform konnte ich bisher noch nicht umsetzen. Da sich die Zeile aus mehreren Sachen vorher zusammensetzt die ich dann erst umändern muss. Ich werd das aber noch ausprobieren.

Aber wie gesagt, nochmal vielen Dank! An euch beide ;)
Benutzeravatar
Gromit
User
Beiträge: 51
Registriert: Montag 8. Mai 2006, 19:07

Psyco

Beitragvon Gromit » Dienstag 17. Oktober 2006, 09:56

Hi,
vielleicht kannst Du ja auch PsyCo einsetzten (Ok, man muß dann die ganze Umgebung updaten, aber dann haben alle Skripte was davon). Ich vermute, daß PsyCo diesen Code stark beschleunigen wird.

PsyCo-Homepage: http://psyco.sourceforge.net/

HTH,
Gerald
BlackJack

Beitragvon BlackJack » Dienstag 17. Oktober 2006, 10:46

Psyco hatte ich auch schon vorgeschlagen. Was meinst Du mit "ganze Umgebung updaten"? Das ist ein ganz normales Modul das man importiert. Da haben auch nicht automatisch alle Programme was von.

Bei rayos Variante wird Psyco auch nicht mehr rausholen weil da schon fast alles in C läuft, sowohl das `binascii` Modul, als auch die `sum()` Funktion sind in C geschrieben.
Benutzeravatar
Gromit
User
Beiträge: 51
Registriert: Montag 8. Mai 2006, 19:07

Beitragvon Gromit » Dienstag 17. Oktober 2006, 12:16

Stimmt, du hast psyco vorgeschlagen, hab ich wieder mal nicht genau gelesen, sorry.

PsyCo ist ja komplett in C implementiert und muss erstmal installiert werden. Wenn die Python-Umgebung vorgegeben ist, ist das evtl. ein Problem.

Bei in C implemenrtierten Funktionen versagt psyco in der Tat, weil er sie nicht analysieren kann.

Hier kann dann nur der Extension-Compiler von PyPy helfen. Aber die Einbindung des kompilierten rpython Codes in c-python ist wohl sehr langsam. Zudem ist er noch aufwändiger in der Anwendung als eine C-Erweiterung und kommt deshalb wohl gar nicht in Frage.
BlackJack

Beitragvon BlackJack » Dienstag 17. Oktober 2006, 12:54

Gromit hat geschrieben:Hier kann dann nur der Extension-Compiler von PyPy helfen. Aber die Einbindung des kompilierten rpython Codes in c-python ist wohl sehr langsam. Zudem ist er noch aufwändiger in der Anwendung als eine C-Erweiterung und kommt deshalb wohl gar nicht in Frage.


Da würde ich lieber Pyrex nehmen um Python-ähnliche Syntax nach C zu übersetzen. Das ist recht erprobt in der Praxis und zumindest unter Linux auch relativ einfach einsetzbar.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder