Elegante Lösung zum Manipulieren von Collections gesucht

[kirdie]

Hintergrund
Ich schreibe gerade an einem Programm für die Uni, welches 2 optimale Teams fürs Tauziehen erstellt.
Das Problem besteht aus einer Menge von Kindern mit verschiedenen Gewichten und eine Lösung gilt als optimal, wenn die Differenz der Gesamtgewichte der beiden Teams minimal ist.
Das schreibe ich jetzt nur fürs Verständnis, ob mein Algorithmus nur wirklich optimal oder effizient ist, ist hier nicht mein Anliegen (der angegebene Code ist auch nur ein Teil der Problemlösung) , mein eigentliches Problem ist folgendes:

Ich habe eine Funktion die folgendermaßen aussieht:

       public static int tauschen(Vector<Integer> kinder,Vector<Integer> team1,Vector<Integer> team2)
	{
           		 ...
		boolean verbesserung = true;
		do
		{
			verbesserung = false;

			for(Integer kind1:team1)
				for(Integer kind2:team2)
					// Tauschen dieser beiden Kinder würde eine Verbesserung bewirken?
					if(Math.abs(sum1-sum2-2*kind1+2*kind2) < diff)
					{
						verbesserung = true;
						team1.remove(kind1);
						team2.remove(kind2);
						team1.add(kind2);
						team2.add(kind1);
						sum1+=kind2-kind1;
						sum2+=kind1-kind2;
						diff = Math.abs(sum1-sum2);
					}
		}
		while (verbesserung&&diff>0);
		return diff;
	}

Problem
Dieser Code wirft eine
java.util.ConcurrentModificationException
Grund: während man über eine Collection iteriert, darf man sie anscheinend nicht verändern.

Jetzt habe ich mir folgendes überlegt:
Ich definiere zusätzlich die Variablen

Vector<Integer> neuesTeam1 = new Vector<Integer>();
Vector<Integer> neuesTeam2 = new Vector<Integer>();
neuesTeam1.addAll(team1);
neuesTeam2.addAll(team2);


und ersetze

						team1.remove(kind1);
						team2.remove(kind2);
						team1.add(kind2);
						team2.add(kind1);

durch

						neuesTeam1.remove(kind1);
						neuesTeam2.remove(kind2);
						neuesTeam1.add(kind2);
						neuesTeam2.add(kind1);

Dies wirft allerdings schon wieder neue Probleme auf.

Neue Probleme

Da ich nach Ausführung dieser Funktion die Listen team1 und team2 noch weiterbenutzen möchte, kann ich nicht einfach

team1 = neuesTeam1;
team2 = neuesTeam2;

machen, da ein Referenzenwechsel sich ja nicht auf den Paramter außerhalb den der Funktion auswirkt, oder?

Wenn ich allerdings

			team1.removeAllElements();
			team2.removeAllElements();
			team1.addAll(neuesTeam1);
			team2.addAll(neuesTeam2);

mache ist das denke ich mal

1. unelegant
2. langsam

Wir kriegen zwar unsere Punkte nach Korrektheit und nicht nach Performanz (solange es nicht länger als 5 Sekunden läuft) oder Eleganz, aber mich wurmt sowas schon.
Deshalb wäre ich sehr dankbar, wenn mir jemand eine bessere Lösung sagen könnte.

Mein weiteres Problem ist, dass, wenn ich die Kinder in den Teams drinlasse, ich beim weiteren Iterieren über
for(Integer kind1:team1)
for(Integer kind2:team2)

Ja dasselbe kind2 nochmal drannehmen könnte, was aber eigentlich schon entfernt ist.

Das einzige was mir jetzt einfällt ist, ein break einzusetzen, wenn ein kind getauscht wurde, dass würde allerdings meiner Meinung nach wieder die Performanz verlangsamen, weil man dieselben kinder, die schon anfangs nicht tauschbar waren beim Neudurchlauf der Schleife wieder erwischt.

Idee

			for(Integer kind1:team1)
				for(Integer kind2:team2)
					// Tauschen dieser beiden Kinder würde eine Verbesserung bewirken?
					if(Math.abs(sum1-sum2-2*kind1+2*kind2) < diff)
					{
						verbesserung = true;
						neuesTeam1.remove(kind1);
						neuesTeam2.remove(kind2);
						neuesTeam1.add(kind2);
						neuesTeam2.add(kind1);
						sum1+=kind2-kind1;
						sum2+=kind1-kind2;
						diff = Math.abs(sum1-sum2);
						break;
					}
		}

Ein weiteres Problem ist für mich, dass ein break ja sicher nur aus der ersten For - Schleife springt und nicht aus der 2 und goto gibt es bei Java ja zum Glück nicht.

Wie könnte ich 1. aus den beiden for - Schleifen gleichzeitig springen oder 2. diese ganzen dummen Probleme gleich auf einmal erschlagen ohne so umständliche Workarounds zu veranstalten?

Wäre echt nett, wenn mir da ein erfahrener Listenjongleur helfen könnte, ähnliche Probleme mit Collections tauchen bei mir häufig auf.

Falls jemand Interesse an dem Problem hat und es selbst mal lösen möchte hier die Aufgabe. (bitte keine Lösungen zuschicken, den Algorithmus möcht ich schon selbst herausfinden ).

 

[byte]

Also zunächst einmal: Solange ihr nicht mit einer uralten Java Version arbeitet, verwendet keinen Vector sondern eine moderne Implementierung von List (z.B. ArrayList oder LinkedList). Ich würde LinkedList in diesem Fall verwenden, da Du die Liste ja nachträglich noch veränderst. Vector wurde nachträglich ans Collection Framework angepasst und ist langsam.

Zum Problem: Die Exception fliegt, weil die Schleifen intern einen Iterator verwenden und Du beim Iterieren die Liste veränderst. Ich bin jetzt zu faul, um mich in die Problematik reinzudenken, aber wenn Du generell durch Listen wandern willst, um sie dabei zu verändern, dann verwende eine ordinäre For-Schleife und greife über die Index auf die Elemente zu.

Wegen der Performance Sache: Erarbeite doch erstmal eine funktionierende Lösung und wenn die dann tatsälich inperformant ist, dann kannst Du immernoch über eine Alternative nachdenken!

 

[kirdie]

@Byto:
Danke für deine Antwort. Das mit dem Vector wusste ich noch garnicht. Ist aber auch schon 2 Jahre her, das wir unsere Java - Einführungskurse hatten, deshalb war das wohl wirklich eine alte Version damals.

Wenn ich eine normale For - Schleife benutze, muss ich allerdings liste.get() benutzen, was ja auch wieder langsam ist, da die Liste ja dann Schritt für Schritt traversiert werden muss. Aber das ist wahrscheinlich immer noch besser als diese Temporäre - Collection - Erzeug - und - Draufkopier Methode die ich da benutzt hab, also werd ich das wohl so machen.

Das Problem ist, dass diese doppelte For - Schleife ja schon maximal n^2 mal durchlaufen wird und wenn get dann noch alle Elemente durchlaufen muss, hab ich bei maximaler Anzahl von 100 Kindern ja schon einen Faktor von 100^3 = 1 Million Schritten, dabei hab ich Angst das mein Rechner dann ganz schön in die Knie geht.

Wegen der Performance: Es geht mir ja nicht hauptsächlich darum, ein lauffähiges Programm zu haben, sondern dabei was zu lernen, weiterhin finde ich es immer besser es gleich richtig zu machen als erstmal was zusammenzuschustern und dann hinterher dran rum friemeln zu müssen.

 

[Wildcard]

Du kannst den Iterator auch explizit erzeugen und dann über Iterator#remove die Elemente entfernen.
Bei einer LinkedList ist dringend zu empfehlen es auch so zu machen, bei einer ArrayList hingegen dürfte der Unterschied nicht weiter spürbar sein.

 

