Java: Equalator? (удаление дубликатов из коллекции объектов)

Question

У меня есть куча объектов класса Puzzle. Я переопределил equals() и hashCode(). Когда пришло время представить решения для пользователя, я бы хотел отфильтровать все «похожие» головоломки (по стандарту, который я определил), поэтому пользователь видит только один из них.

Сходство транзитивно.

Пример:

Result of computations: 
A (similar to A) 
B (similar to C) 
C 
D 

В этом случае, только А или Д и В или С будет представлена ​​пользователю, - но не две подобные головоломки. Две одинаковые головоломки одинаково важны. Важно только, чтобы они не показывались пользователю.

Для этого я хотел использовать ADT, который запрещает дубликаты. Тем не менее, я не хочу изменять методы equals() и hashCode(), чтобы вместо этого вернуть значение сходства. Есть ли Equalator, как Comparator, что я могу использовать в этом случае? Или я должен делать это иначе?

Класс, над которым я работаю, - это головоломка, которая поддерживает сетку букв. (Подобно Scrabble.) Если головоломка содержит одни и те же слова, но находится в другой ориентации, она считается похожей. Таким образом, следующие озадачить:

        (2, 2): A   
            (2, 1): C   
            (2, 0): T 

бы быть похожа на:

    (1, 2): A   
        (1, 1): C   
        (1, 0): T  

Answer 1

Я хотел бы использовать класс-оболочку, которая подменяет equals и hashCode соответственно.

private static class Wrapper { 
    public static final Puzzle puzzle; 
    public Wrapper(Puzzle puzzle) { 
     this.puzzle = puzzle; 
    } 
    @Override 
    public boolean equals(Object object) { 
     // ... 
    } 
    @Override 
    public int hashCode() { 
     // ... 
    } 
} 

, а затем вы обертываете все свои головоломки, кладите их на карту и вынимаете их снова & hellip;

public Collection<Collection<Puzzle>> method(Collection<Puzzles> puzzles) { 
    Map<Wrapper,<Collection<Puzzle>> map = new HashMap<Wrapper,<Collection<Puzzle>>(); 
    for (Puzzle each: puzzles) { 
     Wrapper wrapper = new Wrapper(each); 
     Collection<Puzzle> coll = map.get(wrapper); 
     if (coll == null) map.put(wrapper, coll = new ArrayList<Puzzle>()); 
     coll.add(puzzle); 
    } 
    return map.values(); 
} 

Answer 2

Хорошо, у вас есть способ измерения сходства между объектами. Это означает, что они образуют Metric Space.

Вопрос в том, является ли ваше пространство также Euclidean space обычным трехмерным пространством или целыми числами или чем-то подобным? Если да, то вы можете использовать binary space partition в любом количестве измерений.

(Вопрос, в принципе: есть гомоморфизм между вашими объектами и с реальным номером вектора п-мерного Если да, то вы можете использовать методы для измерения близость точек в п-мерном пространстве?).

Теперь, если это не евклидово пространство, то у вас есть большая проблема. Примером неевклидового пространства, с которым наиболее знакомы программисты, будет Levenshtein Distance между строками.

Если ваша проблема похожа увидеть, как похожа строка является списком уже существующих строк, то я не знаю каких-либо алгоритмов, которые могли бы сделать это без O (п) время. Может быть, там есть.

---

Но еще один важный вопрос: сколько времени у вас есть? Сколько объектов? Если у вас есть время или если ваш набор данных достаточно мал, что алгоритм O (n) практичен, вам просто нужно пройти через список объектов, чтобы увидеть, если он ниже определенного порога. Если да, отвергайте его.

Просто перегрузите AbstractCollection и замените функцию Добавить. Используйте ArrayList или что-то еще. Ваш код будет выглядеть вроде этого

class SimilarityRejector<T> extends AbstractCollection<T>{ 
    ArrayList<T> base; 
    double threshold; 

    public SimilarityRejector(double threshold){ 
     base = new ArrayList<T>(); 
     this.threshold = threshold; 
    } 

    public void add(T t){ 
     boolean failed = false; 
     for(T compare : base){ 
      if(similarityComparison(t,compare) < threshold) faled = true; 
     } 
     if(!failed) base.add(t); 
    } 

    public Iterator<T> iterator() { 
     return base.iterator(); 
    } 

    public int size() { 
     return base.size(); 
    } 
} 

и т.д. Очевидно, что T должен был бы быть подклассом некоторого класса, который вы можете выполнить сравнение на. Если у вас есть евклидова метрика, то вы можете использовать пространственный раздел, а не проходить через все остальные предметы.

Answer 3

1. Создание TreeSet с помощью Comparator
2. Добавляет все элементы в наборе
3. Все дубликаты раздели

Answer 4

Обычно «сходство» не является транзитивным отношения. Таким образом, первым шагом было бы думать об этом с точки зрения эквивалентности, а не сходства. Эквивалентность рефлексивна, симметрична и транзитивна.

Простым подходом здесь является определение оболочки-пазла, методы equals() и hashCode() реализованы в соответствии с рассматриваемым отношением эквивалентности.

Как только у вас есть это, опустите обернутые объекты в java.util.Set и отфильтруйте дубликаты.

Answer 5

ИМХО, самый элегантный способ был описан Гили (TreeSet с пользовательским компаратором).

Но если вы хотите сделать это самостоятельно, кажется, это самое простое и ясное решение:

/** 
* Distinct input list values (cuts duplications) 
* @param items items to process 
* @param comparator comparator to recognize equal items 
* @return new collection with unique values 
*/ 
public static <T> Collection<T> distinctItems(List<T> items, Comparator<T> comparator) { 
    List<T> result = new ArrayList<>(); 

    for (int i = 0; i < items.size(); i++) { 
     T item = items.get(i); 

     boolean exists = false; 
     for (int j = 0; j < result.size(); j++) { 
      if (comparator.compare(result.get(j), item) == 0) { 
       exists = true; 
       break; 
      } 
     } 

     if (!exists) { 
      result.add(item); 
     } 
    } 

    return result; 
}