Java Punkte aus Punktwolken entfernen sehr langsam

[clustered]

Hallo,

es geht darum, Punkte aus Punktwolken (Clustern) zu entfernen, wobei in jeder Wolke (Cluster) jeweils ein Punkt bleiben soll - was aufgrund der vielen verschachtelten Schleifen aber manchmal bis zu 5 Sekunden dauert...

Gibt es viell eine Möglichkeit, den Algo zu optimieren?

Vielen Dank für jeden Hinweis.

Konkret in Verdacht habe ich die TreeMap und den wiederholten MergedClusters-Aufruf:

  private static boolean removePointsFromDatabase(TreeMap<Point2D, Info> mergedClusters) {
    if (mergedClusters.size() <= maxClusteredPoints1) {
      return false;
    }

    // Start points removal logic
    int mergedSize = mergedClusters.size();
    TreeMap<Integer, LinkedList<Map.Entry<Point2D, Info>>> ranking =
        new TreeMap<>(Comparator.reverseOrder());
    for (Map.Entry<Point2D, Info> entry : mergedClusters.entrySet()) {
      int neighboursCount = getNeighboursCount(mergedClusters, entry.getKey());
      ranking.putIfAbsent(neighboursCount, new LinkedList<>());
      ranking.get(neighboursCount).add(entry);
    }
    a:
    for (Map.Entry<Integer, LinkedList<Map.Entry<Point2D, Info>>> entry1 : ranking.entrySet()) {
      for (Map.Entry<Point2D, Info> entry2 : entry1.getValue()) {
        TreeMap<Double, LinkedList<String>> ranking2 = new TreeMap<>();
        for (Map.Entry<String, Info> entry3 : database.entrySet()) {
          double d = distanceInKm(entry2.getKey(), entry3.getValue().getPoint());
          if (d < minDistanceForClustering2) {
            ranking2.putIfAbsent(d, new LinkedList<>());
            ranking2.get(d).add(entry3.getKey());
          }
        }
        if (ranking2.size() >= 2) {
          ranking2.values().stream().skip(1).forEach(entry4 -> entry4.forEach(database::remove));
          mergedSize = getMergedClusters().size();
          if (mergedSize <= maxClusteredPoints2) {
            break a;
          }
        }
      }
    }

    int originalSize = database.size();
    int diffSize = originalSize - mergedSize;
    System.out.println("originalSize = " + originalSize);
    System.out.println("mergedSize = " + mergedSize);
    System.out.println("diffSize = " + diffSize);

    return true;
  }

 

[BeBur]

Die Variablenbenennung ist nicht so geil. entry1, entry2, entry3? Paar erklärende Kommentare und/oder Einführung von Funktionen würde die Lesbarkeit ebenfalls deutlich verbessern.

Du könntest im ersten Durchlauf clustern und im zweiten Durchlauf den Schwerpunkt der Cluster berechnen und den zum Schwerpunkt an nächsten liegenden Punkt behalten und den Rest entfernen.

Konkret in Verdacht habe ich die TreeMap und den wiederholten MergedClusters-Aufruf:

Es gibt profiling tools, die zeigen dir flame graphs u.ä. an, also wo wie viel Zeit aufgewendet wurde.

 

[dms]

Mhhhh .. das erinnert schon stark einen eine bestimmten (ex)Nutzer

 

[clustered]

Du könntest im ersten Durchlauf clustern und im zweiten Durchlauf den Schwerpunkt der Cluster berechnen und den zum Schwerpunkt an nächsten liegenden Punkt behalten und den Rest entfernen.

Mache ich schon, aber leider, wie beschrieben, (sehr) ineffizient.

Der Aufruf getMergedClusters().size() dient nur zum Prüfen, ob das Declustering fertig ist. Tatsächlich kann ich nicht vorhersagen, wie viele konkrete Punkte in einer Iteration entfernt werden. ... Oder ich bräuchte zusätzliche Variablen und müsste die innere Schleife "sprengen".

 

[Krik]

Du schachtelst drei Schleifen (entry1...3). Das ist nun mal sehr teuer.

Du könntest möglicherweise noch einiges an Geschwindigkeit herausholen, wenn du HashMaps statt TreeMaps verwendest.

 

[clustered]

Mhhhh .. das erinnert schon stark einen eine bestimmten (ex)Nutzer

Werde eh gleich wieder wegen irgendeiner fingierten Begründung gesperrt werden... Aber danke für eure Bemühungen.

 

[rezzler]

Werde eh gleich wieder wegen irgendeiner fingierten Begründung gesperrt werden...

Wenn man nach zahllosen Verstößen und Neuanmeldungen die Regeln immer noch nicht verstanden hat…