Compare to

[Amina556]

Angenommen, wir wollen eine statische compareTo-Methode für int schreiben. Ein Vorschlag für die Implementierung ist:

public static int compareTo(int a, int b) { return a - b; }
Die Methode liefert einen negativen Wert für a < b, einen positiven Wert für a > b und bei Gleichheit den Wert 0. Warum wäre eine solche Implementierung nicht korrekt? Geben Sie ein Beispiel für a und b an, bei dem die Methode versagt.

Hallo eine Frage zu der obigen Frage, warum ist die Implementierung nicht korrekt ? Oder sollte man die variablen/Datentypen außerhalb der Methode schreiben ?

 

[thecain]

Versuch es doch es doch mal selber mit sehr grossen und sehr kleinen Zahlen aus

 

[Marinek]

Oder sollte man die variablen/Datentypen außerhalb der Methode schreiben ?

Wie sehe eine solche Implementierung aus? Du musst uns ein Beispiel geben, damit wir das bewerten können.

 

[Blender3D]

Warum wäre eine solche Implementierung nicht korrekt?

Denke an die Grenzen von integer Werten. was passiert bei einem Overflow oder einem Underflow?

 

[Amina556]

Versuch es doch es doch mal selber mit sehr grossen und sehr kleinen Zahlen aus

Ja werde es mal ausprobieren danke

 

[Marinek]

Und beachte, dass die Subtraktion nicht Kummutativ ist.

 

[mihe7]

Ja werde es mal ausprobieren danke

Zum Sinn solcher Überlegungen: https://www.mathe-museum.uni-passau...tuhl/forster-heinlein/Lena/Ariane5_Poster.pdf

 

[M.L.]

Weiterhin könnte man auch Gleitkommazahlen (statt int) zur Subtraktion verwenden: https://de.wikipedia.org/wiki/Auslöschung_(numerische_Mathematik)

 

[thecain]

Weiterhin könnte man auch Gleitkommazahlen (statt int) zur Subtraktion verwenden: https://de.wikipedia.org/wiki/Auslöschung_(numerische_Mathematik)

Wieso sollte man das in dem Fall hier tun? Bei int.

 

[KonradN]

Wieso sollte man das in dem Fall hier tun? Bei int.

Das würde das Problem des Überlaufs lösen. double hat 8 Bytes, 1 Vorzeichen, 11 Exponent 52 bits für die Mantisse. Daher verliert man keine Genauigkeit und die Berechnung kann in keinen Überlauf kommen.

Aber wenn anderer Datentyp, dann würde ich auf long setzen um das Problem des Überlaufs zu verhindern. Aber das ist eine Lösung, die ich nicht wirklich in Betracht ziehen würde - auch wenn es funktionieren würde.

 

[Blender3D]

Aber wenn anderer Datentyp, dann würde ich auf long setzen um das Problem des Überlaufs zu verhindern. Aber das ist eine Lösung, die ich nicht wirklich in Betracht ziehen würde - auch wenn es funktionieren würde.

Das verhindert den Überlauf aber nicht sondern verschiebt ihn nur.

System.out.println(Long.MIN_VALUE-1);

 

[KonradN]

Das verhindert den Überlauf aber nicht sondern verschiebt ihn nur.

System.out.println(Long.MIN_VALUE-1);

Der Überlauf wird verhindert, da wir ja nur Werte des int Bereiches vergleichen:

public static int compareTo(int a, int b) {
    return (int) ( (long) a - (long) b );
}

Du hast maximal 2* Integer.MAX_Value bzw 2* Integer.MIN_Value als Resultat. Da int 32 Bit hat, reichen also die 52 Bit der Mantisse von double bzw. die 64 Bit von long zur Darstellung aller möglichen Operationen.

Aber diese Lösung ist dennoch falsch (was ich leider komplett übersehen habe!) - denn bei dem Cast von long -> int werden die Bits einfach abgeschnitten. Und das Vorzeichen ist natürlich relevant!

