Liste durchsuchen

Status
Nicht offen für weitere Antworten.

DWetzler

Mitglied
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:

Code:
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:

Code:
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!!
 
R

Roar

Gast
: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

Mitglied
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

Top Contributor
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 !
 
G

Guest

Gast
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

Top Contributor
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.
 
G

Guest

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

Roar

Gast
?!? 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
 
G

Guest

Gast
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

Top Contributor
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).

Code:
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);
	}
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
J Dynamische Liste durchsuchen + anpassen Java Basics - Anfänger-Themen 3
R liste durchsuchen Java Basics - Anfänger-Themen 6
G Datentypen "Liste" eigener Objekte durchsuchen Java Basics - Anfänger-Themen 6
M Sortierte Liste nach Wert durchsuchen Java Basics - Anfänger-Themen 8
O Liste durchsuchen Java Basics - Anfänger-Themen 2
R Liste in Variable speichern Java Basics - Anfänger-Themen 6
R Liste und Arrays Java Basics - Anfänger-Themen 12
D 2 ArrayListen gleich sortieren bzw. eine Liste anhand einer anderen Sortieren Java Basics - Anfänger-Themen 6
J Ähnlichen String in Liste finden Java Basics - Anfänger-Themen 6
M Verkettete Liste Java Basics - Anfänger-Themen 1
M Vergleichen, ob eine Liste länger als andere ist Java Basics - Anfänger-Themen 6
H Liste nach String-Länge sortieren Java Basics - Anfänger-Themen 1
D remove Object von einer Liste von Obejcts Java Basics - Anfänger-Themen 3
E Elemente aus Liste entfernen und hinzufügen Java Basics - Anfänger-Themen 3
M Nullpointer beim befüllen meiner Liste im Object Java Basics - Anfänger-Themen 3
D Länge einer Liste aufrufen. Java Basics - Anfänger-Themen 19
B Objekt aus generalisierter Liste entfernen Java Basics - Anfänger-Themen 11
H Liste Knoten NullPointerException Java Basics - Anfänger-Themen 7
W Liste mit Listen in JTable darstellen Java Basics - Anfänger-Themen 1
N Was Passiert mit dem Namen einer Variable, wenn man diese einer Liste Hinzufügt Java Basics - Anfänger-Themen 16
E Suchfunktion in einer Liste Java Basics - Anfänger-Themen 39
T ungeordnete Werte-Paare in einer Liste Java Basics - Anfänger-Themen 7
L Hilfe! Liste mit Items werden ausgegeben aber nicht in zufälliger Reihenfolge Java Basics - Anfänger-Themen 6
berserkerdq2 Warum soll ich shuffle nutzen, um bei Rückgabewert Collection eine Liste zurückzugeben? Java Basics - Anfänger-Themen 3
sserio Wieso werden nicht alle Primzahlen bis 1000 in meine Liste gepackt ? Java Basics - Anfänger-Themen 8
sserio Liste erstellt und ein Problem mit dem Index Java Basics - Anfänger-Themen 8
f3mys Objektwerte in Liste speichern und wieder abrufen Java Basics - Anfänger-Themen 23
H Java verkettete Liste, Wert eines Index zurückgeben Java Basics - Anfänger-Themen 1
K Warum ist die binäre Suche bei der verketteten Liste nicht so effektiv? Java Basics - Anfänger-Themen 3
I 2D-Array Position der Liste ausgeben. Java Basics - Anfänger-Themen 2
I Liste von Infos von einer eigenen Annotation in Liste speichern Java Basics - Anfänger-Themen 0
P Doppelte werte in einer Liste zählen Java Basics - Anfänger-Themen 11
Dorfschmied Kartesisches Produkt von zwei Liste mit Hashmaps<String,String> erstellen Java Basics - Anfänger-Themen 4
Igig1 Autoparkplatz verkettete Liste erstes und letztes Auto Java Basics - Anfänger-Themen 13
thor_norsk Verkette Liste Java Basics - Anfänger-Themen 27
R Rückgabe: verkettete Liste Java Basics - Anfänger-Themen 2
R einfach verkettete Liste Java Basics - Anfänger-Themen 1
R einfach verkettete Liste Java Basics - Anfänger-Themen 12
O Doppelt verkette Liste Element löschen Java Basics - Anfänger-Themen 15
B GUI extension mit einer Liste verbinden Java Basics - Anfänger-Themen 1
B Verkettete Liste durchgehen und einzelne Elemente in neue Liste tun Java Basics - Anfänger-Themen 9
B Bin komplett am verzweifeln :( Verkettete Liste die Objekte hat Attribut auslesen Java Basics - Anfänger-Themen 14
M Java Liste streamen Java Basics - Anfänger-Themen 10
AmsananKING Aussortierung einer Liste Java Basics - Anfänger-Themen 8
A Objekte mit Parametern in eine Liste packen Java Basics - Anfänger-Themen 19
A Korrigierte <String> Liste zurückgeben Java Basics - Anfänger-Themen 22
S Kann nicht auf die Liste zugreifen mit der Methode!? Java Basics - Anfänger-Themen 3
B Datentyp für Einzelnes Objekt oder Liste Java Basics - Anfänger-Themen 9
alice98 Erste Schritte Liste erstellen ohne vorgefertigte Klassen Java Basics - Anfänger-Themen 1
J Doppelt verkette Liste ich bitte um Hilfe Java Basics - Anfänger-Themen 4
I Liste gruppieren nach Monat? Java Basics - Anfänger-Themen 5
districon Element in Liste einfügen Java Basics - Anfänger-Themen 1
B Hilfe bei Map Liste erstellen Java Basics - Anfänger-Themen 10
Y Einfügen in eine doppelt verkettete Liste Java Basics - Anfänger-Themen 8
Y Knoten an einem gegebenen Index aus einer Liste entfernen. Java Basics - Anfänger-Themen 6
H Daten aus einer Datei in eine Liste speichern Java Basics - Anfänger-Themen 23
Gaudimagspam Linked Liste Java Basics - Anfänger-Themen 4
Z Liste umkehren Java Basics - Anfänger-Themen 1
S Eine Liste kopieren Java Basics - Anfänger-Themen 13
java3690 Java- liste füllen ud die werte addieren Java Basics - Anfänger-Themen 13
java3690 Liste mit zufälligen zahlen füllen Java Basics - Anfänger-Themen 27
java3690 eine liste sortieren Java Basics - Anfänger-Themen 12
J Element aus Liste nehmen Java Basics - Anfänger-Themen 3
B JUnit 4: Wie man die eigene Liste testen kann [TDD] Java Basics - Anfänger-Themen 46
B Interface List - Objekt übergeben? Einzelnes Objekt geht, aber Liste nicht? Java Basics - Anfänger-Themen 4
P Was genau bringt mir es ein Array in eine Liste zu bringen Java Basics - Anfänger-Themen 3
A Doppelt verkettete Liste rückwärts ausgeben Java Basics - Anfänger-Themen 17
P Verschachtelte Array Liste Java Basics - Anfänger-Themen 2
H Liste speichern. Was lässt sich verbessern? Java Basics - Anfänger-Themen 7
P Performance Array und Liste Java Basics - Anfänger-Themen 13
M QuickSort und Liste Java Basics - Anfänger-Themen 6
N Methode um Objekte einer Liste hinzuzufügen Java Basics - Anfänger-Themen 1
B Summe von Property innerhalb einer Liste via Lambda Java Basics - Anfänger-Themen 1
V Collections int Werte in einer Liste sortieren Java Basics - Anfänger-Themen 23
B Neue Liste erstellen, wenn Objekte bestimmte Referenz hat / Gruppierung von Einträgen Java Basics - Anfänger-Themen 12
V_Fynn03 Beliebiges Element in einer Liste löschen (Java)(Lineare Datenstrukturen) Java Basics - Anfänger-Themen 9
L Baum aus Integer Liste erstellen Java Basics - Anfänger-Themen 0
CptK Koordinate in Liste suchen Java Basics - Anfänger-Themen 20
C Verschiedene Objekte in einer Liste speichern Java Basics - Anfänger-Themen 6
M Ausgabe einer Liste welche mehrere Stacks enthält Java Basics - Anfänger-Themen 3
D Doppelt Verkettete Zirkular-Liste Java Basics - Anfänger-Themen 1
L Liste in anderem Thread laden Java Basics - Anfänger-Themen 1
M Array liste Verdrehen Java Basics - Anfänger-Themen 8
A Verkettete Liste Java Basics - Anfänger-Themen 2
J Strings untereinander in einer Liste vergleichen Java Basics - Anfänger-Themen 18
B Liste von Tagen generieren ab einem bestimmten Datum und Endedatum Java Basics - Anfänger-Themen 4
S IndexOutOfBoundsException beim hinzufügen eines Elements zu einer Liste Java Basics - Anfänger-Themen 11
B Liste sortieren? Java Basics - Anfänger-Themen 4
O Anonyme Klasse einer Liste erstellen Java Basics - Anfänger-Themen 7
B SWAP List; Liste neu anordnen Java Basics - Anfänger-Themen 4
B CSS Klassen in eine Liste schreiben Java Basics - Anfänger-Themen 4
B Doppelt verkettete Liste implementieren Java Basics - Anfänger-Themen 8
L verkettete Liste Java Basics - Anfänger-Themen 15
scratchy1 doppelt verkettete Liste testen Java Basics - Anfänger-Themen 8
O ADT Liste z. B. Java Basics - Anfänger-Themen 15
B sortierte Liste Java Basics - Anfänger-Themen 4
O Knoten und Liste verarbeitung Java Basics - Anfänger-Themen 20
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
C Methoden Über eine einfach verkettete Liste Java Basics - Anfänger-Themen 8
J Eine Liste von Listen erstellen Java Basics - Anfänger-Themen 11

Ähnliche Java Themen


Oben