| |
![zurück](../images/b_zurueck.gif)
![](../images/48x48/info.gif) | In diesem Forum haben Sie die Möglichkeit Kommentare, Fragen und Verbesserungsvorschläge zu den im vb@rchiv gelisteten Tipps und Workshops zu posten.
Hinweis: Ein neues Thema kann immer nur über die jeweilige Tipps & Tricks bzw. Workshop Seite eröffnet werden! | Fragen zu Tipps & Tricks und Workshops im vb@rchivRe: Prüfen, ob zwei Bilder identisch sind | | ![](../images/trans.gif) | Autor: Snof | Datum: 06.11.09 18:01 |
| Hallo
Zitat: | ![](../images/trans.gif) | Sobald man aber aus mehreren Bildern (oder auch Dateien) Doppelte herausfinden will, muss man jede bisher geprüfte Datei mit der neuen vergleichen. Hier bieten sich sofort Hashes an, da man dadurch jedes Bild nur einmal Hashen muss, das Einlesen der Bilder ist also O(Anzahl Bytes pro Bild * Anzahl Bilder) oder O(Anzahl Gesamtbytes) während es O(Anzahl Gesamtbytes!) wäre, wenn man jedes mal neu alle Bilder einliest. | ![](../images/trans.gif) |
Ich seh das etwas anders. Ob das Hashen etwas bringt hängt davon ab, wie aufwendig das Vergleichen der Hashwerte ist.
Szenario 1:
Es sind bereits m Bilder der Länge n bekannt (inklusive der Hashwert). Es soll überprüft werden, ob ein gegebenes Bild bereits bekannt ist. Die Zeit für das Vergleichen der Hashwerte ist h(n).
Das Überprüfen hat ohne Hashen einen Aufwand von O(n * log m). Mit Hashen dauert es O(n + h * log m).
Szenario 2:
Es sind m Bilder der Länge n (ohne Hashwert) gegeben und es sollen Doppelte gefunden werden.
Der Aufwand ohne Hashen: O(n * m * log m)
Mit Hashen: O(n * m + h * m * log m)
Sollte nun h(n) in O(n) liegen, bringt das Hashen in Bezug auf die Komplexität nichts. Im Idealfall ist h(n) natürlich in O(1).
Die ganze Überlegung setzt vorraus, dass das Hashen in O(n) geschiet und Kollisionen nicht von Relevanz sind.
Im Endeffekt ist die ganze Sache mit dem Hashen reiner Pragmatismus. Das Vergleichen geht halt schneller, auch wenn es nur ein konstanter Faktor ist. Die Einspaarung dadurch ist größer als der Mehraufwand bei Kollision, die diese nur sehr selten auftritt.
Für die Komplexität spielt es ganz streng genommen keine Rolle, denn im schlimmsten Fall haben alle Bilder den selben Hashwert.
PS: Also die naive Implementierung zum suchen von Doppelten geht in O(n * m^2). Wie bist du auf O((n * m)!) gekommen? | ![](../images/trans.gif) |
![](../images/48x48/info.gif) | Sie sind nicht angemeldet! Um einen neuen Beitrag schreiben zu können, müssen Sie sich zunächst anmelden.
Einloggen | Neu registrieren |
![nach oben](../images/b_top.gif) ![zurück](../images/b_zurueck.gif) |
|
sevWizard für VB5/6 ![sevWizard für VB5/6](../images/werbung/sevwizard_100x100.jpg)
Professionelle Assistenten im Handumdrehen
Erstellen Sie eigene Assistenten (Wizards) im Look & Feel von Windows 2000/XP - mit allem Komfort und zwar in Windeseile :-) Weitere InfosTipp des Monats Access-Tools Vol.1 ![Access-Tools CD Vol.1](../images/werbung/apvol1_68x100.gif)
Über 400 MByte Inhalt
Mehr als 250 Access-Beispiele, 25 Add-Ins und ActiveX-Komponenten, 16 VB-Projekt inkl. Source, mehr als 320 Tipps & Tricks für Access und VB
Nur 24,95 EURWeitere Infos
|
|
|
Copyright ©2000-2024 vb@rchiv Dieter Otter Alle Rechte vorbehalten.
Microsoft, Windows und Visual Basic sind entweder eingetragene Marken oder Marken der Microsoft Corporation in den USA und/oder anderen Ländern. Weitere auf dieser Homepage aufgeführten Produkt- und Firmennamen können geschützte Marken ihrer jeweiligen Inhaber sein.
Diese Seiten wurden optimiert für eine Bildschirmauflösung von mind. 1280x1024 Pixel
|
|