Geht es auch schneller doppelte Einträge zu löschen?

[Der Programmierer]

Hi leutz,

ich hab ein Programm, welches doppelte Einträge einer Liste findet und dann einen Eintrag der beiden löscht, das sieht wie folgt aus:

			for(int i = 0; i<liste.size(); i++)
			{
				String test = liste.get(i);
				for(int x = i+1; x<liste.size(); x++)
				{
					String lol = liste.get(x);
					if(lol.equals(test))
					{
						liste.remove(x);
					}
					fortschritt=fortschritt+0.5;
					bar.setValue((int)fortschritt);

				}
			}

Allerdings ist das bei der Menge die ich habe (>40.000) sehr langsam. Gibt es da ne performantere Lösung?
Jemand hat mal gesagt das könnte man auch mit nem collections machen, aber ist das wirklich performanter?

 

[SlaterB]

wenn du deins als langsam empfindest, dann empfinde doch mal wie schnell das andere ist?
sprich: im 40.000er-Alltag benutzen oder direkt testen und Zeit messen
(System.currentTimeInMillies())

mit Map/ Set sollte das sehr viel schneller sein, ja,
bei dir werden ~ 40.000 * 40.000 Vergleiche durchgeführt,

es reichen aber 40.000, jedes Element nur einmal vergleichen,
und zwar indem man die Elemente nicht blind in einer Liste speichert sondern an einem speziell sortierten Platz

List ohneDoppelte = new ArrayList(new HashSet(alteListe));
oder ähnlich
---------

ein anschaulicheres Verfahren, auch recht gut:
die Liste sortieren (geht mit guten Algorithmen wie Collections.sort() auch deutlich schneller als 40.000 * 40.000)
und nur benachbarte Elemente vergleichen

 

[Wildcard]

Zuerst mal die Frage ob du wirklich eine Liste brauchst und nicht einfach ein Set nehmen kannst, dann kannst du dir das ganze sparen.

 

[Youlian]

Ich schließe mich meinem Vorredner an und möchte dich auch noch darauf hinweisen:
Falls "bar" eine grafische Komponente wie JProgressBar ist, würde ich die nicht bei jedem Durchlauf setzen.

Am schönsten wäre natürlich ein eigener Thread/Timer der alle paar 100ms den Fortschritt setzt. So bekommst du einen schönen, flüssigen Balken.

 

[Der Programmierer]

Edit: dieser BEitrag hat sich erledigt ich war nur zu langsam und hab die anderen posts nicht mehr mitgekriegt.

Es muss nicht unbedingt ne Liste sein. Eigentlich muss ich Zeilen in nem Textdokument die doppelten Einträge löschen.
Aber mir ist nix besseres als ne Liste eingefallen!

 

[Wildcard]

Dann einfach ein HashSet nehmen, und gut ist.

 

[Der Programmierer]

Ich glaub ich steh aufem Schlauch. Seit wann löscht HashSet alle doppelte Einträge?

Seid mir nicht böse wenn ich mich gerade etwas sehr blöd anstelle!

 

[Wildcard]

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

 

[Der Programmierer]

okay danke jetzt hab ichs geschnallt ^^

 

[Der Programmierer]

oder anscheinend doch nicht ^^
Irgendwie sind meine Dateien jetzt ganz leer!

			lnr = new LineNumberReader(new FileReader(dateiname));


			for(int i = 0 ; i<zeilen; i++)
			{
				zwischen = lnr.readLine();
				liste.add(zwischen);
				fortschritt = fortschritt + 0.5;
				bar.setValue((int)fortschritt);
			}


			BufferedWriter buffy = new BufferedWriter(new FileWriter(dateiname));
			for(int i = 0; tmp.hasNext(); i++)
			{
				it = tmp.next();
				buffy.write(it);
				buffy.newLine();
				fortschritt=fortschritt+0.5;
				bar.setValue((int)fortschritt);
			}

			buffy.close();

Hat das einen bestimmten Grund oder will Sun mich nur ärgern?

