Such-algorithmus

[Jonnny]

Hallo Zusammen,

ich habe erst vor einer Woche mit Java angefangen und stehe schon vor einem großen Problem.

Ich habe eine Datei, dessen Inhalt ich schon ein String zusammengefasst hab. Nun soll dieser String (Datei) nach einem anderen String (Suchstring) durchsucht werden.

Ich habe schon versucht etwas zu entwickeln, aber komme leider nicht weiter...bin für jede Hilfe dankbar.

  static String_suchen (String Datei, String ID)
  {
  	String sDateiStr=new String(Datei);
  	String sIDStr	=new String(ID);
  	
  	int i;
  	for (i=1; i <= sDateiStr.length(); i++)
  	{
  		if ...?
  	}
  	
  	
  	
  }

-------

Das eigentliche Ziel ist es: Dass der User mittels einer eingegebenen ID aus einer Ursprungsdatei Daten in eine neu abgelegte Datei filtern soll.

d. h. User gibt "abc" ...daraufhin wird die Ursprungsdatei nach Kopfmuster mit "abc" durchsucht. Dessen Inhalt wird dann in ein z. B. .doc-Datei abgespeichert.

 

[meez]

1. Strings wenn nicht unbedingt nötig nicht mit new instanzieren.
2. Schau dir mal indexOf() an.

 

[Sky]

Also, dein Problem mit den Dateien hin und her und neu anlegen habe ich nicht verstanden; dein String-Problem ist jedoch relativ einfach zu lösen:

  // Methoden schreibt man klein und ohne '_'
  // Variablen schreibt man ebenfalls klein
  // Rückgabetyp definieren; hier: boolean = true, wenn ID in Datei vorhanden ist
  static boolean sucheString(String datei, String id) {
    // liefert die Position von id im String Datei zurück
    // oder -1, wenn der String nicht gefunden wird.
    int pos = datei.indexOf(id); 
    return ( pos != -1 );
  }

 

[Jonnny]

hi Sky80,

ich hab nur ne Frage,

ich will ja die genaue Position des Suchstrings wiedergeben, aber mit boolean gebe ich doch einen wahrheitswert wieder oder nicht!?

 

[mic_checker]

Du kriegst zurück ob der String enthalten ist, ansonsten geb int zurück und überprüf ob -1 ist, dann ist der nicht enthalten.
andernfalls kannst du dir die position zurückgeben lassen.

also rückgabewert auf int und datei.indexOf(id) zurückgeben lassen.

 

[Jonnny]

Danke mic_checker,

so hat es geklappt.

Nun habe ich die erste Position. Ich brauche aber noch die Endposition.

Wie kann ich also nach einem best. String suchen , dass nach einer best. Position folgt ?

Das Problem ist, dass das gesuchte String sehr oft vorkommt. Mir ist aber das erste nach der Anfangsposition wichtig...die anderen sind irrelevant.

 

[mic_checker]

http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html#indexOf(int,%20int)

Dort kannst du dann spezifizieren ab welcher Position du suchen willst, guck nach der ersten Position, speicher die Position ab, dann such ab dieser Position mit der Methode den Rest wieder durch und geb es als Ergebnis zurück.


Ansonsten, wenn du das letzte Vorkommen eines best. Strings haben willst, mach lastIndexOf:

http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html

 

[Jonnny]

Also die erste Position habe ich ermittelt und unter "apos" gespeichert.

Nun habe ich aber Probleme mit dem zweiten Teil.

public int indexOf(int ch,  int fromIndex) {

(this.charAt(k) == ch) && (k >= fromIndex)

}

Wie muss dann mein Code aussehen!? Ich weiss nicht was ich statt "ch" eingeben muss. Ich will nach einem String suchen ... aber ich muss ein integer angeben? oder?
und was muss ich statt dem "k" angeben?!

Ohh...da muss ich noch viel lernen...
:###

 

[Wildcard]

Schau dir mal RegEx an.
Damit kann man so ziemlich alles mit Strings machen

 

[meez]

Schau dir mal RegEx an.
Damit kann man so ziemlich alles mit Strings machen

Aber so wenig wie möglich verwenden, da sehr langsam...

 

[Wildcard]

Aber so wenig wie möglich verwenden, da sehr langsam...

