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!

Sie sind aktuell nicht angemeldet.

Funktionen: Einloggen  |  Neu registrieren  |  Suchen

Re: Prüfen, ob zwei Bilder identisch sind
Autor: Snof
Datum: 06.11.09 18:01
Hallo Zitat: 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. 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?

Tipp 2096: Prüfen, ob zwei Bilder identisch sind	4.258	Master of VDL	06.11.09 10:18
Re: Prüfen, ob zwei Bilder identisch sind	1.632	Snof	06.11.09 18:01
Re: Prüfen, ob zwei Bilder identisch sind	1.563	Master of VDL	06.11.09 18:21

Sie sind nicht angemeldet! Um einen neuen Beitrag schreiben zu können, müssen Sie sich zunächst anmelden. Einloggen  |  Neu registrieren

Funktionen:  Zum Thema  |  Gesamtübersicht

Suchen