# Liste durchsuchen



## DWetzler (30. Apr 2006)

Hallo,
ich habe ein Programm geschrieben, welches mir alle vierstelligen Buchstabenkombinationen von a-z in eine Liste ablegt(456976 Einträge). (Z.B. aaaa, aaab,aaac,....,zzzw,zzzx,zzzy,zzzz) Mein Problem ist dass ich jetzt diese Liste auf drei verschiedene Buchstabenkombinationen(od,lo und pq) durchsuchen will und dann mir die Anzahl der gefundenen Treffer anzeigen lassen will. Ich habe folgende Methode, die ich nur zwischen Anfang und Ende ändern kann:


```
public static void test(List<String> collection)
{
long time = System.currentTimeMillis();
//Anfang
int count = 0;
for(int i = 0; i < collection.size(); i++)
{
if (((collection.get(i)).indexOf("od") != -1 )
|| ((collection.get(i)).indexOf("lo") != -1 )
|| ((collection.get(i)).indexOf("pq") != -1 ))
count++;
}
//Ende
System.out.println((System.currentTimeMillis()-time) +
"ms (Gefunden: " + count + " Elemente)");
}
```

da ich aber eine Liste mit 456976 Einträgen habe dauert diese Methode unendlich lange an.

Also habe ich diese wie folgt geändert:


```
public static void test(List<String> a){
    long time = System.currentTimeMillis();
    //Anfang
    int count = 0;
    Pattern p = Pattern.compile("od|lo|pq");

    for(int i = 0; i < a.size(); i++){
      Matcher m = p.matcher(a.get(i));
     while(m.find()){
      count++;
      }
    }
    //Ende
    System.out.println((System.currentTimeMillis()-time) +
    "ms (Gefunden: " + count + " Elemente)");
  }
```

Nur dauert diese Methode auch unendlich lange an. Habe noch versucht sie irgendwie umzuschreiben um sie so schneller durchlaufen zu lassen und auch noch verschiedene regex verwendet weil ich glaube, dass das eine gute Möglichkeit ist meine Methode schneller durchlaufen zu lassen, aber leider ohne Erfolg. Kann mir jemand sagen wie ich dass vielleicht hin bekomme dass das ganze so schnell wie möglich wird? Im Voraus vielen Dank für eure Hilfe!!


----------



## Roar (30. Apr 2006)

:autsch: die methode da dauert vielleicht ~100ms. das nennst du unendlich lange?

mit regex machst du das ganze nur noch langsamer. 
achja und wenn du collection.get(i) nur einmal pro schleifendurchlauf aufrufst kannst du bestimmt auch noch zwei drei nanosekunden einsparen


----------



## DWetzler (30. Apr 2006)

Wie nur so kurz???? Dann läuft bei mir irgendwas falsch! Habe mal probeweise meine Liste nur mit 5 Werten gefüllt. dann bekomme ich auch sofort ein ergebnis. Wenn ich aber meine Liste mit den 456976 einträgen durchlaufen lasse, merke ich nur wie mein Rechner anfängt sich abzurackern und ich kriege kein Ergebnis, als wäre er in einer Endlosschleife!? Was läuft hier falsch????


----------



## André Uhres (1. Mai 2006)

Vielleicht ein Speicherplatzproblem ?
Kommt er denn überhaupt in die Methode hinein (mach ein System.out.println am Anfang)?
Vielleicht "kurbelt" er ja an einer anderen Stelle !


----------



## Guest (1. Mai 2006)

Also, ich habe mal das ganze überprüft, in dem ich System.out.println für die Aktionen eingefügt habe, alles läuft einwandfrei. Der Rechner braucht wirklich so lange bis er die ganze Liste mit über 450000 Einträgen durchgegangenist und diese jeweils dann mit einem Treffer vergleicht. Ich glaube bis der fertig ist vergeht fast ein Tag. Gibt es keine andere Möglichkeit in eine Liste zu schauen ob diese Strings in irgendeiner Form in der Liste vorkommen? Habe nochmal nachgelesen, dass es eine Möglichkeit gibt direkt zu erfragen ob es den einen bestimmten String in der Liste gibt und was auch sehr schnell geht! Aber das funktioniert, wie gesagt nur mit contains() und auch nur für einen bestimmten String. Geht es nicht, dass ich direkt erfragen kann ob und wieviele von diesen Kombinationen in der Liste vorkommen??? Nochmals danke für jede weitere Hilfe!!!!!


