schnelle Listendurchsuche

L

leodennis

Gast
hi leute, ich komm einfach nicht weiter:

Ich soll ein programm schreiben, dass naja wörter übersetzt oder so ähnlich,
dazu hab ich mehrere String-Listen (die wiederum in einer Map gespeichert) sind.
Jetzt muss ich nach der Eingabe suchen die als parameter "satz" an meine Funktion übergeben wird.

HashSets sind zwar mit contains sau schnell, aber ich will wissen ob die eingabe irgendwo im String enthalten ist und den ganzen String dann an meinene ausgabe hänge damit ich zum schluss alle einträge in den Listen die den "satz" enthalten zurückgeben kann...

naja hier mein langsamer aber funktionierender code:
Java: 
private Map<String,HashSet<String>> ListenMap= new HashMap<String, HashSet<String>>();
private final static String splitString = "#s#p#";

public String sucheInListen(String satz){
		String ausgabe = "";
		String[] splitArray;
		for(String listName : ListenMap.keySet()){
			ausgabe = ausgabe.concat(("\n\n-----" + listName + "-----"));
			for(String eintrag : ListenMap.get(listName)){
				if(eintrag.toLowerCase().contains(satz.toLowerCase())){
					splitArray = eintrag.split(splitString);
					if (splitArray.length>1){
						ausgabe = ausgabe.concat("\n\n" + splitArray[0] + "\n" + splitArray[1]);
					}else{
						ausgabe = ausgabe.concat("\n\n" + splitArray[0] + "\n" + "KEIN EINTRAG!");
					}
				}
			}
		}
		return ausgabe;
	}

wichtig ist auf jeden fall, dass es super schnell geht, weil während der eingabe schon gesucht wird (so ähnlich wie bei google...)

danke für Hilfe

lg
Leo
 
L

leodennis

Gast
hmm danke, die schau ich mir mal an!

Falls wer einen lösungsvorschlag hat wo man nicht ne eigene lib für braucht ist mir das auch recht! :)
 
S

SlaterB

Gast
satz.toLowerCase()
könntest du einmal vor der Schleife machen, nicht ständig neu,
richtig schnell wird so ein Komplettdurchlauf aber nicht

Lucene kann das ganze mit unbekannten Routinen irgendwie hinkriegen,
ein Ausblick zur Eigenimplementierung dazu:
splitte alle 'Einträge' nach denen gesucht werden muss, entweder nach ganzen Wörtern, notfalls auch nach kürzeren Bestandteilen, wobei wenige Buchstaben wohl kaum noch Sinn machen,

speichere die Einträge "Montag ist toll" und "Montag ist Dienstag" und "Montag und Dienstag sind toll"
unter den Stichwörtern "Montag", "Dienstag", "toll" usw. ab, evtl. mehrfach je nach vorhandenen Stichwörtern,
wobei kleine wie "ist" und "und" und ähnliche weggelassen werden könnten, muss man abwägen
(z.B. nachträglich alles aus dem Index werfen was x% aller Einträge liefert)

dann hat man einen Suchsatz "Montag und Dienstag", erhält daraus Stichwörter "Montag", "Dienstag",
findet zu jedem Stichwort ein paar Einträge, per HashSet sind die recht schnell auf wenige gemeinsame Einträge zusammengeschmolzen,
und auf diese dann geringe Menge an Einträgen die contains-Suche

ein solcher Einsatz lohnt sich natürlich wie auch Lucene vielleicht bei 100.000 Einträgen, nicht bei 100

wenn schon während der Eingabe nach "Mon" zu suchen ist, hat man natürlich Probleme, falls der Index nicht bereits auf Dreier-Buchstabenfolgen eingestellt ist,

je mehr Platz man zur Verfügung stellt für mehrfache Indexe, desto schneller kann es werden,
neben Einzelwörtern z.B. auch auf Wortkombinationen,
wenn es die Regel gibt dass jeder Eintrag auf alle 3er-Wort-Kombinationen indexiert wird, etwa
"Montag und Dienstag sind toll" unter "Montag und Dienstag" + "und Dienstag sind" + "Dienstag sind toll" gespeichert,
und man einen Suchstring wie "Montag und Dienstag" selbst als 3er-Wort-Kombinationen identifiziert,
dann muss man nur direkt einmal in der Index-Map nach "Montag und Dienstag" schauen und erhält in einen Schritt die Liste aller passenden Einträge,

Suchaufwand auf Faktor 1 reduziert, dafür Speicheraufwand für Index sehr hoch, vielleicht zu hoch
 
L

leodennis

Gast
danke fürd die antwort,

also ich hab über 500.000 listeneinträge! d.h. weit über 1mio wörter insgesamt...

uff das schau ich mir morgen an ich bin jetzt schon fix und fertig...^^
aja während der eingabe sucht er erst wenn mehr als 4 buchstaben da stehen, aber bei "Monta" würd er halt Montag nicht finden... S:

du meinst also die eingabe splitten und die Listen sozusagen auch splitten?!
 
S

Shulyn

