indexOf => bestimmter Bereich

[The_S]

Hi,

wie komm ich am schnellsten an den index einer Zeichenfolge in einem StringBuilder in einem bestimmten Bereich? Also ich habe einen StringBuilder der Daten enthält, jetzt möchte ich überpüfen ob (und wenn wo) sich eine bestimmte Zeichenkette befindet. Diese Überprüfung soll aber nicht den kompletten StringBuilder betreffen, sondern meinetwegen nur von Zeichen 145 bis Zeichen 1009 . Spontan fallen mir hierzu 2 Möglichkeiten ein

1.)

int blub = string.indexOf(substr, 145);
if (blub > 1009 - blub.length()) {
   blub = -1;
}

2.)

int blub = string.substring(145, 1009).indexOf(substr)

Jetzt stellen sich folgende Fragen für mich:

- Welche der beiden Methoden ist schneller bzw. hängt das von etwas ab (Sourcecode der Klasse hat mir net wirklich weitergeholfen)?
- Gibt es evtl. noch weitere (bessere) Methoden, auf die ich bis jetzt noch nicht gekommen bin?

Danke!

 

[Azrahel]

1.)

int blub = string.indexOf(substr, 145);
if (blub > 1009 - blub.length()) {
   blub = -1;
}

2.)

int blub = string.substring(145, 1009).indexOf(substr)

Also ich tippe drauf das Methode 1 schneller ist, weil du bei Methode 2 immer erst Substringen musst, was ja dann eigentlich sowas wie ein Stringcopy ist, und erst in dem RestString suchst du nach dem Index. Aber die If kostet ja auch ein bisserl zeit und wenn die true ergibt kostet die Zuweisung ja auch wieder ein bisschen was. Könnte sich also relativieren.
Aber ist das

if (blub > 1009 - blub.length())

- blub.lenght() da richtig? Weil wenn du eh nur zwischen 145 und 1009 suchen willst reicht doch die Abfrage auf > 1009, oder?

Version 2 ist IMO schöner und sauberer, und immer gleich schnell weils keine If-Klausel drin gibt. Aber das ist ja 1. Geschmacksache, und 2. kommts auch drauf an wie Performancelastig das werden kann und ob du da echt auf jeden Fitzel schneller angewiesen bist.


Ich hoff mal ganz stramm das ich nicht grad den grössten Mist meines Lebens verzapft hab :?

 

[The_S]

Danke erstmal für die Antwort .

Also ich tippe drauf das Methode 1 schneller ist, weil du bei Methode 2 immer erst Substringen musst, was ja dann eigentlich sowas wie ein Stringcopy ist, und erst in dem RestString suchst du nach dem Index.

Bei Methode 1 wird aber in einem Bereich, der sowieso nicht beachtet werden soll, gesucht. D. h. die indexOf-Methode durchsucht x Zeichen unnötigerweise. Zusätzlich noch das hier von dir

Aber die If kostet ja auch ein bisserl zeit und wenn die true ergibt kostet die Zuweisung ja auch wieder ein bisschen was. Könnte sich also relativieren.

, was aber nicht so schwer ins Gewicht fallen sollte.

Aber ist das

if (blub > 1009 - blub.length())

- blub.lenght() da richtig? Weil wenn du eh nur zwischen 145 und 1009 suchen willst reicht doch die Abfrage auf > 1009, oder?

Ja, das ist richtig. indexOf gibt die Startpositon der Zeichenkette zurück. D. h. wenn indexOf = 1008 ist, kann sich die eigentliche Zeichenkette noch weit über Position 1009 erstrecken. Aber jetzt wo du es sagst, muss ich gleich mal überlegen, ob ich nicht beim substring noch auf die 1009 die Länge von blub draufaddieren muss anstelle sie hier abzuziehen *denk* .

2. kommts auch drauf an wie Performancelastig das werden kann und ob du da echt auf jeden Fitzel schneller angewiesen bist.

Sagen wirs mal so, der StringBuilder kann mehrere MB groß sein, eine zu suchende Zeichenkette hat zwischen 0,04% und 0,14% der Größe des StringBuilders und in den meisten Fällen durchlaufe ich sooft diesen Vorgang, bis die Gesamtgröße aller bearbeiteden Zeichenketten der Größe des Urspungs StringBuilder entspricht. Und dieser Vorgang als ganzes kann auch sehr oft ausgeführt werden. Von daher geht es mir um jede Nanosekunde

[edit] Siehe dazu auch http://www.java-forum.org/de/viewtopic.php?t=43664&highlight=

 

[Azrahel]

Also erstens nix zu danken, gern geschehen.
Dann würd ich auf Methode 2 setzen, weil wenn der in Methode 1 unnötig durchforstete RestString zu groß wird kostet das mehr zeit als das Substringing aus Methode 2. Methode 1 lohnt sich dann glaub ich nur in Bereichen in dem der Reststring entsprechend klein ausfällt, und bei 0,04% und 0,14% von mehreren mb kommt schon was zusammen, grad wenn du das mehrfach durchläufst.

[edit]Siehe dazu auch http://www.java-forum.org/de/viewtopic.php?t=43664&highlight=

Holla, ne da kommts echt auf jeden Fitzel an. Also eher direkt substringen, wobei man noch prüfen könnt welchen Teil du durchforsten willst und wo der in deinem String liegt, und dann je nach Fall Methode 1 oder Methode 2 benutzen. Aber das kostet auch wieder Zeit und ich glaub die holst du dann durch Fallabhängiges Nutzen der einen oder der andren Methode nicht raus.[/edit]

 

[The_S]

OK, danke. Ich spiel damit jetzt erstmal ein bisschen rum. Bei neuen Erkenntnissen meld ich mich nochmal. Und falls noch jemanden was einfällt, bin für alles offen .

 

[The_S]

Also, hab jetzt eine bmp (3,8 MB) mit meinem Algorithmus (link) und den unterschiedlichen Methoden überprüft, ob eine Zeichenkette enthalten ist. Zu meiner Überraschung wurde mit Methode 1 die Dateien (inkl. auslesen, aufteilen, etc.) teilweise (Abhängig von der Buffer-Größe) um bis zu 15 Sekunden, bei einer Gesamtverarbeitungszeit der Methode 1 von 23 Sekunden, schneller als Methode 2.

 

[The_S]

So, hab jetzt mal ne eigene Methode geschrieben. Je nach Größe des zu durchsuchenden Buffers (je kleiner desto schneller ist meine Methode) und der Position der Zeichnkette (je näher am Einstiegspunkt, desto langsamer ist meine Methode) ist entweder meine Methode oder die Standard "indexOf" Methode schneller. Da Übereinstimmungen (vorallem in dem zugewiesenen Buffer) seltener sind, dürfte meine Methode für mein Anwendungsgebiet die Nase vorne haben.

	private int myIndexOf(StringBuilder source, String target, int startPos, int endPos) {
		
		int tlength = target.length();
		char startChar = target.charAt(0);
		if (endPos > source.length()) {
			endPos = source.length();
		}
		if (target.length() > endPos - startPos) {
			return -1;
		}
		for (int i = 0, count = 0, pos = startPos - 1;pos + tlength < endPos;) {
			while(++pos + tlength < endPos && source.charAt(pos) != startChar);
			i = pos;
			count = 0;
			for (;count < tlength && source.charAt(i) == target.charAt(count);i++, count++);
			if (count == tlength) {
				return pos;
			}
		}
		return -1;
	}

Fällt euch noch was ein, wie man das Ganze noch ein Stückchen optimieren kann!?

