Ich versuche mit Brüchen in Java zu arbeiten.
Ich möchte arithmetische Funktionen implementieren. Dazu benötige ich zunächst eine Möglichkeit, die Funktionen zu normalisieren. Ich weiß, dass ich 1/6 und 1/2 erst addieren kann, wenn ich einen gemeinsamen Nenner habe. Ich muss 1/6 und 3/6 hinzufügen. Ein naiver Ansatz würde mich dazu bringen, 2/12 und 6/12 hinzuzufügen und dann zu reduzieren. Wie kann ich einen gemeinsamen Nenner mit dem geringsten Leistungsverlust erreichen? Welcher Algorithmus ist dafür am besten geeignet?
Version 8 (danke an hstoerr ):
Verbesserungen umfassen:
- Die Methode equals () stimmt jetzt mit der Methode compareTo () überein
final class Fraction extends Number {
private int numerator;
private int denominator;
public Fraction(int numerator, int denominator) {
if(denominator == 0) {
throw new IllegalArgumentException("denominator is zero");
}
if(denominator < 0) {
numerator *= -1;
denominator *= -1;
}
this.numerator = numerator;
this.denominator = denominator;
}
public Fraction(int numerator) {
this.numerator = numerator;
this.denominator = 1;
}
public int getNumerator() {
return this.numerator;
}
public int getDenominator() {
return this.denominator;
}
public byte byteValue() {
return (byte) this.doubleValue();
}
public double doubleValue() {
return ((double) numerator)/((double) denominator);
}
public float floatValue() {
return (float) this.doubleValue();
}
public int intValue() {
return (int) this.doubleValue();
}
public long longValue() {
return (long) this.doubleValue();
}
public short shortValue() {
return (short) this.doubleValue();
}
public boolean equals(Fraction frac) {
return this.compareTo(frac) == 0;
}
public int compareTo(Fraction frac) {
long t = this.getNumerator() * frac.getDenominator();
long f = frac.getNumerator() * this.getDenominator();
int result = 0;
if(t>f) {
result = 1;
}
else if(f>t) {
result = -1;
}
return result;
}
}
Ich habe alle vorherigen Versionen entfernt. Mein Dank geht an:
Antworten:
Es ist einfach so, dass ich vor nicht allzu langer Zeit eine BigFraction-Klasse für Project Euler-Probleme geschrieben habe . Es behält einen BigInteger-Zähler und -Nenner bei, sodass es niemals überläuft. Aber es wird ein bisschen langsam für viele Operationen sein, von denen Sie wissen, dass sie niemals überlaufen werden. Verwenden Sie es trotzdem, wenn Sie es wollen. Ich wollte das irgendwie vorführen. :) :)
Bearbeiten : Die neueste und beste Version dieses Codes, einschließlich Unit-Tests, wird jetzt auf GitHub gehostet und ist auch über Maven Central verfügbar . Ich lasse meinen Originalcode hier, damit diese Antwort nicht nur ein Link ist ...
quelle
BigInteger
beliebig genaue Werte speichern. Wenn nicht, dannlong
, was eine einfachere Implementierung hat;Number
;Comparable<T>
;equals()
undhashCode()
;String
.toString()
; undSerializable
.In der Tat versuchen Sie dies für die Größe an. Es läuft, kann aber einige Probleme haben:
Ausgabe ist:
quelle
Apache Commons Math hat seit einiger Zeit eine Fraction- Klasse. Meistens die Antwort auf "Junge, ich wünschte, Java hätte so etwas wie X in der Kernbibliothek!" finden Sie unter dem Dach der Apache Commons-Bibliothek .
quelle
Bitte machen Sie es zu einem unveränderlichen Typ! Der Wert eines Bruchs ändert sich nicht - eine Hälfte wird beispielsweise nicht zu einem Drittel. Anstelle von setDenominator könnten Sie withDenominator verwenden, das einen neuen zurückgibt Bruch der denselben Zähler, aber den angegebenen Nenner hat.
Das Leben ist vielMit unveränderlichen Typen einfacher.
Das Überschreiben von Gleichheit und Hashcode wäre ebenfalls sinnvoll, sodass es in Karten und Mengen verwendet werden kann. Die Punkte von Outlaw Programmer zu arithmetischen Operatoren und zur Formatierung von Zeichenfolgen sind ebenfalls gut.
Schauen Sie sich als allgemeine Anleitung BigInteger und BigDecimal an. Sie machen nicht dasselbe, aber sie sind ähnlich genug, um Ihnen gute Ideen zu geben.
quelle
Zum einen würde ich die Setter loswerden und Fractions unveränderlich machen.
Sie möchten wahrscheinlich auch Methoden zum Hinzufügen, Subtrahieren usw. und möglicherweise eine Möglichkeit, die Darstellung in verschiedenen String-Formaten zu erhalten.
EDIT: Ich würde wahrscheinlich die Felder als "endgültig" markieren, um meine Absicht zu signalisieren, aber ich denke, es ist keine große Sache ...
quelle
quelle
Nicht unbedingt notwendig. (Wenn Sie mit Gleichheit richtig umgehen möchten, verlassen Sie sich nicht auf double, um richtig zu arbeiten.) Wenn b * d positiv ist, ist a / b <c / d, wenn ad <bc. Wenn es sich um negative Ganzzahlen handelt, kann dies angemessen behandelt werden ...
Ich könnte umschreiben als:
Die Verwendung von
long
hier soll sicherstellen, dass es keinen Überlauf gibt, wenn Sie zwei große multiplizierenint
s . handle Wenn Sie garantieren können, dass der Nenner immer nicht negativ ist (wenn er negativ ist, negieren Sie einfach sowohl den Zähler als auch den Nenner), müssen Sie nicht mehr prüfen, ob b * d positiv ist, und einige Schritte speichern. Ich bin mir nicht sicher, nach welchem Verhalten Sie mit einem Nenner von Null suchen.Ich bin mir nicht sicher, wie die Leistung im Vergleich zur Verwendung von Doppelwerten verglichen werden soll. (Das heißt, wenn Sie sich so sehr für die Leistung interessieren) Hier ist eine Testmethode, die ich zur Überprüfung verwendet habe. (Scheint richtig zu funktionieren.)
(ps Sie könnten eine Umstrukturierung in Betracht ziehen, um sie zu implementieren
Comparable
oderComparator
für Ihre Klasse.)quelle
Eine sehr geringfügige Verbesserung könnte möglicherweise darin bestehen, den von Ihnen berechneten doppelten Wert so zu speichern, dass Sie ihn nur beim ersten Zugriff berechnen. Dies wird kein großer Gewinn sein, wenn Sie nicht häufig auf diese Nummer zugreifen, aber es ist auch nicht allzu schwierig, dies zu tun.
Ein zusätzlicher Punkt könnte die Fehlerprüfung sein, die Sie im Nenner durchführen ... Sie ändern automatisch 0 in 1. Sie sind sich nicht sicher, ob dies für Ihre spezielle Anwendung korrekt ist, aber im Allgemeinen stimmt etwas nicht, wenn jemand versucht, durch 0 zu teilen . Ich würde dies eine Ausnahme auslösen lassen (eine spezielle Ausnahme, wenn Sie dies für erforderlich halten), anstatt den Wert auf eine scheinbar willkürliche Weise zu ändern, die dem Benutzer nicht bekannt ist.
Im Gegensatz zu einigen anderen Kommentaren zum Hinzufügen von Methoden zum Hinzufügen von Subtrahieren usw. ... da Sie nicht erwähnt haben, dass sie benötigt werden, gehe ich davon aus, dass Sie dies nicht tun. Und wenn Sie keine Bibliothek bauen, die wirklich an vielen Orten oder von anderen Menschen genutzt wird, gehen Sie mit YAGNI (Sie werden sie nicht brauchen, also sollte sie nicht da sein.)
quelle
Es gibt verschiedene Möglichkeiten, diesen oder einen beliebigen Werttyp zu verbessern:
Schauen Sie sich im Grunde die API für andere Werteklassen wie Double , Integer an und tun Sie, was sie tun :)
quelle
Wenn Sie den Zähler und den Nenner eines Bruchs mit dem Nenner des anderen multiplizieren und umgekehrt, erhalten Sie zwei Brüche (die immer noch dieselben Werte sind) mit demselben Nenner und können die Zähler direkt vergleichen. Daher müssten Sie den doppelten Wert nicht berechnen:
quelle
wie ich diesen Code verbessern würde:
quelle
Sie haben bereits eine compareTo-Funktion ... Ich würde die Comparable-Schnittstelle implementieren.
Vielleicht spielt es keine Rolle, was auch immer Sie damit machen werden.
quelle
Wenn Sie sich abenteuerlustig fühlen, schauen Sie sich JScience an . Es hat eine
Rational
Klasse, die Brüche darstellt.quelle
Ich würde sagen, wirf eine ArithmeticException für die Division durch Null, da genau das passiert:
Anstelle von "Durch Null teilen" möchten Sie möglicherweise die Meldung "Durch Null teilen: Nenner für Bruch ist Null" anzeigen.
quelle
Wenn Sie ein Bruchobjekt erstellt haben, warum sollten Sie anderen Objekten erlauben, den Zähler oder den Nenner festzulegen? Ich würde denken, dass diese nur gelesen werden sollten. Es macht das Objekt unveränderlich ...
Außerdem ... sollte das Setzen des Nenners auf Null eine ungültige Argumentausnahme auslösen (ich weiß nicht, was es in Java ist).
quelle
Timothy Budd hat eine gute Implementierung einer Rational-Klasse in seinen "Data Structures in C ++". Natürlich eine andere Sprache, aber die Portierung auf Java ist sehr gut.
Ich würde mehr Konstruktoren empfehlen. Ein Standardkonstruktor hätte den Zähler 0, den Nenner 1. Ein einzelner arg-Konstruktor würde einen Nenner von 1 annehmen. Überlegen Sie, wie Ihre Benutzer diese Klasse verwenden könnten.
Keine Prüfung auf Nenner Null? Wenn Sie vertraglich programmieren, müssen Sie es hinzufügen.
quelle
Ich werde den dritten oder fünften oder was auch immer die Empfehlung sein, Ihren Bruch unveränderlich zu machen. Ich würde auch empfehlen, dass Sie die Number- Klasse erweitern. Ich würde mir wahrscheinlich die Double- Klasse ansehen , da Sie wahrscheinlich viele der gleichen Methoden implementieren möchten.
Sie sollten wahrscheinlich auch Comparable and Serializable implementieren, da dieses Verhalten wahrscheinlich erwartet wird. Daher müssen Sie compareTo () implementieren. Sie müssen auch equals () überschreiben, und ich kann nicht stark genug betonen, dass Sie auch hashCode () überschreiben. Dies kann jedoch einer der wenigen Fälle sein, in denen compareTo () und equals () nicht konsistent sein sollen, da die auf einander reduzierbaren Brüche nicht unbedingt gleich sind.
quelle
Eine Aufräumpraxis, die ich mag, ist, nur eine Rückkehr zu haben.
quelle
Verwenden Sie die Rational-Klasse aus der JScience- Bibliothek. Es ist das Beste für die gebrochene Arithmetik, die ich in Java gesehen habe.
quelle
Ich habe Cletus 'Antwort aufgeräumt :
valueOf(String)
durch das,BigInteger(String)
das sowohl flexibler als auch schneller ist.quelle
Erste Bemerkung:
Schreiben Sie niemals Folgendes:
Das ist viel besser
Erstellen Sie einfach, um eine gute Angewohnheit zu erstellen.
Indem Sie die Klasse wie vorgeschlagen unveränderlich machen, können Sie auch das Double nutzen, um die Operationen equals und hashCode sowie compareTo auszuführen
Hier ist meine schnelle schmutzige Version:
Informationen zur statischen Factory-Methode können später hilfreich sein, wenn Sie den Bruch in Unterklassen unterteilen, um komplexere Aufgaben zu erledigen, oder wenn Sie einen Pool für die am häufigsten verwendeten Objekte verwenden.
Es kann sein, dass dies nicht der Fall ist, ich wollte nur darauf hinweisen. :) :)
Siehe Effektives erstes Java- Element.
quelle
Könnte nützlich sein, um einfache Dinge wie Hin- und Herbewegung hinzuzufügen, den Rest zu erhalten und ganz zu werden.
quelle
Obwohl Sie über die Methoden compareTo () verfügen, sollten Sie auch Comparable implementieren, wenn Sie Dienstprogramme wie Collections.sort () verwenden möchten.
Für eine hübsche Anzeige empfehle ich außerdem, toString () zu überschreiben.
Und schließlich würde ich die Klasse öffentlich machen, damit Sie sie aus verschiedenen Paketen verwenden können.
quelle
Diese Funktion zur Vereinfachung der Verwendung des Eukledian-Algorithmus ist beim Definieren von Brüchen sehr nützlich
quelle
Für die branchenübliche Fraction / Rational-Implementierung würde ich sie so implementieren, dass sie NaN, positive Unendlichkeit, negative Unendlichkeit und optional negative Null mit einer Betriebssemantik darstellen kann, die genau den IEEE 754-Standardzuständen für Gleitkomma-Arithmetik entspricht (dies erleichtert auch die Umrechnung in / von Gleitkommawerten). Da der Vergleich mit Null, Eins und den oben genannten speziellen Werten nur einen einfachen, aber kombinierten Vergleich von Zähler und Nenner mit 0 und 1 erfordert, würde ich zur Vereinfachung der Verwendung mehrere isXXX- und compareToXXX-Methoden hinzufügen (z. B. eq0 () Verwenden Sie hinter den Kulissen den Zähler == 0 && Nenner! = 0, anstatt den Client mit einer nullwertigen Instanz vergleichen zu lassen. Einige statisch vordefinierte Werte (ZERO, ONE, TWO, TEN, ONE_TENTH, NAN usw.) sind ebenfalls nützlich. da sie an mehreren Stellen als konstante Werte erscheinen. Dies ist meiner Meinung nach der beste Weg.
quelle
Klassenfraktion:
Das Hauptprogramm:
quelle