Erstellen eines HashSet für Doubles

Question

ich eine HashSet für reelle Zahlen erstellen möchten (derzeit Double s) eine definierte Toleranz mit (epsilon), (cf Assert.assertEquals(double, double, double)
Da nur mit Double.equals() zur exakten Gleichheit funktioniert und Double ist eine endgültige Klasse Ich kann es nicht verwenden Meine ursprüngliche Idee ist es, HashSet (zB DoubleHashSet) mit einer setEpsilon(double) Methode zu erweitern und eine neue Klasse ComparableDouble zu erstellen, wobei equals() diesen Wert von DoubleHashSet verwendet.Aber ich möchte überprüfen, ob es bestehende Lösungen gibt bereits vorhandene und vorhandene F/OSS-Bibliotheken

(In th Die Zukunft möchte ich auf Tupel reeller Zahlen ausdehnen - z. Rechtecke und Würfel - so ein allgemeiner Ansatz ist vorzuziehen

HINWEIS: @ NPE hat vorgeschlagen, dass es unmöglich ist. Leider vermute ich das formell richtig ist :-) Also ich frage mich ob es approximative Methoden gibt ... Andere müssen dieses Problem gehabt haben und es ungefähr gelöst haben. (Ich benutze bereits regelmäßig ein Werkzeug Real.isEqual(a, b, epsilon) und es ist sehr nützlich.) Ich bin bereit, einige seltene Fehler der Transitivität zu akzeptieren.

HINWEIS: Ich verwende ein TreeSet als das löst das Problem von "fast gleich()". Später werde ich komplexe Zahlen, Rechtecke (und komplexere Objekte) vergleichen und es ist wirklich nützlich, ein Limit zu setzen, innerhalb dessen 2 Dinge gleich sind. Es gibt keine einfache natürliche Reihenfolge von complexNumbers (vielleicht würde ein Cantor-Ansatz funktionieren), aber wir können sagen, ob sie nahezu gleich sind.

Answer 1

Es gibt einige grundlegende Fehler in diesem Ansatz.

HashSet verwendet equals(), um zwei Elemente auf Gleichheit zu überprüfen. The contract on equals() has the following among its requirements:

Es ist transitiv: für alle Nicht-Null-Referenzwerte x, y und z, wenn x.equals(y) kehrt true und y.equals(z) kehrt true, dann sollte x.equals(z)true zurück.

Betrachten wir nun das folgende Beispiel:

x = 0.0 
y = 0.9 * epsilon 
z = 1.8 * epsilon 

Es ist klar, dass von Ihnen vorgeschlagenen Vergleichsschema der Transitivität Anforderung brechen würde (x gleich y und y gleich z, doch x nicht gleich z). Unter diesen Umständen kann HashSet nicht richtig funktionieren.

Darüber hinaus wird hashCode() zusätzliche Herausforderungen produzieren, aufgrund der folgenden requirement:

Wenn zwei Objekte gleich sind nach dem equals(Object) Verfahren, dann auf jeder der beiden Objekte die hashCode Methode aufrufen müssen die gleiche produzieren ganzzahliges Ergebnis

Die hashCode() Anforderung kann durch die Verwendung eines TreeSet statt HashSet ausgewichen werden.

Answer 2

Was würde ich tun, um das Doppel ist sie vor der Anwendung (vorausgesetzt, dies angemessen ist)

z.B.

public static double roundByFactor(double d, long factor) { 
    return (double) Math.round(d * factor)/factor; 
} 

TDoubleHashSet set = new TDoubleHashSet(); // more efficient than HashSet<Double> 
set.add(roundByFactor(1.001, 100)); 
set.add(roundByFactor(1.005, 100)); 
set.add(roundByFactor(1.01, 100)); 
// set has two elements. 

Sie können dieses Verhalten in Ihr eigenes DoubleHashSet einbinden. Wenn Sie den ursprünglichen Wert reservieren möchten, können Sie HashMap oder TDoubleDoubleHashMap verwenden, wobei der Schlüssel der gerundete Wert und der Wert das Original ist.

Answer 3

I @ NPE Ansatz umgesetzt haben (ich habe seine/ihre Antwort akzeptiert, so er/sie die Punkte bekommt :-) und geben hier den Code

//Create a comparator: 
public class RealComparator implements Comparator<Double> { 

    private double epsilon = 0.0d; 

    public RealComparator(double eps) { 
     this.setEpsilon(eps); 
    } 

    /** 
    * if Math.abs(d0-d1) <= epsilon 
    * return -1 if either arg is null 
    */ 
    public int compare(Double d0, Double d1) { 
     if (d0 == null || d1 == null) { 
      return -1; 
     } 
     double delta = Math.abs(d0 - d1); 
     if (delta <= epsilon) { 
      return 0; 
     } 
     return (d0 < d1) ? -1 : 1; 
    } 

    /** set the tolerance 
    * negative values are converted to positive 
    * @param epsilon 
    */ 
    public void setEpsilon(double epsilon) { 
     this.epsilon = Math.abs(epsilon); 
    } 

und testen Sie es

public final static Double ONE = 1.0; 
public final static Double THREE = 3.0; 

@Test 
public void testTreeSet(){ 
    RealComparator comparator = new RealComparator(0.0); 
    Set<Double> set = new TreeSet<Double>(comparator); 
    set.add(ONE); 
    set.add(ONE); 
    set.add(THREE); 
    Assert.assertEquals(2, set.size()); 
} 
@Test 
public void testTreeSet1(){ 
    RealComparator comparator = new RealComparator(0.0); 
    Set<Double> set = new TreeSet<Double>(comparator); 
    set.add(ONE); 
    set.add(ONE-0.001); 
    set.add(THREE); 
    Assert.assertEquals(3, set.size()); 
} 
@Test 
public void testTreeSet2(){ 
    RealComparator comparator = new RealComparator(0.01); 
    Set<Double> set = new TreeSet<Double>(comparator); 
    set.add(ONE); 
    set.add(ONE - 0.001); 
    set.add(THREE); 
    Assert.assertEquals(2, set.size()); 
} 
@Test 
public void testTreeSet3(){ 
    RealComparator comparator = new RealComparator(0.01); 
    Set<Double> set = new TreeSet<Double>(comparator); 
    set.add(ONE - 0.001); 
    set.add(ONE); 
    set.add(THREE); 
    Assert.assertEquals(2, set.size()); 
}