Und was mir auch noch aufgefallen ist, bei manchen Dateien (z. B. ein BMP, das 500KB kleiner als mein Test-BMP ist) benötigt die StringBuilder.charAt Methode ca. 0,5 Sekunden. Bei meinem Test-BMP oder bis jetzt allen anderen getesteten Dateien liegt die Zugriffszeit im nicht Messbaren bereich. Woran liegt das?

 

[Azrahel]

Mann, alter, du schreibst Code da raucht einem ja das Hirn ab ???:L


Für die For-Schleife gabs doch ne neuere und schnellere Schreibweise, ich hab sie noch nie benutzt und weiss sie auch nicht auswendig, aber die wurd hier auch mal im Forum gepostet. Wär die auf deinen Fall anwendbar? weil dann könnteste beide Forschleifen noch durch die andre ersetzen. Würd vllt noch was bringen.

Und was mir auch noch aufgefallen ist, bei manchen Dateien (z. B. ein BMP, das 500KB kleiner als mein Test-BMP ist) benötigt die StringBuilder.charAt Methode ca. 0,5 Sekunden. Bei meinem Test-BMP oder bis jetzt allen anderen getesteten Dateien liegt die Zugriffszeit im nicht Messbaren bereich. Woran liegt das?

Wenn das BMP kleiner ist als dein testBMP dauerst länger?? ist ja hart. ich weiss ja nicht was in den Bmp drin steht, hab noch nie in eins reingeguggt, aber merkwürdig find ich das schon.

 

[The_S]

Mann, alter, du schreibst Code da raucht einem ja das Hirn ab ???:L

naja, geht so

Für die For-Schleife gabs doch ne neuere und schnellere Schreibweise

Halt ich fürn Gerücht, aber such bitte mal (ich weiß ja net nach was) => man weiß ja nie

Wenn das BMP kleiner ist als dein testBMP dauerst länger?? ist ja hart. ich weiss ja nicht was in den Bmp drin steht, hab noch nie in eins reingeguggt, aber merkwürdig find ich das schon.

Sry, falsche Info. Liegt am Algo von myIndexOf und an dem von indexOf (tritt halt bei beiden auf), hab da n bisschen n vorschnellern Schluss gezogen . Dennoch verwirt es mich, dass bei einem kleineren File (somit auch ein kleinerer Buffer) der Algorithmus um so viel langsamer sein kann (BMP mit 3,8 MB benötigt der Algorithmus eine fast nicht messbare Zeit. Bei besagtem 3,2 MB BMP aber bis zu 10 Sekunden (was sich dann beim kompletten File mit ca. 10 Minuten bemerkbar macht => dagegen stehen immerhin 3 Sekunden)). Mach ich mal auf die Suche nach dem Warum, wenn jemand ne Idee hat bzw. sogar weis warum, nehm ich das natürlich auch gerne an .

 

[Azrahel]

Das mit der Schleife hab ich gefunden, das hat ein gewisser Hobbit_im_Blurausch mal gepostet

"Bei der Auflistung in der Java-Insel fehlt noch die for-each Schleife, die es seit Java 5 gibt.

for (String str : strArray) { 
   System.out.println(str); 
}

Diese iteriert durch eine Collection oder ein Array.

Lol, sorry, wusst nur das es da was gibt, aber nicht was genau. Aber ein Versuch wars mir wert

 

[The_S]

Gibts scho seit Java 5 => nicht wirklich neu
iteriert durch listen => kann ich nicht gebrauchen
ersetzt

for (int i = 0; i < blub.length; i++)

=> nicht schneller als normal

Aber danke, jetzt darfst du dich wieder meinem eigentlichen Problem widmen

 

[Azrahel]

Du wirst lachen, ich hab schon ein wenig nach Bmp-Aufbau gegoogelt, hab nur auf die schnelle nix gefunden. Aber wenn ich nacher noch dazu komme gugg ich nochmal weiter :###

 

[The_S]

Ich glaub das hat weniger mit dem aufbau von bmps zu tun, sondern vielmehr dass eine (für den Algorithmus) äußerst ungünstige Reihenfolge an Bytes im File steht.

 

[Azrahel]

Hm, ja aber eine solche Konstellation könnte bei jedem Algorythmus vorkommen.

Und was für eine Konstellation könnte das sein? Mir fällt spontan mal keine ein die den Algorythmus so stramm runter ziehen könnte. Was ich mir vorstellen könnte wäre das das eine Bild mehr Zeilen mit weniger Bytes und das andre weniger Zeilen mit mehr Bytes hätte, da er das ganze ja 1 mal pro Zeile macht, das würd dann darauf passen. Aber ob das sein kann hab ich keine Ahnung

 

[The_S]

? Was hat das mit Zeilen zu tun? Meinste meinen Buffer? Die 0,04 - 0,14% beziehen sich nicht auf die länge von einer Zeile, sondern sind ein Erfahrungswert, mit welcher Buffergröße der Algorithmus am Besten zurecht kommt.

Kann mir das z. B. vorstellen wenn sich zwei Dateien ein bisschen ähnlich sind. Z. B. wenn beide bmp Dateien viele weiße Stellen haben, sind die bytes eben sehr identisch. D. h. myIndexOf bzw. indexOf fängt mords an zu vergleichen, trifft dann aber nach ner halben Ewigkeit auf ne Differenz. Also versucht ers mit der nächsten Position. Da kommt er (da ja überall alles weiß is) dann wieder bis zur selben Stelle und steigt dort ebenfalls wieder aus. Sowas ein paar mal und an ungünstigen Stellen könnte den Algo doch ganz schön ausbremsen.

Aber das is nur ne wilde Vermutung .

 

[Azrahel]

Das Problem haste dann aber bei jeder Farbe. Also wär ein Bild von nem Gelben Auto sehr identisch mit nem Bild mit vielen gelben Blumen. Ja, ok nicht ganz so krass, aber im prinzip schon. Aber ich denke das bekommste nicht rausoptimiert aus dem Algorythmus, oder du müsstest auch noch die Änderungen zwischen beiden Bildern vergleichen ob die in den Datein vorkommenden Änderungen der Bytes sich auch ähneln.

Oder verpeil ichs jetzt ganz? Sorry hab letzte nacht garnicht und die nacht davor nur 2 std geschlafen, ich häng grad durch :bahnhof:

 

[Azrahel]

hm, was man dabei auch prüfen könnte wär das Farb-Verteilungsmuster in dem Bild. Wo kommen welche Farben am häufigsten vor und so. aber obs dadurch genauer wird kommt echt auf die Bilder an. Auf jeden fall würds dadurch langsamer werden.

 

[The_S]

Ne, hast das schon richtig erfasst. Die Bilder werden ja dann dennoch als unterschiedlich gekennzeichnet, nur dauerts halt. Zum Glück soll sich das Tool ja auch nicht primär um Bilderdaten sondern um Binär-Dateien allgemein kümmern. Für Bilder wäre eine andere Vorgehensweise ohnehin besser geeignet (Farbwerte vergleichen statt bytes), aber evtl. liegt der Hund ja doch wo anders begraben. Hoff ma, dass mir oder einen von den schlauen Köpfen hier, noch was einfällt.

Irgendwie scheint mir, als wäre die Grenze zwischen meinen beiden Threads mehr als fließend ...

Aber aufjedenfall schonmal ein großes Danke an dich Kätzchen !

[edit] Hab deinen 2. Post jetzt erst gesehen. Geht ja wie gesagt primär nicht um Bilder. Ich test das hier nur mit einigen Dateien und das Prob ist halt zufällig mit nem Bild aufgetreten ...

 

[byte]

Hab den Thread nur mal kurz überflogen, aber eins verstehe ich nicht: Warum verwendest Du überhaupt Strings, wenn Du doch offenbar Binärdaten (Bytes) vergleichen willst?