Angeblich im vergleich zu anderen Sprachen sogar sehr schnell.
Die Frage ist aber eben was das eigentlich heißt. Hat jemand mal ein paar messungen
bezüglich indexOf, StringTokenizer, RegEx gemacht, oder einen Link der auf den Performance-Unterschied näher eingeht?

 

[mic_checker]

public int indexOf(int ch,  int fromIndex) {

(this.charAt(k) == ch) && (k >= fromIndex)

}

Wie muss dann mein Code aussehen!? Ich weiss nicht was ich statt "ch" eingeben muss. Ich will nach einem String suchen ... aber ich muss ein integer angeben? oder?
und was muss ich statt dem "k" angeben?!

:###

Also das ist die "falsche" der indexOf Methoden...du brauchst:

http://java.sun.com/j2se/1.3/docs/api/java/lang/String.html#indexOf(java.lang.String,%20int)
-> indexOf(String str, int fromIndex)

Ein Beispiel-Code

   String s = "abcdhalloefghallo";
   String search_str = "hallo";

//.....
	int pos1 = s.indexOf(search_str);
	
	if(pos1 != -1) {
		int pos2 = s.indexOf(search_str,pos1+1);
		System.out.println("Erstes Mal gefunden an Stelle "+pos1);
		if(pos2 != -1)
			System.out.println("Zweites Mal gefunden an Stelle "+pos2);
		else
			System.out.println("Kein zweites Mal gefunden");
	} else 
		System.out.println("Nicht gefunden");

Beim zweiten Aufruf von indexOf gibst du an das erst ab Position pos1 + 1 gesucht werden soll (wenn ab pos gesucht wird liefert er das selbe Ergebnis nochmal).

Hoffe konnte etwas helfen.

 

[meez]

bezüglich indexOf, StringTokenizer, RegEx gemacht, oder einen Link der auf den Performance-Unterschied näher eingeht?

Ich hab die Methode replaceAll der Stringklasse mit einer selbst geschriebenen, welche auf indexOf() basiert, verglichen.
Da war die String-Klassenmethode teilweise bis zu 10 mal langsamer...

Zudem kann es logisch gar nicht schneller sein, da schlussendlich auch der Regex-Parser auf die Grundebefehle zurückgreifen muss, so wie auch indexOf() dies tut.

 

[Sky]

Ich hab die Methode replaceAll der Stringklasse mit einer selbst geschriebenen, welche auf indexOf() basiert, verglichen.
Da war die String-Klassenmethode teilweise bis zu 10 mal langsamer...

Basierte deine eigene Implementierung auch auf der String-Klasse oder hast Du mit einem Stringbuffer gearbeitet??

 

[mic_checker]

Aber so wenig wie möglich verwenden, da sehr langsam...

Angeblich im vergleich zu anderen Sprachen sogar sehr schnell.
Die Frage ist aber eben was das eigentlich heißt. Hat jemand mal ein paar messungen
bezüglich indexOf, StringTokenizer, RegEx gemacht, oder einen Link der auf den Performance-Unterschied näher eingeht?

Hab auch mal gesucht, beim javaperformanceportal wurde ich jetzt nicht fündig. Hier ist ganz wenig zu StringTokenizer (sind aber eher allgemeine Performance-Tipps):
http://www.javacommerce.com/displaypage.jsp?name=java_performance.sql&id=18264

Leider keine genauen Angaben drüber.

http://www.ftponline.com/javapro/2002_08/online/servletsjsp_08_06_02/Java Servlets Ch16.pdf
Hier wird auch wieder nur gesagt man sollte den Einsatz von StringTokenizer eher vermeiden.

Im Forum von SUN habe ich in einigen Threads auch nur grobe Angaben gefunden, z.B. das der Einsatz von StringTokenizer 4-5 mal schneller sein soll als der von split(...). Aber da weiss man ja auch nicht wie die Leute das "gemessen" haben.

Vielleicht ist ja auch der folgende Thread interessant:
http://forum.java.sun.com/thread.jspa?forumID=31&threadID=569915

Wäre allerdings auch froh wenn jemand was handfestes posten könnte ..

 

[meez]

Ich hab die Methode replaceAll der Stringklasse mit einer selbst geschriebenen, welche auf indexOf() basiert, verglichen.
Da war die String-Klassenmethode teilweise bis zu 10 mal langsamer...

Basierte deine eigene Implementierung auch auf der String-Klasse oder hast Du mit einem Stringbuffer gearbeitet??

Teils teils...