Schonmal danke für eure Hilfe
Der Programmierer

 

[Wildcard]

Der Code macht so gar keinen Sinn. Was ist liste, was ist tmp usw.?

 

[Der Programmierer]

oh entschuldigung hab ganz vergessen den Abschnitt mit den ganzen definitionen zu posten!

	LineNumberReader lnr;
	HashSet<String> liste = new HashSet<String>();	
	Iterator <String> tmp = liste.iterator();
	int zeilen;
	BufferedReader zaehler;
	String         zwischen;
	String dateiname       ;
	JProgressBar bar;
	double fortschritt = 0;
	String it;
	

//Konstruktor etc...

	public void run()
	{               


		
		System.out.println("BEI DER ARBEIT");

		try
		{
			
			lnr = new LineNumberReader(new FileReader(dateiname));


			for(int i = 0 ; i<zeilen; i++)
			{
				zwischen = lnr.readLine();
				liste.add(zwischen);
				fortschritt = fortschritt + 0.5;
				bar.setValue((int)fortschritt);
			}


			BufferedWriter buffy = new BufferedWriter(new FileWriter(dateiname));
			for(int i = 0; tmp.hasNext(); i++)
			{
				it = tmp.next();
				buffy.write(it);
				buffy.newLine();
				fortschritt=fortschritt+0.5;
				bar.setValue((int)fortschritt);
			}

			buffy.close();
			setVisible(false);

 

[Wildcard]

Den Iterator darfst du erst dann erzeugen lassen wenn das set gefüllt ist.
Ein leerer Iterator macht wenig Sinn.

 

[Der Programmierer]

Boah seiht ihr göttlich!

Das rennt wie blöd. Ich habs gerade mit 2.000.000 Einträgen probiert und es ging in unter 7 Sekunden!

Vielen dank!!!!!!!

 

[SlaterB]

das HashSet nenn mal set bzw. menge statt liste
aber über Variablennamen wie zwischen und tmp kann man ja auch streiten..

 

[Der Programmierer]

in sonem kleinen Programm gibts wichtigeres. Aber hast natürlich Recht ich ändere die mal!

 

[ray3002]

Hmmm... bin gerade auf den Thread gestossen, weil ich ein ganz ähnliches Problem habe. Ich will in irgendeiner Collection die Duplikate rausfiltern, ABER ich brauche die Häufigkeit der doppelt vorkommenden Elemente. Ich habe mal mit Collections.sort() die ganze Sache sortiert und gehe sie dann nach aufeinenander folgenden gleichen Elementen durch. Habe es mit einer LinkedList und mit einem Stack probiert, aber irgendwie wollen die ca. 220.000 Strings da nicht schnell durch. Gibt es da nicht irgendwie was bessers?
Hier mal meine Ansätze:


Mit Stack:

	public Stack<String> duplikateAussortieren(Stack<String> stack) {
		Collections.sort(stack);
		String string1;
		String string2;
		int size = stack.size();
		Stack<String> neuerStack = new Stack<String>();
		monitor.setMaximum(size);
		monitor.init();
		

		while (stack.size() > 2) {
			string1 = stack.pop();
			neuerStack.add(string1);
			string2 = stack.pop();
			monitor.setValue(size - stack.size() + (size / 100));

			if (string1.equals(string2)) {
				while (string1.equals(string2)) {
					monitor.setValue(size - stack.size() + (size / 100));
					if(stack.size() > 1)
					string2 = stack.pop();
					

				}

			} else {
				neuerStack.add(string2);
			}
		}
		monitor.clear();
		return neuerStack;

	}

Monitor kann man ignorieren, ist ein Statusbalken.

Und hier noch meine LinkedList Lösung:

	public LinkedList<String> findDuplicates(LinkedList<String> list) {
	
		for (Iterator<String> i = list.iterator(); i.hasNext();) {
		
			String s = i.next();
			if (s.equals(i.next())) {
				i.remove();
			}
		}
	
		return list;
	}

Ich programmiere noch nicht so lange, wie man sicher sehen kann ;-). Wäre aber trotzdem sehr nett, wenn mir jemand auf die Sprünge helfen könnte.

Grüße aus Kölle

Ray

[/code][/quote]

 

[SlaterB]

was genau ist denn die Frage?
dauert irgendwas davon mehr als 100 ms?
wieviele doppelte unter diesen 220.000, wie lang sind die Strings durchschnittlich?

wolltest du nicht noch die Anzahl pro Doppelten zählen?

-------


wahrscheinlich ist das Sortieren mit Abstand der größte Teil der Arbeit,
wenn du einfach nur Doppelte filtern willst, dann könntest du alle Elemente einmal in ein HashSet schreiben (und evtl. wieder in eine Liste zurück)

oder die Hauptliste unsortiert durchlaufen, Elementen nebenbei mit einem HashSet abgleichen,
(einfügen, schauen ob Set größer geworden ist oder contains() )


wenn die Liste schon sortiert vorliegt, dann gehts kaum schneller

------

edit: ach je, darum gings am Anfang des Topics ja auch schon,
man sieht, dass ich immer das gleiche wiederhole

List ohneDoppelte = new ArrayList(new HashSet(alteListe));
oder ähnlich

 

[byte]

Brauchst Du am Ende für jedes mehrfach vorkommende Element genau die Anzahl an Vorkommen? Dann könntest Du folgendes machen:

(ungetestet)

List<String> stringList ...;
Set<String> stringSet = new HashSet<String>(stringList.size());
// Mapping zwischen String und Häufigkeit
Map<String, Integer> frequency = new HashMap<String, Integer>(stringList.size());

for (String s : strings) {
  if (!stringSet.add(s)) {
    // Eintrag in Map hochzählen
  }
}

Da HashSet#add und HashMap#get/put konstante Laufzeit haben, sollte das Ganze auf ne Laufzeit von n hinauslaufen.

 

[SlaterB]

wobei die Map selber auch als Set gelten könnte

for (String) {
Integer oldCount = map.get
newCount = 1 oder oldCount+1
map.put
}

map.keySet();
ist am Ende das Set an Strings ohne Doppelte

 

[byte]

Stimmt, das ist noch besser.

 

[ray3002]

Ahhh das sieht nach einer praktikablen Möglickeit aus, werde es gleich mal ausprobieren.
Vielen Dank! Ray

 

[Gast]

@der Programmierer, dein Code vom Anfang 1. Post, hat einen Bug, Bei einer Liste oder was auch immer. Die so gestrickt ist, das es einmal zu einer Konstellation wie dieser kommt.

{bereits fertig sortiert}, element a, element a, element a

so terminiert der Algorithmus mit folgendem Ergebnis

{bereits fertig sortiert}, element a, element a.

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Vector;

public class TestSortierung {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Vector<String> vector = new Vector<String>();
		for (int i = 0; i < 3; i++) {
			vector.add("String1");
			vector.add("String2");
			vector.add("String3");
			vector.add("String4");
			vector.add("String5");
		}
		printCollection(vector);
		Vector<String> clone = (Vector) vector.clone();
		long start = System.currentTimeMillis();
		for (int i = 0; i < vector.size(); i++) {
			String test = vector.get(i);
			for (int x = i + 1; x < vector.size(); x++) {
				String lol = vector.get(x);
				if (lol.equals(test)) {
					vector.remove(x);
				}

			}
		}
		System.out.println(System.currentTimeMillis() - start);
		printCollection(vector);
		
		printCollection(clone);
		start = System.currentTimeMillis();
		HashSet<String> set = new HashSet<String>();
		for (String str : clone) {
			set.add(str);
		}
		System.out.println(System.currentTimeMillis()-start);
		printCollection(set);
	}

	private static void printCollection(Collection<String> collection) {
		
		for(String str : collection){
			System.out.println(str);
		}
		System.out.println();
	}

}

Fals es jemand ausprobieren möchte

 

[ray30002]

Vielen Dank, hatte den Bug auch schon bemerkt. Gruesse