----------



## byte (1. Mai 2006)

Schmeiss die Strings z.b. in ein TreeSet. Da hat die contains() ne schnellere Laufzeit, nämlich log(n). Ne unsortierte Liste läuft da im Worst Case durch alle n Elemente, also bei 450.000 Einträgen ne Menge.


----------



## Guest (1. Mai 2006)

Ist das denn so einfach möglich dass ich meine LinkedList in einen TreeSet umwandele?? Oder muss ich irgendetwas beachten?


----------



## Roar (1. Mai 2006)

?!? du benutzt eine LinkedList und greifst dann über den *index* auf die elemente zu? kein wunder dass das jahre dauert...
nimm entweder ne ArrayList oder benutz einen Iterator um über die Liste zu iterieren


----------



## Guest (1. Mai 2006)

Ja, daran lag es!! Super! Vielen Dank für eure Hilfe!!!!!!!!!!!!!!!!!!!!
Muß es jetzt nur noch schaffen die methode test ein bißchen schneller durchlaufen zu lassen. Stimmt mit pattern wird es wirklich langsamer. Wenn jemand weiß wie ich noch ein paar ms schneller werden kann, so bin ich für jeden Tip dankbar!!!


----------



## Murray (2. Mai 2006)

String#indexOf ist normalerweise eine ziemlich gut optimierte Methode, da kann man mit Bordmitteln nicht viel besser sein. Folgendes Beispiel bringt - auf meinem WinDoze-System - noch knapp 20% Verbesserung. Allerdings gibt es einen wesentlichen Unterschied - je nach exakter Aufgabenstellung ist nur eine der beiden Varianten richtig! Meine Lösung findet nämlich 61 Treffer mehr als die indexOf-Variante.  Warum ist das so: es gibt genau 61 Kombinationen, die zwei Muster gleichzeitig enthalten:

(a-z)lod (26 Möglichkeiten) enthalten sowohl lo als auch od
lod(a-z) (26 Möglichkeiten) enthalten sowohl lo als auch od

Dann gibt es noch die direkten Kombinationen von zwei Mustern:
odlo
odpq
lood
lopq
pqod
pqlo

Und dann noch das doppelte Vorkommen eines Musters:
odod
lolo
pqpq

Was ist jetzt genau gefragt: "wieviele der String enthalten (mindestens) eines der Muster?", oder "wie oft sind die Muster in den Strings enthalten?". Je nach Fragestellung stimmt nur eine der beiden Methoden. Das müsste man zuerst klären und dann die falsche Lösung entsprechend erweitern (ist in beiden Fällen ja nicht sonderlich schwierig); eigentlich kann man die beiden Implementierungen erst dann wirklich vergleichen (wobei sich der Unterschied eher vergrößern wird).


```
public void test() {
		int count = 0;
		for ( String str : strs) {
			char[] chars = str.toCharArray(); 
			for ( int i=0; i<4; i++) {
				if ( chars[i] == 'o') {
					if ( (i<3) && (chars[i+1] == 'd')) count++;
					if ( (i>0) && (chars[i-1] == 'l')) count++;
				} else if ( chars[i] == 'p') {
					if ( (i<3) && (chars[i+1] == 'q')) count++;
				} else if ( i==2) {
					//--- Sonderfall: wenn das vorletzte Zeichen weder o noch p noch l ist, 
					//--- dann kann es kein Treffer sein
					if ( chars[i] != 'l') break;
				}
			}
		
		}
		System.out.println( "test: count = " + count);
	}
```


----------