Da wunderts mich auf jeden Fall nicht, dass Du Performance-Probleme bekommst...

 

[The_S]

Zuerst hab ich auch mit Arrays und ArrayListen gearbeitet. Blöderweiße hab ich bei der Initialisierung meines 2D-Integer-Arrays immer ab einer bestimmten Größe einen OutOfMemory Error bekommen, was bei einem StringBuilder (warum auch immer) nicht auftrat.

Lange Rede kurzer Sinn, wie würdest du denn am geschicktesten eine mehrere MB große Datei im Binärformat speichern?

 

[byte]

Spontan würde ich jetzt einfach byte-Array sagen (oder wenns geht einfach direkt mit den Streams arbeiten und gar nicht alles in den Speicher lesen). Hab aber wie gesagt nicht alles hier gelesen (zu wenig Zeit). Nur die String-Operationen sind halt langsam (daran ändert auch StringBuilder nicht viel). Mit Strings solltest Du auch tatsächlich nur arbeiten, wenn Du Zeichenketten verwendest.

Edit: Warum eigentlich 2D Integer Array? Du willst doch die Bytes von zwei Binärdateien speichern und dann irgendwie vergleichen. Dann nimm für jede Datei ein 1D-Array und schmeiss da die Bytes rein. Bei 2D ist es ja klar, dass der Speicher da recht schnell voll ist.

 

[The_S]

Bei der Verwendung von Arrays bin ich wie gesagt sehr schnell an die Grenzen gestosen (ich weis ja auch, dass Strings eher langsam ist) und direkt mit den Streams geht nicht, da ich hin und her springen muss. Hm, evtl. könnte ich eine bei einer Datei (brauche immer zwei) ein bisschen sparen, wenn ich diese nur sporatisch lade, aber bleibt das Problem mit Datei Nummer 2.

Aber schonma danke!

 

[byte]

Verstehe nicht, wo das Problem ist. Angenommen, ich habe zwei 5 MB Dateien. Das entspricht also jeweils 5242880 Bytes. Ich habe also zweimal:

new int[5242880];

Das klappt doch problemlos bei der Standard Heapsize von 64 MB.

 

[The_S]

Oh verdammt ... hab mich bei der Berechnung der Größe des Arrays (muss ein 2D Array sein) verrechnet. Deswegen die Exception . Werd meinen Code mal anpassen. Danke!

 

[The_S]

So, hier mal meine Methode, auf ints angepasst (läuft gleich alles viel schneller :

	public int myIndexOf(int[] file, int[] target, int startPos, int endPos) {
		
		int tlength = target.length;
		int startInt = target[0];
		if (endPos > file.length) {
			endPos = file.length;
		}
		if (target.length > endPos - startPos) {
			return -1;
		}
//		long start = System.currentTimeMillis();
		for (int i = 0, count = 0, pos = startPos - 1;pos + tlength < endPos;) {
			while(++pos + tlength < endPos && file[pos] != startInt);
			i = pos;
			count = 0;
			for (;count < tlength && file[i] == target[count];i++, count++);
			if (count == tlength) {
	//			System.out.println("Treffer: " + (System.currentTimeMillis() - start));
				return pos;
			}
		}
//		System.out.println("Kein Treffer: " + (System.currentTimeMillis() - start));
		return -1;
	}

Der komplette, aktualisierte Code ist hier http://www.java-forum.org/de/viewtopic.php?t=43664&highlight=

 

[byte]

:applaus:

 

[Azrahel]

Oh verdammt ... hab mich bei der Berechnung der Größe des Arrays (muss ein 2D Array sein) verrechnet. Deswegen die Exception . Werd meinen Code mal anpassen. Danke!

So wie du gestern rumgewuselt hast kein Wunder, du hast je gestern aufgedreht als gäbs heut kein Java mehr :wink: Aber cool das es jetzt schneller läuft, insgesamt ne supercoole Sache :applaus: