Tworzenie HashSet dla Doubles

Question

pragnę stworzyć HashSet dla liczb rzeczywistych (obecnie Double s) stosując określoną tolerancję (epsilon), (cf Assert.assertEquals(double, double, double)
Ponieważ korzystanie Double.equals() działa tylko na dokładnym równości i Double jest ostateczna klasa Moim początkowym pomysłem jest rozszerzenie HashSet (np. Do DoubleHashSet) przy użyciu metody setEpsilon(double) i utworzenie nowej klasy ComparableDouble, gdzie equals() używa tej wartości z DoubleHashSet. Chciałbym jednak sprawdzić, czy istnieją istniejące rozwiązania już istniejące biblioteki F/OSS:

(W W przyszłości będę chciał rozszerzyć to na krotki liczb rzeczywistych - np. prostokąty i sześciany - dlatego preferowane jest podejście ogólne

UWAGA: @NPE zasugerowało, że jest to niemożliwe. Niestety podejrzewam, że jest to formalnie poprawne :-) Więc zastanawiam się, czy istnieją przybliżone metody ... Inni musieli mieć ten problem i rozwiązać go w przybliżeniu. (Używam już regularnie narzędzia Real.isEqual(a, b, epsilon) i jest bardzo użyteczne.) Jestem gotów zaakceptować kilka rzadkich błędów przechodniości.

UWAGA: Będę używał zestawu drzewiastego, ponieważ rozwiązuje to problem "prawie równy()". Później będę porównywał złożone liczby, prostokąty (i bardziej złożone obiekty) i naprawdę warto jest ustawić limit, w którym 2 rzeczy są równe. Nie ma prostego naturalnego uporządkowania złożonych liczb (może działałoby podejście Cantora), ale możemy stwierdzić, czy są one prawie równe.

Answer 1

Istnieje kilka podstawowych wad tego podejścia.

HashSet używa equals(), aby sprawdzić dwa elementy równości. The contract on equals() has the following among its requirements:

jest przechodni: za nie zerowych wartości odniesienia x, y i z jeśli x.equals(y) powraca true i y.equals(z) powraca true, następnie x.equals(z) powinna powrócić true.

Teraz rozważmy następujący przykład:

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

Jest oczywiste, że Twój proponowany system porównanie złamie warunek przechodniości (x równa y i y równa z jeszcze x nie równa z). W takich okolicznościach HashSet nie może działać poprawnie.

Ponadto hashCode() spowoduje dodatkowe trudności, ze względu na następujące requirement:

Jeśli dwa obiekty są równe metodą equals(Object), a następnie wywołanie metody hashCode każdego z dwóch przedmiotów musi produkować ten sam wynik całkowity.

Wymóg hashCode() można pominął za pomocą TreeSet zamiast HashSet.

Answer 2

Co zrobiłbym jest okrągła deblu przed ich użyciem (zakładając, że jest to właściwe)

np

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. 

Możesz zawęzić to zachowanie w swoim własnym DoubleHashSet. Jeśli chcesz zarezerwować oryginalną wartość, możesz użyć HashMap lub TDoubleDoubleHashMap, gdzie klucz jest wartością zaokrągloną, a wartość jest oryginalna.

Answer 3

I wprowadziły @ podejścia NPE jest (ja przyjąłem jego/jej odpowiedzi więc on/ona dostaje punkty :-) i podać kod tutaj

//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); 
    } 

i przetestować go

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()); 
}