Map-Comparator reversed

[grrr]

Ich weiß leider nicht, warum folgendes alles nicht funktioniert:

TreeMap<Map.Entry<Point2D, Info>, Double> distancesFromMostNeighbors = new TreeMap<>(Map.Entry.<Map.Entry<Point2D, Info>, Double>comparingByValue().reversed());

-> no instance(s) of type variable(s) exist so that Entry<Point2D, Info> conforms to Entry<Entry<Point2D, Info>, Double>

TreeMap<Map.Entry<Point2D, Info>, Double> distancesFromMostNeighbors = new TreeMap<>((Comparator) Map.Entry.<Map.Entry<Point2D, Info>, Double>comparingByValue().reversed());

-> Raw use of parameterized class 'Comparator'
-> Unchecked call to 'TreeMap(Comparator<? super K>)' as a member of raw type 'java.util.TreeMap'

Hat jemand vielleicht eine Idee?

 

[KonradN]

Also eine Treemap sortiert nach den Keys und erwartet daher auch einen Comparator für die Keys:
TreeMap(Comparator<? super K> comparator)

Das Map.Entity compareByValue liefert aber:
static <K,V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue()

Du brauchst also ein Comparator<? super MapEntry<Point2D, Info>> aber du gibst ihm ein
Comparator<Map.Entry<MapEntry<Point2D, Info>, Double>

Und das passt natürlich nicht. Und so so ein genereller Fehler ist natürlich durch irgend einen Cast nicht zu beseitigen.

 

[grrr]

Also eine Treemap sortiert nach den Keys und erwartet daher auch einen Comparator für die Keys

Stimmt. Hatte nicht nachgedacht...

So geht es jetzt aber:

  TreeSet<Map.Entry<Map.Entry<Point2D, Info>, Double>> distancesFromMostNeighbors = new TreeSet<>((o1, o2) -> Double.compare(o2.getValue(), o1.getValue()));
  for (Map.Entry<Point2D, Info> entry : tempClusters.entrySet()) {
    double distance = distanceBetween(mostNeighborsEntry.getKey(), entry.getKey());
    distancesFromMostNeighbors.add(new AbstractMap.SimpleEntry<>(entry, distance));
  }

 

[Oneixee5]

Ich denke hier liegt ein grundsätzliches Missverständnis vor, wie TreeSet funktioniert. Ein TreeSet nutzt den Comparator, um Gleichheit festzustellen, nicht .equals()

Zu: distanceBetween

Stell dir vor, du berechnest Abstände von einem Mittelpunkt (0,0):

• Punkt A liegt bei (3, 4). Abstand ist 5,0.
• Punkt B liegt bei (5, 0). Abstand ist auch 5,0.

Obwohl Punkt A und Punkt B an völlig unterschiedlichen Positionen liegen, sagt dein aktueller Comparator: Double.compare(5.0, 5.0) ergibt 0.
Das Ergebnis: Das TreeSet wirft Punkt B weg, weil es denkt, er sei "gleich" wie Punkt A.

Rechnung Abstand für Punkt A (3, 4) - euklidischen Distanz, Satz des Pythagoras:

Hier die x-Achse (Länge 3) und die y-Achse (Länge 4) sind die beiden kurzen Seiten eines Dreiecks.
Quadriere: 3^2 = 9 und 4^2 = 16
Addiere: 9 + 16 = 25
Zieh die Wurzel: sqrt(25) = 5,0
Das ist das klassische "3-4-5-Dreieck", das man in der Schule als erstes Beispiel für Pythagoras lernt.

Rechnung für Punkt B (5, 0)
Dieser Punkt liegt auf der x-Achse. Wenn wir die Formel trotzdem anwenden:
Quadriere: 5^2 = 25 und 0^2 = 0
Addiere: 25 + 0 = 25
Zieh die Wurzel: sqrt(25) = 5,0

Ich denke das erfüllt den Zweck, ist etwas lesbarer und wird auch morgen noch verstanden.

record NeighborDistance(Point2D point, Info info, double distance) {}

List<NeighborDistance> sortedDistances = tempClusters.entrySet().stream()
    .map(entry -> new NeighborDistance(
        entry.getKey(),
        entry.getValue(),
        distanceBetween(mostNeighborsEntry.getKey(), entry.getKey())
    ))
    .sorted(Comparator.comparingDouble(NeighborDistance::distance).reversed())
    .toList();

 

[grrr]

Nabend. Ich verstehe, was du meinst...

Stell dir vor, du berechnest Abstände von einem Mittelpunkt (0,0):

• Punkt A liegt bei (3, 4). Abstand ist 5,0.
• Punkt B liegt bei (5, 0). Abstand ist auch 5,0.

Obwohl Punkt A und Punkt B an völlig unterschiedlichen Positionen liegen, sagt dein aktueller Comparator: Double.compare(5.0, 5.0) ergibt 0.
Das Ergebnis: Das TreeSet wirft Punkt B weg, weil es denkt, er sei "gleich" wie Punkt A.

Punkt A würde weggeworfen werden, da dieser eher in der Menge war...

Es geht um Latitude und Longitude, also Koordinaten auf einer Sphäre. Jede Koordinate ist einzigartig, aber dennoch kann das von dir beschriebene Verhalten natürlich auftreten, das zwei Koordinaten genau den gleichen Abstand zu einem dritten Punkt (fest) haben.

Aber dieser Fall wäre sehr unwahrscheinlich.

Meine bisherige Logik ist:

    while (true) {
      TreeMap<Point2D, Info> clusters = getMergedClusters(database);
      if (clusters.size() <= maxClusteredPoints) {
        break;
      }
      TreeMap<Point2D, Integer> neighborsCount = new TreeMap<>(pointComparator);
      for (Map.Entry<Point2D, Info> entry : clusters.entrySet()) {
        int neighborCount = 0;
        for (Map.Entry<Point2D, Info> entry2 : clusters.entrySet()) {
          if (entry == entry2) {
            continue;
          }
          if (distanceInKm(entry.getKey(), entry2.getKey()) < minDistanceForClustering) {
            neighborCount++;
          }
        }
        neighborsCount.put(entry.getKey(), neighborCount);
      }
      Map.Entry<Point2D, Info> mostNeighborsEntry = null;
      int maxNeighbors = -1;
      for (Map.Entry<Point2D, Integer> entry : neighborsCount.entrySet()) {
        if (entry.getValue() > maxNeighbors) {
          maxNeighbors = entry.getValue();
          Point2D key = entry.getKey();
          Info value = clusters.get(key);
          mostNeighborsEntry = new AbstractMap.SimpleEntry<>(key, value);
        }
      }
      if (mostNeighborsEntry == null) {
        throw new IllegalStateException("Point with most neighbors not found.");
      }
      TreeSet<Map.Entry<Map.Entry<Point2D, Info>, Double>> distancesFromMostNeighbors =
          new TreeSet<>((o1, o2) -> Double.compare(o2.getValue(), o1.getValue()));
      for (Map.Entry<Point2D, Info> entry : clusters.entrySet()) {
        if (entry.getKey().equals(mostNeighborsEntry.getKey())) {
          continue;
        }
        double distance = distanceInKm(mostNeighborsEntry.getKey(), entry.getKey());
        if (distance < minDistanceForClustering) {
          distancesFromMostNeighbors.add(new AbstractMap.SimpleEntry<>(entry, distance));
        }
      }
      while (true) {
        Map.Entry<Map.Entry<Point2D, Info>, Double> entry = distancesFromMostNeighbors.pollFirst();
        if (entry == null) {
          throw new IllegalStateException("No more points to remove, but still over limit.");
        }
        int removedCount = removeInfoFromDatabase(entry.getKey().getValue());
        if (removedCount > 0) {
          break;
        }
      }
    }

Es geht darum, einen Punkt zu entfernen, der am weitesten vom Zentrum des größten Clusters entfernt ist. Dabei spielt es aber keine Rolle, ob es 1, 2 oder n solcher Punkte gibt.

Btw die Abstände auf einer Kugel müssen wegen der Krümmung anders berechnen werden (3D), Pythagoras berechnet ja nur die direkte Verbindung:

  static double distanceInKm(Point2D p1, Point2D p2) {
    double lon1 = p1.getX(), lat1 = p1.getY(), lon2 = p2.getX(), lat2 = p2.getY();
    final int R = 6371; // Radius of the earth in km
    double latDistance = Math.toRadians(lat2 - lat1);
    double lonDistance = Math.toRadians(lon2 - lon1);
    double a =
        Math.sin(latDistance / 2) * Math.sin(latDistance / 2)
            + Math.cos(Math.toRadians(lat1))
                * Math.cos(Math.toRadians(lat2))
                * Math.sin(lonDistance / 2)
                * Math.sin(lonDistance / 2);
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    return R * c; // convert to kilometers
  }

 

[grrr]

Vielleicht noch als Ergänzung, ich hatte die Aufteilung in Methoden vergessen, und ggf. kann es auch bei einer Map bleiben, wenn man die Keys und Values vertauscht, also die Distanzen als Schlüssel wählt.

 

[KonradN]

Deine Herangehensweise finde ich immer sehr irritierend ...
a) Aufteilung in Methoden: Das ist etwas, das ich Dir von Anfang an sehr ans Herz legen würde ... dann rennst Du auch nicht in so dubiose Ansätze a.la. zwei verschachtelte Schleifen die so absolut keinen Sinn machen ...
b) Wie wählst Du Maps? Wenn da einfach so Keys und Values getauscht werden, dann wird da vermutlich keinerlei wirkliche Notwendigkeit für eine Map vorgelegen haben (die den Zugriff per key ja als Schlüsselmerkmal hat). Hier auch der Tipp, hier ggf. erst mit kleinen Basis-Typen anzufangen. Mein Gefühl ist, dass Du einfach ein Tupel an Daten hattest und Du da dann halt Map.Entry dafür gewählt hast. Und dann darauf Aufbauend so Konstrukte wie Map.Entry<Map.Entry<...>...> Da wäre einfach die Fragestellung: Findest Du dies wirklich gut lesbar?

Ich neige da zu Ansätzen wie eine List oder Set mit einem eigenen Typ, intern verwaltet in einer Klasse und so möglichst gut gekapselt. Da hat man dann im nu einen Code und da kann man dann Zugriffe ggf. weiter optimieren.

Aber egal - ich will das nicht weiter vertiefen. Es ist toll, dass Du für Dich eine Lösung gefunden hast und mit Deinem Code soweit zufrieden bist.

 

[grrr]

dann rennst Du auch nicht in so dubiose Ansätze a.la. zwei verschachtelte Schleifen die so absolut keinen Sinn machen ...

Allerdings, diese machen sinn, nur sollte man durch Methoden break und continue vermeiden...

Aber du hast den Punkt, dass es eine eigene Tupel-Klasse als Kapselung braucht.