schneller hash algorithmus

Für alle Python / pyGame-Entwickler
Antworten
Autor
Nachricht
Benutzeravatar
taake
9 Bit
Beiträge: 656
Registriert: Fr Jun 18, 2010 08:34
Wohnort: ~/

schneller hash algorithmus

#1 Beitrag von taake » Di Jul 19, 2011 08:39

Moin,

Zum "Problem" im Moment mach ich von einer großen Datenmenge md5 fingerprints da ich sie damit leichter identifierzieren kann.
Allerdings ist die md5 generierung ziemlich lahm.

Bin jetzt auch kein experte in Sachen hash.

Daher die Frage ob es ggf. ein anderen Hash algo gibt der bei der generierung schneller ist.
#export EDITOR="$(which rm)"

Filmtipp: telnet towel.blinkenlights.nl

Benutzeravatar
torro
8 Bit
Beiträge: 365
Registriert: Fr Jan 30, 2009 22:33
Wohnort: Aachen

Re: schneller hash algorithmus

#2 Beitrag von torro » Di Jul 19, 2011 08:55

Meistens ist nicht die Berechnung des Hashwertes der wirkliche Flaschenhals, sondern eher das einlesen der Daten, da würde Dir aber dann auch kein anderer Algorithmus helfen.

Benutzeravatar
taake
9 Bit
Beiträge: 656
Registriert: Fr Jun 18, 2010 08:34
Wohnort: ~/

Re: schneller hash algorithmus

#3 Beitrag von taake » Di Jul 19, 2011 09:29

Mhmm da könnte was dran sein,
ich hab den readbuffer jetzt auf 8192 gesetzt ... bringt gefühlt zumindest eine kleine Verbesserung

Code: Alles auswählen

path4filehash = os.path.join ( oDirPaths, filename )
filehash = open ( path4filehash , 'rb' )
hash = hashlib.md5( filehash.read(8192) ).hexdigest()
#export EDITOR="$(which rm)"

Filmtipp: telnet towel.blinkenlights.nl

Benutzeravatar
boeseronkel2k
Forum Team
Forum Team
Beiträge: 976
Registriert: So Okt 09, 2005 14:24
Wohnort: 127.0.0.1:/
Kontaktdaten:

Re: schneller hash algorithmus

#4 Beitrag von boeseronkel2k » So Jul 24, 2011 16:52

das hast ja auch nur die ersten 8kb an Daten ;)

Code: Alles auswählen

path4filehash = os.path.join ( oDirPaths, filename )
fp = open ( path4filehash , 'rb' )
hash = hashlib.md5()
while True:
    data = fp.read(8192)
    if not data:
        break
    hash.update(data)
hexhash = hash.hexdigest()
fp.close()
Außerdem schließt du den Dateideskriptor nicht, das ist auch nicht gut

In diesem Beispiel liest du die komplette Datei in 8kb Blöcken und übergibst diese an die MD5 Hashing Funktion
8 Bits are enough for me, this is not where I should be!

Kleines Blog

Benutzeravatar
Christoph.Krn
10 Bit
Beiträge: 1142
Registriert: Di Mär 17, 2009 22:25

Re: schneller hash algorithmus

#5 Beitrag von Christoph.Krn » Mo Jul 25, 2011 00:18

taake hat geschrieben:[...] im Moment mach ich von einer großen Datenmenge md5 fingerprints da ich sie damit leichter identifierzieren kann.
Die Frage lautet, welche Art von und Menge an Daten du auf welche Weise identifizieren möchtest. Dein Problem hat ja eigentlich nichts mit Prüfsummen zu tun, sondern vielmehr mit dem schnellen Identifizieren von Daten. Mit mehr Informationen ist es für andere mindestens einfacher, passende Prüfsummenverfahren vorzuschlagen.

Benutzeravatar
hede
8 Bit
Beiträge: 315
Registriert: Mi Okt 08, 2008 18:37
Wohnort: Siegen ePost: gp2x342@der-he.de
Kontaktdaten:

Re: schneller hash algorithmus

#6 Beitrag von hede » Mo Jul 25, 2011 09:55

Christoph.K hat geschrieben: Die Frage lautet, welche Art von und Menge an Daten du auf welche Weise identifizieren möchtest.
Allerdings. Denn oftmals benötigt man gar keine kompletten Hashes.
Wenn man hashes in eine permanente Datenbank schreiben will, also Daten hat, die einmal archiviert werden und dann nur noch (per hash) drauf zugegriffen wird, ok, dann sollte man alles hashen.

Aber wenn es z.B. um sich ständig ändernde Daten geht, die bei jedem Lauf neu verglichen werden, kann es sich u.U. lohnen anders vorzugehen. Beispiel rsync:
Sind die Dateigrößen verschieden -> Dateien unterschiedlich
Sind sie gleich -> weiter mit nächstem Punkt.
Sind die schwachen hashes ersten paar Bytes verschieden -> Dateien sind unterschiedlich
Sind sie gleich -> stärkere hashes bzw. bit-für-bit-Vergleich anwenden
... weiter mit den nächsten bytes... usw.
(rsync hat da noch andere Feinheiten, z.B. nur geänderte Blöcke zu übertragen, aber darum geht es ja hier nicht!?)

Und bei der Wahl des Hashes an sich kommt es auch darauf an, was man damit erreichen will. Will man (böswillige) Veränderungen verhindern, dann reicht im ersten Schritt md5 u.U. schon nicht mehr und man braucht stärkere Verfahren. Um nur Unterschiede zu finden, kann man allerdings auch getrost schon auf schwächeres zurückgreifen. Günstiger berechenbar sind als Beispiel CRC-Checksummen, die für diesen Zweck u.U. ebenfalls geeignet sind. (Besonders in Hardware lassen sich diese AFAIK wesentlich einfacher realisieren als mdX oder shaX, da ein einfaches Schieberegister reicht. Aber sie bieten KEINE Sicherheit gegen absichtliche Manipulationen und bei vielen verschiedenen Datensätzen ist die Gefahr von Kollisionen deutlich höher!)

-- Mo Jul 25, 2011 12:03 --

Kannte ich selber noch nicht, aber ein wirklich schneller und einfacher Algorithmus ist z.B. Adler-32 (http://de.wikipedia.org/wiki/Adler-32)

Zum Vergleich auf Unterschiedlichkeit hervorragend geeignet: Sind zwei Adler-32-Werte verschieden, sind die Daten verschieden.
Sind die Adler-32-Werte aber gleich, besteht eine höhere Wahrscheinlichkeit als bei crc32 oder gar md5, dass die kompletten Daten dennoch verschieden sind. Dennoch kann das - je nach Anwendungsfall - durchaus ausreichend sein!
Grüße
der hede

* ...steckt mehr drin, als man denkt : http://der-he.de/ *

Antworten

Zurück zu „Python / pyGame“

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast