Каков самый быстрый способ сравнить два набора в Java?

Question

Я пытаюсь оптимизировать фрагмент кода, который сравнивает элементы списка.

Например.

public void compare(Set<Record> firstSet, Set<Record> secondSet){ 
    for(Record firstRecord : firstSet){ 
     for(Record secondRecord : secondSet){ 
      // comparing logic 
     } 
    } 
} 

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

Благодаря

Шекхар

Answer 1

firstSet.equals(secondSet) 

Это действительно зависит от того, что вы хотите сделать в логике сравнения ... то, что происходит, если вы нашли элемент в одном наборе не в другой? У вашего метода есть возвращаемый тип void, поэтому я предполагаю, что вы сделаете необходимую работу в этом методе.

Более мелкозернистый контроль, если вам это нужно:

if (!firstSet.containsAll(secondSet)) { 
    // do something if needs be 
} 
if (!secondSet.containsAll(firstSet)) { 
    // do something if needs be 
} 

Если вам нужно получить элементы, которые находятся в одном наборе, а не другие.
EDIT: set.removeAll(otherSet) возвращает логическое, а не набор. Чтобы использовать removeAll(), вам придется скопировать набор, а затем использовать его.

Set one = firstSet; 
Set two = secondSet 
one.removeAll(secondSet); 
two.removeAll(firstSet); 

Если содержимое one и two являются пустыми, то вы знаете, что эти два набора были равны. Если нет, то у вас есть элементы, которые сделали множества неравными.

Вы упомянули, что количество записей может быть высоким. Если базовая реализация - это HashSet, то выборка каждой записи производится в O(1) времени, поэтому вы не можете получить намного больше, чем это. TreeSet - O(log n).

Answer 2

Если вы просто хотите знать, если множества равны, equals метод на AbstractSet реализуется примерно, как показано ниже:

public boolean equals(Object o) { 
     if (o == this) 
      return true; 
     if (!(o instanceof Set)) 
      return false; 
     Collection c = (Collection) o; 
     if (c.size() != size()) 
      return false; 
     return containsAll(c); 
    } 

Обратите внимание, как она оптимизирует общие случаи, когда:

• в два объекта одинаковы
• Другой объект не является комплектом, и
• Размеры двух комплектов - это diff различны.

После этого containsAll(...) вернется false как только он находит элемент в другом наборе, который также не в этом наборе. Но если все элементы присутствуют в обоих наборах, им нужно будет проверить их все.

В худшем случае производительность возникает, когда два набора равны, но не одни и те же объекты. Эта стоимость обычно составляет O(N) или O(NlogN) в зависимости от реализации this.containsAll(c).

И если вы получаете большие и худшие характеристики корпуса, если они велики и отличаются только небольшим процентом элементов.

---

UPDATE

Если вы готовы инвестировать время в пользовательском наборе реализации, существует подход, который может улучшить «почти такое же» дело.

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

Как вы могли реализовать такой хэш-код? Ну, если множество хэш-код был:

• нуль для пустого множества, а
• XOR из всех элементов hashcodes для непустого множества,

тогда можно дешево обновить кешированный хэш-код набора при каждом добавлении или удалении элемента. В обоих случаях вы просто XOR хэш-код элемента с текущим заданным хэш-кодом.

Конечно, это предполагает, что хэш-коды элементов являются стабильными, а элементы являются членами множеств. Он также предполагает, что функция hashcode элементов классов классов дает хороший разброс. Это связано с тем, что, когда два набора хэш-кодов одинаковы, вам все равно придется вернуться к сравнению всех .

---

Вы можете принять эту идею немного дальше ... по крайней мере теоретически.

Предположим, что класс заданного элемента имеет метод для возврата контрольных сумм криптограммы для элемента. Теперь реализуем контрольные суммы набора с помощью XORing контрольных сумм, возвращаемых для элементов.

Что это покупает у нас?

Ну, если мы предположим, что ничего не сделано, вероятность того, что любые два неравных множества элемента имеют одни и те же контрольные суммы N-бит, равна 2 ^-N. А вероятность 2 неравных множеств имеет те же N-битовые контрольные суммы, что и 2 ^-N. Так что моя идея заключается в том, что вы можете реализовать equals как:

public boolean equals(Object o) { 
     if (o == this) 
      return true; 
     if (!(o instanceof Set)) 
      return false; 
     Collection c = (Collection) o; 
     if (c.size() != size()) 
      return false; 
     return checksums.equals(c.checksums); 
    } 

В указанных выше предположениях, это только даст вам неправильный ответ один раз в 2 ^-N времени. Если вы делаете N достаточно большим (например, 512 бит), вероятность неправильного ответа становится незначительной (например, примерно 10 ^-150).

Недостатком является то, что вычисление криптограмм для элементов очень дорого, особенно по мере увеличения количества бит. Поэтому вам действительно нужен эффективный механизм для запоминания контрольных сумм. И это может быть проблематично.

Answer 3

public boolean equals(Object o) { 
     if (o == this) 
      return true; 
     if (!(o instanceof Set)) 
      return false; 

     Set<String> a = this; 
     Set<String> b = o; 
     Set<String> thedifference_a_b = new HashSet<String>(a); 


     thedifference_a_b.removeAll(b); 
     if(thedifference_a_b.isEmpty() == false) return false; 

     Set<String> thedifference_b_a = new HashSet<String>(b); 
     thedifference_b_a.removeAll(a); 

     if(thedifference_b_a.isEmpty() == false) return false; 

     return true; 
    } 

Answer 4

Существует метод в гуавах Sets, который может помочь здесь:

public static <E> boolean equals(Set<? extends E> set1, Set<? extends E> set2){ 
return Sets.symmetricDifference(set1,set2).isEmpty(); 
} 

Answer 5

Там в O раствора (N) для очень специфических случаев, когда:

• наборов оба отсортированных
• оба отсортированы по тому же заказу

В следующем коде предполагается, что оба набора основаны на сопоставимых записях. Аналогичный метод может быть основан на компараторе.

public class SortedSetComparitor <Foo extends Comparable<Foo>> 
      implements Comparator<SortedSet<Foo>> { 

     @Override 
     public int compare(SortedSet<Foo> arg0, SortedSet<Foo> arg1) { 
      Iterator<Foo> otherRecords = arg1.iterator(); 
      for (Foo thisRecord : arg0) { 
       // Shorter sets sort first. 
       if (!otherRecords.hasNext()) return 1; 
       int comparison = thisRecord.compareTo(otherRecords.next()); 
       if (comparison != 0) return comparison; 
      } 
      // Shorter sets sort first 
      if (otherRecords.hasNext()) return -1; 
      else return 0; 
     } 
    } 

Answer 6

Я бы поставил secondSet в HashMap перед сравнением. Таким образом вы уменьшите время поиска второго списка до n (1). Как это:

HashMap<Integer,Record> hm = new HashMap<Integer,Record>(secondSet.size()); 
int i = 0; 
for(Record secondRecord : secondSet){ 
    hm.put(i,secondRecord); 
    i++; 
} 
for(Record firstRecord : firstSet){ 
    for(int i=0; i<secondSet.size(); i++){ 
    //use hm for comparison 
    } 
} 

Answer 7

Если вы используете библиотеку Guava это можно сделать:

 SetView<Record> added = Sets.difference(secondSet, firstSet); 
     SetView<Record> removed = Sets.difference(firstSet, secondSet); 

А затем сделать вывод, основанный на них.

Answer 8

Я думаю метод ссылка с методом равных можно использовать. Мы предполагаем, что тип объекта без тени сомнения имеет свой собственный метод сравнения. Простой и простой пример здесь,

Set<String> set = new HashSet<>(); 
set.addAll(Arrays.asList("leo","bale","hanks")); 

Set<String> set2 = new HashSet<>(); 
set2.addAll(Arrays.asList("hanks","leo","bale")); 

Predicate<Set> pred = set::equals; 
boolean result = pred.test(set2); 
System.out.println(result); // true