Also bei einem Vergleich von Integer.MAX_VALUE (2147483647) mit Integer.MIN_Value (-2147483648) hat man als Ergebnis -2147483648:
System.out.println("int: " + ( (int)-4294967295L ) + " long: " + -4294967295L);
Liefert beim int halt leider eine 1

Daher ist es halt existenziell, dass man double verwendet und nicht long. Da gibt es diese Problematik nicht und das Vorzeichen wird korrekt behandelt:

import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;

import static org.junit.jupiter.api.Assertions.assertTrue;

public class CompareTests {

    public static int compareTo(int a, int b) {
        return (int) ( (double) a - (double) b );
    }

    public boolean compareResults(int result1, int result2) {
        return (result1 == 0 && result2 == 0) ||
                (result1 < 0 && result2 < 0) ||
                (result1 > 0 && result2 > 0);
    }
    @ParameterizedTest
    @CsvSource ({
            "2147483647, -2147483648",
            "2147483647, -2147483647",
            "-2147483648, 2147483647"
    })
    public void testCompareTo(int a, int b) {
        int correctResult = Integer.compare(a, b);
        int calcResult = compareTo(a, b);
        System.out.println("(" + a + " , " + b + ") = " + calcResult + " (" + correctResult + ")" );
        assertTrue(compareResults(correctResult, calcResult));
    }
}

Sieht zumindest erst einmal sehr gut aus.

Aber aufpassen, dass man nicht float nimmt - da reicht die Genauigkeit leider nicht aus, d.h. nach dem Cast gäbe es keine Unterscheidung von z.B. 2147483647 zu 2147483646 so dass hier das falsche Ergebnis 0 heraus kommen würde. Also Anzahl der Bits der Mantisse ist wichtig, so dass alle Werte unterschieden werden können:
System.out.println((int) ((float)2147483646)); gibt 2147483647 aus.

 

[mihe7]

Statt double könnte man auch Math.signum verwenden, allerdings frage ich mich, warum nicht einfach

return a == b ? 0 : (a < b ? -1 : 1);

 

[Marinek]

Statt double könnte man auch Math.signum verwenden, allerdings frage ich mich, warum nicht einfach

return a == b ? 0 : (a < b ? -1 : 1);

Ich würde schon sagen, dass das eine korrekte Lösung ist

Aber das war ja vermutlich, aus didaktischer Sicht, gerade das Ziel dies selbst zu erarbeiten an einem einfachen Beispiel.

Manchmal ist die erste Lösung nun mal nicht immer die perfekte Lösung. Und man muss den konformation bias selbstständig vermeiden können.

 

[KonradN]

Mich würde da mal die Praxis interessieren. Was wird denn da bei euch an Code geschrieben?

Also wenn wirklich nur eine int Property verglichen werden muss, dann ist es doch einfach ein Integer.compare Aufruf, also wenn ich ein Feld age habe, dann wäre es einfach etwas wie:

public class SomethingWithAge {
    private int age;
    
    public int compareTo(SomethingWithAge other) {
        return Integer.compare(age, other.age);
    }
}

um es mal einfach zu skizzieren.

Und wenn ich mehrere Felder / Properties habe? Schreibt da wirklich noch jemand Code wie:

public int compareTo(MyEntity other) {
    int result = Integer.compare(age, other.age);
    if (result != 0) return result;
    
    result = .....;
    if (result != 0) return result;
    
    // ...
    
    return Integer.compare(lastField, other.lastField);
}

Oder habt ihr da auch etwas wie:

package de.kneitzel;

import org.jetbrains.annotations.NotNull;

import java.util.Comparator;

public class MyEntity implements Comparable<MyEntity> {
    private String name;
    private int age;
    private String city;
    
    private final Comparator<MyEntity> naturalOrderComparator = Comparator
            .comparing(MyEntity::getName)
            .thenComparingInt(MyEntity::getAge)
            .thenComparing(MyEntity::getCity);

    // Getter, Constructor, ....

    @Override
    public int compareTo(@NotNull MyEntity o) {
        return naturalOrderComparator.compare(this, o);
    }
}

Ich frage nur, weil sich das für mich richtig anfühlt und es ist gut lesbar. Man kann dann noch überlegen, so ggf. mehrere Comparator Konstanten bereit zu stellen - falls das im Rahmen der Entity Sinn macht. (Sprich public static final NATURAL_ORDER_COMPARATOR = ... und dann evtl. noch sowas wie ORDER_BY_CITY_COMPARATOR und ORDER_BY_AGE_COMPARATOR )

Aber ich finde das eigentlich nirgends groß im Web. Ich habe da nicht zu viel recherchiert, aber die kurzen Suchen, die ich hatte, da findet man dann Treffer wie: Guide to Implementing the compareTo Method | Baeldung
Da wird dann Comparator zwar auch etwas erwähnt, aber das ist dann separat und auf doch recht deutlich abgeteilt zu der compareTo Methode.

 

[LimDul]

Ich nutze zu 80% Comparator.comparing

Einen expliziten Comparator baue ich nur dann, wenn es eine sehr fachliche und komplexe Sortierung ist, die nicht einfach irgendwelche Propertys der Reihe nach abfragt.

 

[KonradN]

Sprich du erzeugst bei jedem compareTo Aufruf den Comparator?

Sind das nicht viele Instanzen die bei Kopiervorgängen erzeugt werden?

 

[LimDul]

Achso, nein - wenn die compareTo Methode implementiert wird, ist der Comparator in der Regel ein Feld der Klasse (oder sogar static).

ich hab nur sehr oft hier den Fall, dass ich Objekte sortiere, die nicht comparable implementieren. Also oft folgenden Code

objekt.getListe().stream().sorted(Comparator.comparing(SubObject::getParameter)).collect(Collectors.toList());

Gerne mal mit Filtern und/oder map-Methoden ergänzt

 

[Neumi5694]

Ich würde schon sagen, dass das eine korrekte Lösung ist

Aber das war ja vermutlich, aus didaktischer Sicht, gerade das Ziel dies selbst zu erarbeiten an einem einfachen Beispiel.

Manchmal ist die erste Lösung nun mal nicht immer die perfekte Lösung. Und man muss den konformation bias selbstständig vermeiden können.

Richtig, bei der Aufgabe scheint es ja nicht darum zu gehen, eine funktionierende Lösung zu finden, sondern um zu erkennen, warum die andere Lösung falsche Ergebnisse liefern kann.

 

[Blender3D]

Statt double könnte man auch Math.signum verwenden, allerdings frage ich mich, warum nicht einfach

Das ist auch die klassische und richtige Lösung.

 

[httpdigest]

Das ist auch die klassische und richtige Lösung.

Definiere "klassisch" hier. Selbst das JDK nutzt dieselbe Lösung wie die von @mihe7 (nur, dass sie zuerst auf < vergleichen).
Und das ist auch die mit Abstand performanteste Lösung hier.
Es wurde zwar nie konkret gesagt, wie eine Lösung mit "Math.signum" konkret aussehen sollte, aber eine Lösung wie etwa:

public static int compareTo(int a, int b) {
  return (int) Math.signum((double) a - (double) b);
}

ist hier leider nur halb so schnell, hauptsächlich wegen der ganzen Casts/Conversions und dem NaN/Not-a-Number Handling, die alle Fließkommaoperationen immer machen müssen.

 

[mihe7]

Die Übung taugt hervorragend als Beispiel für:

1. Premature optimization is the root of all evil.
2. KISS
3. Aussagekraft zyklomatischer Komplexität.

ad 1) es erscheint zunächst sehr elegant a - b zu rechnen. Tatsächlich tappt man hier in eine Falle.

ad 2) worum gehts? Es sollen zwei Zahlen verglichen werden. Ja, warum dann nicht einfach zwei Zahlen miteinander vergleichen?

ad 3) Die zyklomatische Komplexität der Rechnerei liegt bei 1, die der Fallunterscheidung dürfte bei 3 liegen. Ist das nun aber wirklich schwerer zu verstehen? Sicher, der Code ist aufgrund der Fallunterscheidung komplexer, allerdings hat man die in jedem Fall, nur ggf. versteckt. Die Anweisung a - b ist leicht zu verstehen aber ich muss ja nach wie vor nachvollziehen, in welchem Fall a - b < 0 gilt und was in welchem Fall zurückzugeben ist. So gesehen ist a - b fast noch schwerer zu greifen als die Fallunterscheidung. Noch witziger wird es, wenn der Vergleich negiert wird (z. B. für absteigendes Sortieren). "Ah, b - a, ah ja, was war b? Ach der zweite Parameter, gut und was ist b - a, gut wird kleiner 0, wenn a > b gilt. Dann gebe ich also -1 zurück. Moment, das ist doch dann b < a, äh, ne b > a, äh, a < b, ach, irgendsowas halt." Gut, etwas übertrieben aber im Prinzip läuft es doch so ähnlich.

Noch was (um auf die Frage von @KonradN einzugehen) : ich habe früher tatsächlich auch per a - b "verglichen", das ist einfach Blindheit durch Routine und in meinen Fällen war das auch kein Problem, weil der Wertebereich völlig ausreichend war. Andererseits hätte man sich natürlich auch mal fragen können, ob es eigentlich sinnvoll ist, zum 300.000-ten Mal den gleichen Mist zu implementieren

Jedenfalls verwende ich mittlerweile eigentlich ausschließlich Integer.compare (bzw. Comparator.comparingInt, falls es ein Comparator werden soll). Erstens ist der Spaß vorhanden und damit als korrekt anzunehmen, zweitens ist das lesbarer. Und nur, damit hier niemand auf dumme Gedanken kommt: für einfache Vergleiche verwende ich natürlich die Vergleichsoperatoren...

 

[KonradN]

Definiere "klassisch" hier. Selbst das JDK nutzt dieselbe Lösung wie die von @mihe7 (nur, dass sie zuerst auf < vergleichen).

Ich denke, das ist, was die Aussage auch meinte. Ich hatte @Blender3D auch genau so verstanden.

(um auf die Frage von @KonradN einzugehen)

Oh, ich hoffe da ist jetzt nicht verstanden worden, dass ich diese Form der Berechnung als irgendwie sinnvoll ansehen würde. Ich denke wir alle sind und hier doch extrem einig, dass wir keine Berechnung machen wollen sondern eben Vergleichen oder einfach die Methoden aufrufen, die es dazu gibt (wie z.B. Integer.compare).

Jedenfalls verwende ich mittlerweile eigentlich ausschließlich Integer.compare (bzw. Comparator.comparingInt, falls es ein Comparator werden soll).

Ja, wobei meine Frage von mir mehr war, wie Du das Comparable implementierst. Denn man hat ja extrem oft, dass man etwas nach mehreren Kriterien sortieren muss. Also erst nach Nachname, dann nach Vorname und dann nach Stadt oder so .... Und da fand ich die Comparator Schreibweise extrem gut und hilfreich: Sehr kurz und prägnant und dabei extrem gut lesbar. Daher halt die Erstellung eines Comparators nur um die compareTo Methode zu schreiben.

 

[mihe7]

Oh, ich hoffe da ist jetzt nicht verstanden worden, dass ich diese Form der Berechnung als irgendwie sinnvoll ansehen würde.

Ne, davon wäre ich jetzt auch nicht ausgegangen

wie Du das Comparable implementierst

Also erst nach Nachname, dann nach Vorname und dann nach Stadt oder so ....

Via Comparator.comparing...