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: Master of VDL
Datum: 06.11.09 18:21
Argh - du hast recht mit O(n*m^2) - ich weiß auch nicht genau, wie ich auf O((n*m)!) gekommen bin. Ich habe hier darstellen wollen, dass das Hashen für diese Anwendung keinen Sinn macht, da man in beiden Fällen jedes Byte der beiden Bilder (m ist konstant bei 2) einmal einliest - nämlich entweder direkt beim Vergleich der Byte-Daten der Bilder oder beim erzeugen der Hashes der beiden Bilder. Im letzeren Fall packe ich ja noch (ein paar wenige) mehr Bytes an als im ersten - nämlich die (paar) Bytes der Hashes, die ich dann vergleiche. Diese Bytes kosten mich aber im Endeffekt extra Zeit. Sinnvoll ist das Hashen erst, wenn das erzeugen eines Hashes kürzer als O(n) ist - das würde aber theoretisch bedeuten, dass der Hash nicht alle Bytes der Daten einliest und verarbeitet, was seine Unsicherheit wieder erhöht... Das Suchen von Doppelten sollte ein Beispiel für einen Fall sein, in dem das Hashen sinnvoller ist als in dem Tipp, aber auch zeigen, dass Collissions schnell vorkommen können. Daher habe ich scheinbar bei der Angabe der Laufzeit für die naive Implementierung zur Suche von Doppelten etwas verwirrtes hingeschrieben: Ich habe nicht an die Summe 1+2+3+4+... gedacht (vergleiche bild 2 mit bild 1, bild 3 mit bildern 1 und 2, ...) sondern irgendwie an eine Multiplikation 1*2*3*4*... - weiß auch nicht warum... Danke, dass du es bemerkt und angemerkt hast.

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.631	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