Bekanntes Mitglied
Du könntest deine Liste kleiner werden lassen.
Wenn ich es richtig verstanden habe beginnst du nach der eingabe des 1. zeichens mit dem suchen.
Verwende eine kopie der Liste beim Suchen, nach der 1. Eingabe (1 char) beginnst du alle Einträge zu durchsuchen, alles ohne treffer wird entfernt. So wird es nach der 1. Suchen immer schneller.

Weitere überlegungen könnten sein :
- schon nach der eingabe von 1 Zeichen mit der Suche anfangen? evtl 3 abwarten
- bei einem Treffer "bei der Eingabe" weitersuchen oder abbrechen und auf nächtes zeichen warten?

// Edit
Mal wieder zu langsam geschrieben...
leodennis hat gesagt.:
[..] aja während der eingabe sucht er erst wenn mehr als 4 buchstaben da stehen, aber bei "Monta" würd er halt Montag nicht finden... [..]
Zum Vergrößern anklicken....

[Java]
if(text.machtes(".*"+ suchWort +".*") {
// treffer
}
[/Java]

So würde er bei "Monta" auch "Montag" finden.
 
Zuletzt bearbeitet:
M

Marco13

Top Contributor
RegEx sind nicht gerade bekannt dafür, dass mit ihnen die Performance durch die Decke geht. Eher durch die der Person, die unter einem wohnt, um beim Bild zu bleiben :D
 
B

bERt0r

Gast
Was performance angeht, schon mal überlegt StringBuffer statt ""+"" zu verwenden? Bei einer entsprechenden Menge an iterationen wirkt sich das sicher aus.
 
L

ledennis

Gast
Ok ich komme immernoch nicht weiter -.-
hab jetzt über 5h gesucht und ausprobiert!

das mit StringBuffer machts schon schneller und mit toLowerCase() nur einmal am Anfang natürlich auch...

fazit:
SlaterBs Vorschlag würd ich gern machen, aber das probem sind Wörter wie:
item(s), 'Show SD', order\n, data?, Monat:, \"Ende\"
die ich ja auch finden will!

Marco13s Vorschlag hört sich auch Interessant an, aber ich hab einfach nix passendes im internet gefunden wie ich sowas umsetzen kann!

Shulyns Vorschlag wäre eine Idee, aber letztendlich zu langsam, es muss von anfang an schnell sein...

Aja und raiLs Vorschlag hab ich auch ausprobiert, aber ich finde keine beispiele wie ich damit suchen kann, das was ich gefunden habe ist wie man ordner durchsucht und vorher indexiert, aber umbasteln auf listen oder so hab ich nicht geschafft!

Also:

falls wer codebeispiele für "Apache Lucene" womit man in Listen/Sets etc. suchen kann, "Suffix tree" oder sonst ne Idee hat, her damit... :)

lg
Leo
 
S

SlaterB

Gast
wo genau besteht ein Problem bei meinem Vorschlag?
Sonderzeichen kannst du reinnehmen oder weglassen, das ist wieder der allgemeine Tradeoff:
wenn du nur "Monat" im Index hast, dann sind es weniger Index, dafür mehr Ergebnisse die je Suche zu filtern sind,
hast du für "Monat" und "Monat:" Indexe, dann sind das mehr, aber Suche nach "Monat:" geht schneller, läßt die allgemeinen "Monat" weg,

schlecht wäre in der Tat, Einträge mit "Monat:" nur unter "Monat:" abzuspeichern, nicht aber unter "Monat",
und dann nach "Monat" zu suchen und nichts bzw. nicht genau diesen Eintrag auch zu finden,

das ist aber vergleichbar mit sonstigen Wortanfängen, "Mona" wird ja auch nicht gefunden,
entweder generell den Index ausweiten auf im Extremfall beliebige Buchstabenfolgen in Wörtern oder etwas gedämpter Wortanfänge, also "Mon", "Mona" usw.,
oder falls es bei ganzen Wörtern bleibt, dann eben Nicht-Buchstaben wie ":" usw. abtrennen beim Indexieren + evtl. bei der Suche, je nachdem

ansonsten ganz konkret sagen was du hast/ planst und bei welcher Kombination exakt welches Problem vorliegt/ vermutet wird
 
L

leodennis

Gast
ok ich versuch mich mal mit deinem vorschlag, bevor ich heut garnix geschafft habe...

also
ich hab nen Vector mit allen sätzen die zu durchsuchen sind. Dann ne HashMap die als key alle wörter hat die im Vector vorkommen und als value ne liste mit allen Indexe des Vectors wo die wörter herkommen:

Vector<String>
Map<String,HashSet<Integer>>

Dann splitte ich die Eingabe nach " " in Wörter und lass mir von meiner Map alle indexe geben, dann vergleich ich die Indexe und da wo jedes Wort den gleichen index besitzt sind die Ergebnisse im Vector...

naja die keys muss ich halt entsprechend anpassen...

na dann mach ich mich mal ans Werk^^
 
B

bERt0r

Gast
Nur um mal in Erfahrung zu bringen was du überhaupt machen willst, für mich sieht es ja so aus:
Du willst Sätze übersetzten und in deiner ListenMap= new HashMap<String, HashSet<String>>().
Wenn du jetzt z.b Deutsch auf Englisch übersetzt, steht in <DeutscherSatz,<HashSet<EnglischerSatz>>.
Wenn das so ist, wäre es da nicht sinnvoller deine HashMap umzudrehen in <Deutsch<Vector<Englisch>>?
 
F

freez

Top Contributor
Bleibt es bei den 1 Mio Wörter? Grad wenn es mehr wird, könnte auch eine Datenbank helfen.

Auch wenn es etwas weniger ist, könnten so genannte NoSQL Datenbanken helfen, da die ja eigentlich auf Performance getrimmt sind. Ich denke in deinem Fall speziell an Key-Value Datenbanken. Ich meine auch mal von einer Java basierten Datenbank gelesen zu haben, welche nur im Arbeitsspeicher die Daten hält und damit rasend schnell ist.

Das sind alles Gedanken, die mir bei deiner Problemschilderung spontan gekommen sind, allerdings habe ich keine Performancevergleiche zwischen deinen Ansatz und den Datenbanken.
 
L

leodennis

Gast
So, da man bei meinem letzten Versuch eine Java heap space exception bekommen hatte und ich nicht unnötig speicher erweitern will habe ich mich für Datenbanken entschieden (SQLite) mit der es gut funktioniert!

ich mach mir mal die mühe zu erklären wie man das anstellt :)

also:

download Link für die erforderliche .jar:
http://files.zentus.com/sqlitejdbc/sqlitejdbc-v056.jar
zum Einbinden bei Eclipse: Rechtscklick auf dein Prokjekt -> "Build Path" -> "Add External Achives..." dann die .jar auswählen...

es gibt auch auf dieser Seite nen nettes Getting Started Beispiel:
SQLiteJDBC

aber um es noch schneller zu machen bin ich auf:
SQLite FTS3 and FTS4 Extensions

und hab FTS3 benutzt...

also hier zusammengefasst noch der Code den ich benutzt habe:

Java: 
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;

public class Suche {
		
	private Connection conn;
	private Statement stat;
	
	
	Suche() throws SQLException{
		try {
			Class.forName("org.sqlite.JDBC");
		} catch (ClassNotFoundException e) {
		}
		//die Datenbank "Suche.db" öffnen bzw erstellen falls sie noch nicht da ist.
		conn = DriverManager.getConnection("jdbc:sqlite:Suche.db"); 
		stat = conn.createStatement();
		
		//zum Testen:
		TabelleErstellen("Testtabelle");
		System.out.println("Ergebnis von Suche1:");
		System.out.println(sucheInTabelle("VALUE", "Testtabelle"));
		System.out.println("Ergebnis von Suche2:");
		System.out.println(sucheInTabelle("val", "Testtabelle"));
		System.out.println("Ergebnis von Suche3:");
		System.out.println(sucheInTabelle("VALUE2", "Testtabelle"));
	}	

	public String sucheInTabelle(String eingabe, String tableName) throws SQLException {
		StringBuilder ausgabe = new StringBuilder();
		
		//Abfrage erstellen wenn man genaue Ergebnisse haben will muss man die * weglassen!
		ResultSet rs = stat.executeQuery("SELECT * FROM " + tableName + " WHERE spalte1 MATCH '*" + eingabe + "*'");
		while (rs.next()) {
			ausgabe.append(rs.getString(1));
			ausgabe.append("\n");
		}
		rs.close();
		
		return ausgabe.toString();
	}
	
	public void TabelleErstellen(String tableName) throws SQLException{
		conn.setAutoCommit(false);
		//alte Tabelle löschen
		stat.executeUpdate("drop table if exists " + tableName + ";");	
		//neue Tabelle erstellen
	    stat.executeUpdate("CREATE VIRTUAL TABLE " + tableName + " USING fts3(spalte1);"); 
	    PreparedStatement prep = conn.prepareStatement("INSERT INTO " + tableName + " VALUES (?);");
	    
	    prep.setString(1, "Value1");
	    prep.addBatch();
	    
	    prep.setString(1, "Value2");
	    prep.addBatch();
	    
	    prep.setString(1, "Value3");
	    prep.addBatch();
	    //...
		
		prep.executeBatch();
		conn.commit();
		conn.setAutoCommit(true);
	}	
}

@Admin da ich nicht angemeldet bin, bitte Thema als erledigt makieren...
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Schach schnelle Zuggenerierung Allgemeine Java-Themen 3
I Methoden Schnelle Hilfe benötigt - Kleines Video/Slideshow aus mehreren Bildern erstellen Allgemeine Java-Themen 3
T "Platzsparende" und "schnelle" Indizes erzeugen Allgemeine Java-Themen 10
ruutaiokwu schnelle datenstruktur... Allgemeine Java-Themen 13
M Schnelle Scriptsprache für einfache Funktionen? Allgemeine Java-Themen 5
V Zu schnelle Buttonklicks verhindern? Allgemeine Java-Themen 8
A brauche schnelle antwort wg. schleife! Allgemeine Java-Themen 3

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben