Verschachtelte Schleifen optimieren

Java-Forum Java-Grundlagen
1

Hallo zusammen,

ich habe folgende verschachtelte Schleife:

	/**
	 * In dieser Methode werden diejenigen Zeilen zu einer zusammegefasst, die unterschiedliche, aber unmittelbar aufeinanderfolgende
	 * Gütigkeitsbereiche haben.
	 * 
	 * @param distinctBlmDataList
	 * @return die aggregierte BLM-Daten-Liste.
	 */
	private List<BlmDaten> aggregateBlmData(ArrayList<BlmDaten> distinctBlmDataList) {

		List<BlmDaten> aggregatedBlmDataList = distinctBlmDataList;

		// Alle BlmDaten in ein Array kopieren:
		final BlmDaten[] blmDatenArray = distinctBlmDataList.toArray(new BlmDaten[distinctBlmDataList.size()]);

		for (int i = 0; i < blmDatenArray.length; i++) {

			BlmDaten daten = blmDatenArray**;

			for (int j = 0; j < blmDatenArray.length; j++) {

				BlmDaten successor = blmDatenArray[j];

				if ((!daten.equals(successor)) && (daten.isAppendable(successor))) {

					daten.setGueltigBis(successor.getGueltigBis());
					aggregatedBlmDataList.remove(successor);
				}
			}
		}
		return aggregatedBlmDataList;
	}

Ziel der Methode: ich habe eine Liste von Daten, in der bis auf den Gültigkeitsbereich alle Daten gleich sind. Wenn der Gültigkeitsbereich aufeinanderfolgt (
Satz 1 gueltigVon = 01.02.2014 gueltigBis = 31.03.2014
Satz 2 gueltigVon = 01.04.2014 gueltigBis = 30.04.2014
etc… das können 1-n Sätze sein die gleich sind.

Diese Sätze möchte ich dann zu einem Objekt zusammenfassen und das niedrigste gueltigVon und das höchste gueltigBis-Datum setzen. Im oben genannten Beispiel wäre das dann de Satz mit gueltigVon = 01.02.2014 und gueltigBis = 30.04.2014

Gibt es eine bessere Möglichkeit als die verschachtelten Schleifen? Teilweise kommen an die 1000 Datensätze zurück, was das ganze sehr langsam macht.
die Methode isAppendable ist implementiert wie die equals-Methode, nur das dabei der Gültigkeitsbereich mit berücksichtigt wird.

Wenn jemand eine Idee hat, das ganze performancetechnisch zu optimieren, wäre ich echt dankbar! Ich hoffe ich konnte es verständlich erklären.

2

Fang erstmal an, Dir zu überlegen, was jede einzelne Schleife macht. Gib dem Ding einen Namen und lager das in eine eigene Methode aus. Das macht den Code lesbar. Ansonsten bin ich mir nicht ganz sicher,was das Umkopieren in ein Array soll. Das frisst bei vielen Daten ganz sicher Performance.

3

bei 1000 sollte es keine Rolle spielen, an sich ist aber die doppelte Schleife ein Problem,
1000 mal die innere Schleife ausgeführt macht Größenordnung 1 Mio. Arbeitsschritte

wie liegen die Daten ursprünglich vor, schon zeitlich sortiert?
reicht es, jeden Eintrag nur mit dem Nachfolger zu vergleichen? dann beschränke dich darauf:
nur EINE Schleife, letzten Eintrag merken, mit aktuellen Vergleichen, evtl. kopieren

es ist übrigens evtl. performanter, 700 Einträge in eine neue Liste einzufügen, als 300 aus einer vollen zu entfernen,
beim Entfernen am Anfang müssen alle dahinter stehenen Elemente um 1 Position verschoben werden (bei ArrayList)

wenn die Einträge unsortiert sind, kann es schwieriger werden, gibt es sich überlagernde Zeiträume, mehrere Einträge die an Tag X enden?
dabei noch equal oder unterschiedliche andere Kategorien?

es braucht in jedem Fall eine Map, in der alle bisherigen Einträge abgelegt werden,
für jeden neuen Eintrag muss ein Key gefunden werden um in einem Schritt nachschauen zu können, ob ein Zusammenfass-Partner vorhanden ist oder nicht

z.B. liegt in der Map
„Kategorie 12 - 31.01.2014“ → Eintrag X
„Kategorie 12 - 31.03.2014“ → Eintrag Y

neuer aktuell untersuchter Eintrag Z hat Kategorie 12 und beginnt am 1.4.2014,

nun muss man einen entsprechenden Key zusammenbauen,
dabei leider mit Kalender-Methoden den Vortag ermitteln, etwas unschön, aber isAppendable()-Methode kann dabei nicht helfen,
außer wieder mit paarweisen Vergleich, was eben langsam ist

also Such-Key „Kategorie 12 - 31.03.2014“ bauen, Eintrag Y finden, die beiden zusammenfassen wenn gefunden, alten Key löschen, neuen Key (neues Enddatum) ablegen,
und weiter

lohnt sich alles normalerweise nur bei sehr vielen Daten, 1 Mio. x 1 Mio. wären schon sehr viele Vergleiche,
bei 1000x1000 kann die Map-Variante mit aufwendigen Strings auch viel langsamer sein

was heißt sehr langsam? sind 1000 die Anzahl an Ergebnissen oder Rohdaten, wie stark wird komprimiert?
versuche zu untersuchen, wo die Zeit verloren geht,
wie lange dauert es, wenn equals bzw. das ganze if weggelassen wird

4

Also für mich sieht die sache ganz einfach aus: Du sortierst deine Liste nach Gültigkeitsdatum und gehst sie dann einmal durch, vergleichst je zwei Objekte und fasst sie dann zusammen falls möglich.

5

[quote=bERt0r]Also für mich sieht die sache ganz einfach aus: Du sortierst deine Liste nach Gültigkeitsdatum und gehst sie dann einmal durch[/quote]sehe ich auch so.
Und das Sortieren überlässt Du einen [JAPI]TreeSet[/JAPI] mit passendem [JAPI]Comparator[/JAPI]…

bye
TT

6

Wenn die Daten unsortiert sind, würde es sich auf jeden Fall lohnen, sie (ggf. in einer neuen Liste) zu sortieren, weil man damit nicht O(n^2) sondern nur noch O(n logn) hat, und man danach das ganze mit einem durchlauf erledigen kann. Das aggregatedBlmDataList.remove ist mir aber auch aufgefallen: “remove” hat O(n), da kann man sich durch so eine Zeile seinen Algorithms leicht kaputt machen (aber die Frage würde sich bei einem anderen Ansatz gar nicht stellen)

EDIT: Hoppala :o das Tab war noch von gestern offen :o

7

Danke erstmal für die Antworten :slight_smile: …
folgendes Bild zeigt mal ein paar Beispiel-Daten - der gelb markierte Bereich soll zu einem Datensatz zusammengefasst werden.
Ich habe für den Datentyp sowohl eine equals-Methode, als auch eine „abgewandelte“ equals-Methode (isAppendable), die dann true zurückgibt, wenn sich ein Datensatz nur um den Gültigkeitsbereich unterscheidet, und dieser fließend ineinerander (selber Tag oder +1 Tag) übergeht.
Die Daten kommen schon sortiert rein. Ich denke eine Map mit irgendeinem zusammengesetzten Key wäre hier die beste Lösung.

8

wenn alles in Reihenfolge liegt und nur benachbartes zusammenzufassen ist, dann reicht eine schlichte Schleife

9

Können gleiche “gültigVon” mit ungleichen “gültigBis” auch appendable sein?
Naja, wie dem auch sei. Ich würde da gar nicht mit Arrays arbeiten, sondern mit einem Iterator und einem TreeSet, welches sich nach jedem Durchgang aktualisiert (BlmDaten müssen dafür entweder comparable sein oder es muss ein externer Comparator verwendet werden; sortieren nach “gültigVon”).

BlmDaten current = outer.first();
do {
  Iterator<BlmDaten> inner = new ArrayList<BlmDaten>(distinctBlmDataList).iterator();
  while(inner.hasNext()) {
    BlmDaten test = inner.hasNext();
    if(!current.equals(test) && current.isAppendable(test) {
      current.setGueltigBis(test.getGueltigBis());
      inner.remove();
    }
  }
  outer = new TreeSet<BlmDaten>(distinctBlmDataList); // wichtig, weil sich die Liste verändert haben könnte
  current = outer.higher(current);
} while(current != null);```BTW.: Bin mir grad nicht sicher, ob "<TreeSet>.first()" bzw <TreeSet>.higher()" eine NoSuchElementException wirft, wenn das Ende des Sets überschritten wurde. Die müsste sonst ggf. abgefangen und "current" explizit auf null gesetzt werden.
10

Es könnten auch noch werte dazwischen liegen, die als eigener Datensatz bestehen bleiben müssen. Ich muss glaub ich nochmal in Ruhe darüber nachdenken oder erstmal nicht darüber nachdenken. Danke auf jeden Fall.

*** Edit ***

Das sieht nach nem gute Ansatz aus! Danke!

11

@Spacerat
sieht nach merkwürdigen Code aus,

  • remove aus Liste ist teuer, Elemente werden verschoben
  • ständig neue TreeSet erzeugen, ineinander verschachtelte Schleifen (wie am Anfang des Threads)?
    das klingt ja nach dem Gegenteil von Optimierung,

was sollte so kompliziert sein das alles zu rechtfertigen?
die Grundregel ist, sich auf einen Schleifendurchlauf zu beschränken, linearer Aufwand, konstante Arbeit pro Eintrag,

nur mit Nachfolger oder ein paar Nachbarn vergleichen, in sortierter Liste evtl. direkt möglich,
mit Map je nach Aufwand für Key eindeutiger,

einmalige Sortierung mit Aufwand n log n wäre notfalls gewiss akzeptabel dabei

12

ich glaube ich denke zu kompliziert :frowning: ich versuxche mal ne Map und einen entsprechenden Key - der kann ja auch zusammengesetzt sein.

*** Edit ***

ok -also die einfache Schleife wird schwer, weil auch diese Fälle abgedeckt werden müssen:

  1. 10.10.2013 – 12.10.2013
  2. 19.10.2013 – 20.10.2013
  3. 11.10.2013 – 14.10.2013

hier müssten dann 1. und 3. zusammengefügt werden… 2. bliebe als eigener Datensatz stehen.
Also doch in irgendeiner Form die Map.

13

Beginn von 3. ist vor Ende von 1., die Zahlen 11 und 12 vertauscht?
oder solche Überlappungen auch zu bedenken? das würde es nicht einfacher machen… (edit: oder doch, je nach Regeln…)

eine Sortierung ist hier überhaupt nicht zu erkennen, Sortierung wäre Grundvorausetzung für nur-Schleife-über-Liste-Lösung

für theoretisches Beispiel

  1. 10.10.2013 – 15.10.2013
  2. 11.10.2013 – 20.10.2013
  3. 16.10.2013 – 19.10.2013
    sortiert nach Beginn-Datum,
    könnte die Regel lauten, innerhalb der Liste nicht nur den direkten Nachfolger anzuschauen, sondern soweit bis Beginn von Nachfolgern nach aktuellen Ende liegt,
    also eine unbestimmte Anzahl weiterer Einträge prüfen, hier würde man vom 1. aus auch den 3. anschauen und diese dann zusammenfassen könnnen

Problem ist die Unbestimmtheit, theoretisch könnte man hunderte/ alle Nachfolger anschauen müssen, dann wieder effektiv bei der Doppelschleife,

aus der Sichtweise kann die Map besser sein:

    1. Eintrag in der Map ablegen mit Key 15.10.2013, konstante Arbeit
    1. Eintrag kommt dran…
    1. Eintrag SuchKey 15.10.2013 berechnen, nachschauen, den 1. Eintrag finden, sie zusammenfassen, neu ablegen usw., alles in konstanter Arbeit

klappt soweit ohne Betrachtung von Problemem doppelter Einträge mit gleichen Datum, Unterscheidungskategorien usw.

14

[QUOTE=SlaterB]@Spacerat
sieht nach merkwürdigen Code aus,

  • remove aus Liste ist teuer, Elemente werden verschoben
  • ständig neue TreeSet erzeugen, ineinander verschachtelte Schleifen (wie am Anfang des Threads)?
    das klingt ja nach dem Gegenteil von Optimierung,

was sollte so kompliziert sein das alles zu rechtfertigen?
die Grundregel ist, sich auf einen Schleifendurchlauf zu beschränken, linearer Aufwand, konstante Arbeit pro Eintrag,

nur mit Nachfolger oder ein paar Nachbarn vergleichen, in sortierter Liste evtl. direkt möglich,
mit Map je nach Aufwand für Key eindeutiger,

einmalige Sortierung mit Aufwand n log n wäre notfalls gewiss akzeptabel dabei[/QUOTE]Okay, ich könnte das hier noch anbieten

		Collections.sort(data);
		int c = 0;
		do {
			BlmData current = data.get(c);
			Iterator<BlmData> it = data.listIterator(c + 1);
			while(it.hasNext()) {
				BlmData test = it.next();
				if(!current.equals(test) && current.isAppendable(test)) {
					current.setGueltigBis(test.getGueltigBis());
					it.remove();
				}
			}
			c++;
		} while(c < data.size());
		return data;
	}```aber ich weis beim besten willen nicht, wie du das in einer einzigen Schleife machen willst. Das "it.remove()" sorgt während der Arbarbeitung zumindest dafür, dass die Arbeit immer weniger wird.
15

nun, ich bin doch nicht ganz schweigsam,
vielleicht nicht korrekt in den Ideen, aber zumindest gebe ich sie ja zum Besten :wink:
11:48-Posting vielleicht noch nicht gesehen,

dein Code erweitert um Abbruch der inneren Schleife wenn man sehen kann dass es nix mehr wird (Beginn späterer Einträge > Ende von ‚current‘) wäre die Unbestimmtheit-Variante

Alternative z.B. etwas mit Map, soweit machbar

16

ok - das Beispiel oben war doof gewählt. Ich wollte zum Ausdruck bringen, das theoretisch Werte dazwischen liegen können, die nicht mit aggregiert werden - also das diese nicht unmittelbar hintereinander stehen müssen.
Daher glaubte ich auch, man käme und die doppelte Schleifenlösung nicht herum.
Ich versuche die Map-Lösung umzusetzen.
Vielen Dank für die Zeit & vielen Tipps :slight_smile: ich werde das Forum weiterempfehlen :slight_smile:

17

Nach welchem Key willst du bitte da eine Map sortieren? In deinem Bild sehe ich keinen Eintrag der sich dafür eignet. Vielleicht sehe ich einfach das Problem nicht, für mich sieht das ziemlich einfach aus: Sortiere den Datenbestand nach <Daten die gleich sein müssen>
Jetzt gehst du Eintrag für Eintrag durch. Du merkst dir einen Eintrag und vergleichst ihn mit dem aktuell in der Schleife bearbeiteten. Können sie zusammengeführt werden, super. Du änderst das End-Datum des merk-Eintrags. Können sie nicht zusammengeführt werden, speicherst du den merk-Eintrag in eine neue Liste und merkst dir den aktuellen Eintrag.

Das Beispiel

  1. 10.10.2013 – 15.10.2013 Montag
  2. 11.10.2013 – 20.10.2013 Dienstag
  3. 16.10.2013 – 19.10.2013 Montag
    kann hier nicht auftreten, weil du entweder 1 und 2 schon verbinden würdest (wenn der Wochentag unwichtig ist), oder sie eben so nicht stehen würden weil die Sortierung sie anders reiht (Montag immer vor Dienstag).
18

ob das geht hängt von den Regeln ab,
bisher klingt es als müsste das neue Beginn-Datum = vorheriges End-Datum + 1 Tag sein, womit man 1. + 2. nicht zusammenfassen kann, wohl aber 1. + 3.

wenn nicht nur der direkte Nachfolger zum Vergleich interessant ist, sondern potentiell der 120. folgende, dann hat man ein gewisses Problem

unter Annahmen nicht völlig verrückter Überlappungen reicht es vielleicht,
alle ‚noch offenen‘ Kandidaten zu merken, mit der Zeit zu entfernen:

  1. 10.10.2013 – 15.10.2013
  2. 11.10.2013 – 24.10.2013
  3. 16.10.2013 – 19.10.2013
  4. 22.10.2013 – 29.10.2013

Bearbeitung von 1. → Aufnahme in eine Liste X noch wichtiger Einträge
Bearbeitung von 2. → Vergleich mit allen in X, nix gefunden, selber in X aufgenommen
Bearbeitung von 3. → Vergleich mit allen in X, Verschmelzung gefunden, der neue zusammengefasste Eintrag 1#3 bleibt in X

Bearbeitung von 4. → Vergleich mit allen in X, nix gefunden,
da aber nun 22.10. erreicht ist kann 1#3 mit End-Datum 19.10. aus X gestrichten werden, 2. bleibt vorerst in X

usw.

zwar auch gewisse Doppelschleife, aber begrenzt auf hoffentlich immer nur kleine Zahl an Einträgen in X,

Datum als Key für Map macht es zu einzelnen Schritten

19

Du kannst das Datum nicht als Key nehmen (weder Beginn noch End) weil du ,wie im Bild oben ersichtlich, 6 verschiedene, nicht zusammenfassbare Einträge zum gleichen Datum haben kannst.

20

abgelegt und gesucht wird das End-Datum, alles aus dem Jahr 9999 wird gnädigerweise ausgeklammert :wink:

bei doppelten Dati hätte man als erstes fachliche Fragen, danach kann man über Details wie Map-Key nachdenken

ohne alle Regeln und Daten-Beispiele ist es aber in der Tat nicht wirklich zu beurteilen