[kirdie]

Habs jetzt mal folgendermaßen probiert:

			for(Iterator<Integer> itTeam1 = team1.iterator();itTeam1.hasNext();)
			{
				Integer kind1 = itTeam1.next();
				for(Iterator<Integer> itTeam2 = team2.iterator();itTeam2.hasNext();)
				{
					Integer kind2 = itTeam2.next();
					// Tauschen dieser beiden Kinder würde eine Verbesserung bewirken?
					if(Math.abs(sum1-sum2-2*kind1+2*kind2) < diff)
					{
					verbesserung = true;
					itTeam1.remove();
					itTeam2.remove();
					team1.add(kind2);
					team2.add(kind1);
					sum1+=kind2-kind1;
					sum2+=kind1-kind2;
					diff = Math.abs(sum1-sum2);
					break;
					}
				}
			}

Die Zeile

Integer kind1 = itTeam1.next();

gibt mir allerdings immer noch eine java.util.ConcurrentModificationException.

 

[Wildcard]

Diese Zeile? :shock:
Läuft da noch ein Thread?

 

[kirdie]

Nee, das ist eine statische Methode die von der main aufgerufen wird, threads hab ich garkeine erzeugt. Weiterhin tritt die Exception nicht immer auf (ich teste es gerade mit Zufallseingaben) aber es könnte auch sein dass er in den nicht - Exceptionfällen garnicht in die Schleife kommt.

Edit:
Hab mal in die API geguckt:

"If a single thread issues a sequence of method invocations that violates the contract of an object, the object may throw this exception. For example, if a thread modifies a collection directly while it is iterating over the collection with a fail-fast iterator, the iterator will thow this exception."

Sieht so aus als dürfte man überhaupt keine Iteratoren benutzen, wenn man was ändert, ich frag mich nur wofür dann die remove methode überhaupt gut ist....

Und ich würd immer noch gerne wissen ob ein break bei verschachtelten for-schleifen aus einer oder aus allen rausgeht.

 

[Guest]

Du kannst die Collections nicht manipulieren, während du da durchiterierst.
Wenn überhaupt, dann über die Iteratoren selbst und dies auch, wenn diese
die add-Methode implementieren (siehe ListIterator).

 

[kirdie]

Du kannst die Collections nicht manipulieren, während du da durchiterierst.
Wenn überhaupt, dann über die Iteratoren selbst und dies auch, wenn diese
die add-Methode implementieren (siehe ListIterator).

Beziehst du dich jetzt auf meinen Originalpost? Habe ja noch eine geänderte Variante gepostet in der ich direkt Iterator.remove aufrufe. Oder meinst du das schon? Kannst du das vielleicht nochmal genauer angeben? Ich verstehe deine Antwort nicht so ganz.

Die Iteratoren haben keine add Methode. Heißt das ich soll statt Iterator ListIterator benutzen? Die Remove Methode haben sie ja trotzdem, wofür ist die dann da wenn man die nicht benutzen kann?

Habe es jetzt mal mit ListIteratoren versucht:

	// Lässt sich Verbesserung durch Tausch zweier Kinder erreichen?
			for(ListIterator<Integer> itTeam1 = team1.listIterator();itTeam1.hasNext();)
			{
				Integer kind1 = itTeam1.next();
				for(ListIterator<Integer> itTeam2 = team2.listIterator();itTeam2.hasNext();)
				{
					Integer kind2 = itTeam2.next();
...

Die Exception wird allerdings immer noch geworfen...

 

[Eldar]

Ein kurzer Einwurf.
Sobald du etwas veränderst, wird der Iterator ungültig und du brauchst einen neuen.

 

[kirdie]

Ein kurzer Einwurf.
Sobald du etwas veränderst, wird der Iterator ungültig und du brauchst einen neuen.

Nicht unbedingt.

		LinkedList<Integer> l = new LinkedList<Integer>();
		l.add(1);
		l.add(2);
		l.add(3);
		l.add(1);
		l.add(2);
		l.add(3);
		for(Iterator<Integer> it = l.iterator();it.hasNext();)
			{
			Integer i = it.next();
			if(i==1) it.remove();
			}
		for(Integer i:l) System.out.println(i);

Dieses Programm läuft ohne Fehler durch.

Was mir dabei allerdings aufgefallen ist, ist dass

l.remove(Integer.valueOf(1));

Die erste 1 in der Liste entfernt. Also scheint remove nicht nach Referenzengleicheit sondern nach der Equals - Methode zu funktionieren was bei mir sehr ungünstig ist. Es gibt ja manchmal mehrere Kinder mit dem selben Gewicht und da könnte ja dann das falsche entfernt werden. Kann das Problem vielleicht etwas damit zu tun haben? (gut für die Programmlösung ist es egal wenn 2 kinder das selbe Gewicht haben bewirkt die Aktion ja das gleiche aber vielleicht kommt er deswegen durcheinander?).

Jetzt wäre es nett, wenn mir vielleicht doch einer beantworten könnte wie man mit break beide For - Schleifen auf einmal beenden kann, dann müsste das Problem ja entfallen...

Edit: Habe was gefunden was anscheinend geht. Ist allerdings nicht sehr elegant (würde lieber die Schleife weiter durchlaufen) und benutzt labels was man ja nicht benutzen soll. gibt es da was besseres? (wie break 2; in php)

			hauptschleife:
			for(ListIterator<Integer> itTeam1 = team1.listIterator();itTeam1.hasNext();)
			{
				Integer kind1 = itTeam1.next();
				for(ListIterator<Integer> itTeam2 = team2.listIterator();itTeam2.hasNext();)
				{
					Integer kind2 = itTeam2.next();
					// Tauschen dieser beiden Kinder würde eine Verbesserung bewirken?
					if(Math.abs(sum1-sum2-2*kind1+2*kind2) < diff)
					{
					verbesserung = true;
					itTeam1.remove();
					itTeam2.remove();
					team1.add(kind2);
					team2.add(kind1);
					sum1+=kind2-kind1;
					sum2+=kind1-kind2;
					diff = Math.abs(sum1-sum2);
					break hauptschleife;
					}
				}
			}

 

[Wildcard]

Ich sehe gerade das du in der Liste jetzt zwar nichts mehr entfernst, aber immer noch etwas hinzufügst.
Das geht natürlich genauso wenig.

               team1.add(kind2);
               team2.add(kind1);

 

[kirdie]

Ich sehe gerade das du in der Liste jetzt zwar nichts mehr entfernst, aber immer noch etwas hinzufügst.
Das geht natürlich genauso wenig.

               team1.add(kind2);
               team2.add(kind1);

Ahhh danke. Mit

					itTeam1.add(kind2);
					itTeam2.add(kind1);

Scheint es jetzt endlich zu gehen.

 

[Guest]

Ersetze noch die add und remove Zeilen durch set.

itTeam1.set(kind2); 
itTeam2.set(kind1);

 

[Marco13]

Also zunächst einmal: Solange ihr nicht mit einer uralten Java Version arbeitet, verwendet keinen Vector sondern eine moderne Implementierung von List (...) Vector wurde nachträglich ans Collection Framework angepasst und ist langsam.

Du weißt aber hoffentlich schon, dass ein Vector und eine ArrayList praktisch identisch sind? Es gibt keinen großen Unterschied zwischen den beiden, aber einen wichtigen, nämlich dem, dass Vector synchronisiert ist - das IST er nunmal langsamer, manchmal aber notwendig...

 

[kirdie]

Oh ein Vektor wird von einem array repräsentiert? Deshalb benutz ich ja immer listen statt arrays damit ich schnell was einfügen kann... dann muss ich mir den ja wirklich schnell abgewöhnen....

 

[Wildcard]

ArrayList basiert auch auf Arrays. Wenn du viel einfügen willst und meistens nur iterierst ist ArrayList das richtige für dich.