String kommt schon in Vector vor?

K

KingOfExceptions

Bekanntes Mitglied
Ich hab eine Datei, in der Wörter stehen, die ausgelesen werden und in einen Vector gepackt werden.
Es kann jedoch vorkommen, dass zwei gleiche Wörter vorkommen. Ich habe das nun so gelöst, dass jeder String mit dem anderen verglichen wird (zwei for-Schleifen). Das dauert aber bei mehreren 10k Wörtern eine Ewigkeit.
Wie kann man das besser lösen?

So hab ichs gemacht:

Java: 
for (int g = 0; g < words.size(); g++)
		{
			for (int h = 1; h < words.size(); h++)
			{
				if (words.elementAt(g).equals(words.elementAt(h)) && g != h)
				{
					words.remove(h);
				}			
			}
		}

EDIT: Ist die contains()-Methode eine Alternative? Oder ist die genau so langsam?
 
Zuletzt bearbeitet:
Nach Datum sortieren Nach Zustimmungen sortieren
Schon beim Auslesen in eine Set (z.B. LinkedHashSet) packen?! Dann kommen alle nur noch einmal vor ...

BTW es gibt kaum Gründe, einen Vector zu verwenden - außer vielleicht als eine form einer synchronsierten Liste. Dann sollte man aber tunlichst
private List<String> list = new Vector<String>();
schreibe, und überall nur die Methode aus 'List' verwenden (also z.B 'get' statt 'elementAt').
 
Zustimmen 0
Du kannst dir ja die Implementierung der contains()-Methode anschauen.
Rein theoretisch ist sie genauso schnell/langsam wie deine Methode. Läuft in O(n) und das für jedes Element kommst auch bei O(n²) raus. Aber es ist wohl besser vor dem Einfügen zu prüfen ob ein String schon vorhanden ist, da du sonst unnötige Einfüge-/Lösch-Operationen machst und gegebenenfalls die Größe des Arrays in der Vector-Klasse mehrfach änderst und dadurch das Array umkopierst.
 
Zustimmen 0
Ja.
Sets laufen viel schneller ab und erlauben keine Duplikate.
Wieso willst du denn Sachen aus einem Set "ersetzen"?
Das ist in einem Set nicht erlaubt!
Du musst löschen und neu einfügen.
 
Zuletzt bearbeitet:
Zustimmen 0
Wir sprechen hier von einem Set...
Wieso willst du da "elementAt" haben???
Ein Set ist normalerweise nicht sortiert, also das erste Element, welches du hinzufügst, steht üblicherweise auch bei einem Iterator nicht an erster Stelle. Es könnte genauso gut an x-ter Stelle oder am Schluss stehen.

Du kannst darüber iterieren oder fragen, ob ein Element existiert. Ein "elementAt(x)" ist in einem Set ziemlich sinnlos.
 
Zustimmen 0
Wenn du mit Indizes arbeiten willst, musst du mit List arbeiten und dort gibt es keine schnellere Methode als eben O(n²) (zumindest keine, die mir gerade einfällt)

Die Frage ist aber, warum die Reihenfolge wichtig ist, wenn keine Duplikate erlaubt sind.
 
Zustimmen 0
Wenn du die Einträge indiziert abfragen willst/musst nimm ne ArrayList mit passender Initialsierungs-Größe, wenn du in etwa weisst, wie viele Strings aus der Datei in die Liste gepackt werden.

Code: 
List<String> words = new ArrayList<String>(size);

Falls du mit mehreren Threads arbeitest die auf die Liste zugreifen, nimm nen Vector wie Marco13 es gepostet hat.
 
Zustimmen 0
Ich muss die Position später noch genau wissen, deswegen leider kein SET.

Ist es denn schneller, mehrere Threads laufen zu lassen, als nur einen, obwohl die ja unterbrochen werden, damit der andere Thread weitermachen kann?
 
Zustimmen 0
Das ganze kann/soll/darf vom Benutzer geändert werden, wenn er zB ein Wort findet, das dort noch nicht drin ist. Oder eben manuell Fehler (ä,ö,ü auch wenn ich das schon abändere) korrigieren.
 
Zustimmen 0
weil ich so gucke, ob eine benutzereingabe mit wörtern im vektor übereinstimmt... nicht richtig übereinstimmt, denn das programm ist schließlich eine kreuzworträtselhilfe und da weiß man ja nicht alles
 
Zustimmen 0
Okay. Beispiel: Benutzer gibt "Aachen" ein.
Was spricht dagegen:

Java: 
String input = "Aachen";
if(mySet.contains(input))
    System.out.println("Ist drin");
else
    System.out.println("Ist nicht drin");
 
Zustimmen 0
gucks dir selbst an ^^

Java: 
entry.toUpperCase();
		for (int x = 0; x < words.size(); x++)
			words.elementAt(x).toUpperCase();
		Vector<String> splittetEntry = new Vector<>(3, 5);
		Vector<String> goodWords = new Vector<>(3, 5);
		boolean foundAny = false;
		int i = 1;
		// auteilen von entry in buchstaben
		for (int x = 0; x < entry.length(); x++)
		{
			splittetEntry.add((String) entry.substring(x, i));
			i++;
		}
		boolean[] foundCorrectOne = new boolean[splittetEntry.size()];
		for (int x = 0; x < words.size(); x++)
		{
			for (int y = 0; y < splittetEntry.size(); y++)
			{
				if (splittetEntry.elementAt(y) != null
						&& entry.length() == words.elementAt(x).length())
				{
					if (!splittetEntry.elementAt(y).equals("_"))
					{
						if (splittetEntry.elementAt(y).equalsIgnoreCase(
								String.valueOf(words.elementAt(x).charAt(y))))
							foundCorrectOne[y] = true;
						else
							foundCorrectOne[y] = false;
					}
					else
						foundCorrectOne[y] = true;
				}
			}
			// Test if foundCorrectOne everything is true
			for (int j = 0; j < foundCorrectOne.length; j++)
			{
				if (foundCorrectOne[j])
					foundAny = true;
				else
				{
					foundAny = false;
					break;
				}
			}
			// if everything is true, then add word
			if (foundAny)
				goodWords.add(words.elementAt(x));
			// set all foundCorrectOne false
			for (int g = 0; g < foundCorrectOne.length; g++)
			{
				foundCorrectOne[g] = false;
				foundAny = false;
			}
		}
		// if any words found, print error
		if (goodWords.size() == 0)
			return null;
		else
			return goodWords;
 
Zustimmen 0
Ich finde deinen Code ziemlich umständlich... Einige Sachen sind unnötig:

Java: 
for (int x = 0; x < entry.length(); x++) {
            splittetEntry.add((String) entry.substring(x, i));
            i++;
}

Besser wäre meiner Meinung nach einfach
Code: 
char[] entryChars = entry.toCharArray();
Das ist doch alles, was du machen willst?

Außerdem bringt es nichts, wenn du einfach nur ein
Code: 
words.elementAt(x).toUpperCase();
aufrufst. Du machst nichts mit dem Rückgabewert also kannst du die Methode genausogut weglassen.

Genausogut wie
Code: 
entry.toUpperCase();

Java: 
if ( splittetEntry.elementAt(y).equalsIgnoreCase(String.valueOf(words.elementAt(x).charAt(y))) )
würde ich demnach mit
Java: 
if ( Character.toUpperCase( entryChars[y] ) == Character.toUpperCase( words.elementAt( x ).charAt( y ) ) ) )

Alternativ könntest du alle Einträge in deinem Vector schon von Anfang an in uppercase storen, dann gäbs am anfang leicht längere Ladezeit, aber das Programm liefe leicht schneller.


Also wenn ich dein Programm verstanden habe, willst du einen String nach Pattern "x_y__z" in deinem 'Set' nachschlagen, ob es einen Match gibt.

Sprich: "A__h_n" soll "Aachen" und "aschen" liefern etc.

Ich würde dann eher mit einem zweidimensionalen char-array arbeiten.
 
Zustimmen 0
Also wenn Wörter nur einmal vorkommen dürfen, dann auf jeden Fall ein Set (HashSet). Wenn man das Set als Liste benötigt dann lässt sich das mit "new ArrayList(mySet)" recht schnell temporär bewerkstelligen und zwecks schnellerer Suche per "Collections.sort()" sortieren.
Was in deinem Fall aber viel besser wäre:
Java: 
Set<String> wordSet = new HashSet<String>(); // noetig, damit keine doppelten Worte eingefügt werden koennen
// das immer temporaer
String[] wordList = wordSet.toArray(new String[wordSet.size()]);
Arrays.sort(wordList); // String ist Comparable, also klappt das
// needle ist die Nadel im Heuhaufen, also das gesuchte Wort.
// wurde sie nicht gefunden, wird "index" -1.
int index = Arrays.binarySearch(wordList, needle);
if(index >= 0) {
  goodWords.add(wordList[index]);
}
Das Ganze klappt dann auch mit mehrdimesionalen Char-Arrays, was durchaus 'ne Alternative ist.
 
Zuletzt bearbeitet von einem Moderator:
Zustimmen 0
Ich habs jetzt geändert, so wie ihr es meintet 🙂

Jetzt ist nur noch das Problem, dass das HashSet total langsam wird (verständlich bei 1,4 mio Einträgen).
Kann man dagegen was machen?
EDIT: Hat sich erledigt, ich hab die Kapazität am Anfang erhöht.
 
Zuletzt bearbeitet:
Zustimmen 0
Bei welcher Art Zugriff ist das HashSet denn lagsam? Beim drüberiterieren, um an ein bestimmtes Element zu kommen? evtl. wärst du ja mit einer TreeMap dann noch besser bedient, weil das ständig sortiert ist. Allerdings dauert der (hoffentlich einmalige) Ladevorgang etwas länger, weil die Zugriffszeiten beim Einfügen erbärmlich (im Gegensatz zu einem ein Array) sind. An ein bestimmtes Element kommt man dann auch ohne Index.
Java: 
TreeSet<String> words = new TreeSet<String>();

if(words.contains(needle)) {
  goodWords.add(words.tailSet(needle).first());
}

Im Zweifelsfalle würde ich mir bei dieser Masse an Daten auch nochmal ein anderes Konzept überlegen: Alle Wörter bleiben in ein oder mehreren Textdateien wo sie ausschlieslich durch ein Leerzeichen getrennt werden. Diese Dateien komplett als ein String laden und dann per RegEx nach Wortteilen suchen. Müsste theoretisch klappen, aber mit RegEx selber hab' ich noch recht wenig Erfahrung.
 
Zustimmen 0
Wenn ich das Programm richtig verstanden habe, soll es einfach nur Matches finden.
"______" würde praktisch ~10k Ergebnisse liefern etc.
Deshalb ist auch unerheblich, ob das Array sortiert ist oder nicht.
Bei "____en" kann er "lachen" genausogut wie "machen" finden.
Ich führe das mal an einem Beispiel vor:

Einträge im Wörterbuch:
lachen, machen, Drachen, Aachen, versprachen, Rachen, entfachen

Gesuchtes Wort: "__chen"

Richtige Ergebnisse: "Aachen", "machen", lachen", "Rachen"

Hier würde ich wirklich auf ein zweidimensionales Array plädieren.
Du weißt, dass es sich um 1,4 Mio Einträge handelt, also ungefähr sowas:

Java: 
char[][] entries = new char[1_500_000][];
int i = 0;
String text;
while((text = reader.readLine()) != null)
	entries[i++] = text.toCharArray(); // alternativ toUpperCase() (dauert länger)
und dann, wenn du nach dem Ergebnis suchst:

Java: 
List<String> goodWords = new ArrayList<>();
char[] needle = inputField.getText().trim().toCharArray(); //alternativ toUpperCase() (dauert fast gleich lang)
int length = needle.length();
outer: for(int i=0; i<entries.length; i++) {
	if( length != entries[i].length )
		continue outer;
	inner: for( int j = 0; j < length; j++ )
		if ( needle[j] == '_' )
			continue inner;
		else if ( needle[j] != entries[i][j] )
			continue outer;
	//word matches!
	goodWords.add(new String(needle));
}

Übrigens würde ich bei deinem Programm doppelte Einträge ignorieren. Ich finde, der Aufwand lohnt sich nicht. Du kannst die "goodWords" ja doppelte aussortieren. Ansonsten übergebe ich an Spacerat, ich halt mich da raus. 😀
 
Zuletzt bearbeitet:
Zustimmen 0
@Mujahiddin: Nee, mach' mal ruhig weiter, sieht gut aus. 🙂

'ne kleine Anregung hätt' ich aber noch: "toUpperCase()" bekommt man auch bei chars hin, das klappt aber nur bei Buchstaben zuverlässig. Entscheidend für Gross- oder Kleinbuchstabe ist das Bit 5 des ASCII-Wertes. ist es gelöscht, ist's ein kleiner, ist's gesetzt, ein grosser. Das könnte man in der Schleife mit den Vergleichen berücksichtigen, indem man dieses Bit isoliert. Beim Erstellen der Wortliste würd's weniger Sinn machen, weil die Geschwindigkeit von "toCharArray()" darunter leiden würde.
[JAVA=10]if(needle[j] & 0x5F != entries[j] & 0x5F) {[/code]
 
Zustimmen 0
Mit 0xDF geht es sogar für ü, ö und ä.
Da ist es einfach auch das fünfte Bit, aber auch siebte Bits sind dabei.

Java: 
char c = 0xDF;
System.out.println(c);

Okay, ASCII macht mir Angst...
 
Zustimmen 0
Mujahiddin hat gesagt.:
Mit 0xDF geht es sogar für ü, ö und ä.
Da ist es einfach auch das fünfte Bit, aber auch siebte Bits sind dabei.

Java: 
char c = 0xDF;
System.out.println(c);

Okay, ASCII macht mir Angst...
Zum Vergrößern anklicken....
Das kann ich mir vorstellen... 0xDF ist weit über ASCII-Max 0x7F. 0xDF gehört also schon zu Extended ASCII und benötigt daher 'ne Codepage. Wieviele CPs mit Umlauten kennst du? Schwamm drüber. Glücklicherweise geht's hier ja üm eine Kreuzworträtsel-Anwendung und da kommen Umlaute höchst selten bis gar nicht vor. 0x5F reicht also aus.
 
Zustimmen 0
😀 Du verstehst nicht, was ich andeuten wollte...
0x5F = 0101111
0xDF = 1101111
So, wir wollen die Bits so setzen, dass Kleinbuchstaben zu Großbuchstaben werden.
Also benutzen wir 0xDF:
myChar & 0xDF
Das funktioniert bei ALLEN Buchstaben des deutschen Alphabets, sogar für ü und ö und ä.

Jetzt stellt sich nur eine Frage... Was passiert bei ß? Wird das auch zum Großbuchstaben gecastet? Was ist der 'Großbuchstabe' zu ß?

Erschreckenderweise stellt sich heraus, dass 0xDF, also unsere Mask, gerade der ASCII Code für ß ist... WTF!!


Und was meinst du mit Codepage?
 
Zuletzt bearbeitet:
Zustimmen 0
Mujahiddin hat gesagt.:
😀 Du verstehst nicht, was ich andeuten wollte...
0x5F = 0101111
0xDF = 1101111
So, wir wollen die Bits so setzen, dass Kleinbuchstaben zu Großbuchstaben werden.
Also benutzen wir 0xDF:
myChar & 0xDF
Das funktioniert bei ALLEN Buchstaben des deutschen Alphabets, sogar für ü und ö und ä.

Jetzt stellt sich nur eine Frage... Was passiert bei ß? Wird das auch zum Großbuchstaben gecastet? Was ist der 'Großbuchstabe' zu ß?

Erschreckenderweise stellt sich heraus, dass 0xDF, also unsere Mask, gerade der ASCII Code für ß ist... WTF!!


Und was meinst du mit Codepage?
Zum Vergrößern anklicken....
Doch, ich verstehe sehr gut, was du andeuten wolltest. Aber Umlaute und "ß" haben nun mal das Extended-ASCII-Bit (Bit 7) gesetzt und das bedeutet, dass es ein reiner Glücksfall (zumindest in vielen anderen Ländern, ausser Deutschland bzw. Westeuropa) ist, wenn diese Konvertierung funktioniert. Das "ß" hat in CP830 (Westeuropa) übrigens den Wert 0xDF und wäre damit ein Kleinbuchstabe (sowieso). Das grosse "ß" wäre dann "ÿ" (0xFF).
 
Zustimmen 0
Nochmal: Alles in der Form
[Java]
Vector<String> splittetEntry = new Vector<>(3, 5);
...
...splittetEntry.elementAt(x)...
[/code]
sollte ersetzt werden durch
[Java]
List<String> splittetEntry = new ArrayList<>();
...
...splittetEntry.get(x)...
[/code]

Ansonsten wäre es vielleicht gut, wenn du nochmal genauer beschreiben würdest, was du erreichen willst...
 
Zustimmen 0
Ich hab mal etwas herumexperimentiert wie man die Performance der Suchanfragen verbessern kann. Auf meinem Rechner braucht der Code etwa 2 Sekunden zum laden der Daten und die Suchanfragen werden innerhalb von wenigen Millisekunden ausgeführt.

Java: 
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Main
{
	private static List<String> itemList;
	private static Map<IndexKey, IndexList> indexMap;

	public static void main(final String[] args) throws IOException
	{
		Main.itemList = new ArrayList<>();
		Main.indexMap = new HashMap<>();

		long start = System.currentTimeMillis();
		BufferedReader reader = new BufferedReader(new InputStreamReader(
				new FileInputStream(new File("german.txt")), "ISO-8859-1"));
		String line;
		while ((line = reader.readLine()) != null) {
			int index = Main.itemList.size();
			line = line.trim();
			Main.itemList.add(line);
			line = line.toLowerCase();
			for (short n = 0; n < line.length(); n++) {
				IndexKey key = new IndexKey(line.length(), n, line.charAt(n));
				IndexList indexList = Main.indexMap.get(key);
				if (indexList == null)
					Main.indexMap.put(key, indexList = new IndexList());
				indexList.add(index);
			}
		}
		reader.close();

		System.out
				.println("loadtime > " + (System.currentTimeMillis() - start));
		System.out.println("items > " + Main.itemList.size());

		start = System.currentTimeMillis();
		for (int n = 0; n < 10000; n++)
			Main.search("r___e__");
		System.out.println("searchtime > "
				+ (System.currentTimeMillis() - start));
		System.out.println("result > " + Main.search("r_c_e___e_"));
	}

	private static Set<String> search(final String search)
	{
		ArrayList<IndexList> searchList = new ArrayList<>();
		for (short n = (short) (search.length() - 1); n >= 0; n--) {
			char c = search.charAt(n);
			if (c == '_')
				continue;

			IndexList indexList = Main.indexMap.get(new IndexKey(search
					.length(), n, c));
			if (indexList == null)
				return null;

			searchList.add(indexList);
		}

		if (searchList.isEmpty())
			return null;

		TreeSet<String> result = new TreeSet<>();

		IndexList firstList = searchList.get(0);
		outerLoop: for (int n = 0; n < firstList.count; n++) {
			int index = firstList.items[n];
			for (int k = 1; k < searchList.size(); k++)
				if (Arrays.binarySearch(searchList.get(k).items, 0,
						searchList.get(k).count, index) < 0)
					continue outerLoop;

			result.add(Main.itemList.get(index));
		}
		return result;
	}

	private static class IndexKey
	{
		private final int wordLength;
		private final short position;
		private final char character;

		public IndexKey(final int wordLength, final short position,
				final char character)
		{
			this.wordLength = wordLength;
			this.position = position;
			this.character = character;
		}

		@Override
		public int hashCode()
		{
			final int prime = 31;
			int result = 1;
			result = prime * result + this.character;
			result = prime * result + this.position;
			result = prime * result + this.wordLength;
			return result;
		}

		@Override
		public boolean equals(final Object obj)
		{
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (this.getClass() != obj.getClass())
				return false;
			IndexKey other = (IndexKey) obj;
			if (this.character != other.character)
				return false;
			if (this.position != other.position)
				return false;
			if (this.wordLength != other.wordLength)
				return false;
			return true;
		}
	}

	private static class IndexList
	{
		private int count;
		private int[] items;

		public IndexList()
		{
			this.items = new int[16];
		}

		public void add(final int index)
		{
			if (this.count >= this.items.length) {
				int[] copy = new int[(int) (this.items.length * 1.3)];
				System.arraycopy(this.items, 0, copy, 0, this.items.length);
				this.items = copy;
			}
			this.items[this.count] = index;
			this.count++;
		}
	}
}
 
Zustimmen 0

Aktuelle Jobs

Neue Themen

Ähnliche Themen

HashMap<String,Vector<String>> a = new HashMap<String,Vector<String>>();
Antworten: 4
Wie oft kommt WertX int[] vor?
Antworten: 2
Stringsuche: Wie häufig kommt String1 in Strin2 vor?
Antworten: 7
Char kommt 2 mal im Wort vor (indexOf)
Antworten: 5
Zeit kommt mir zu lange vor...
Antworten: 7

Zurück
Oben