Я пытаюсь оптимизировать фрагмент кода, который сравнивает элементы списка.
Eg.
public void compare(Set<Record> firstSet, Set<Record> secondSet){
for(Record firstRecord : firstSet){
for(Record secondRecord : secondSet){
// comparing logic
}
}
}
Пожалуйста, учтите, что количество записей в наборах будет высоким.
Спасибо
Шекхар
firstSet.equals(secondSet)
Это действительно зависит от того, что вы хотите сделать в логике сравнения... т.е. что произойдет, если вы найдете элемент в одном наборе, а не в другом? Ваш метод имеет тип возвращаемого значения void, поэтому я предполагаю, что вы будете выполнять необходимую работу в этом методе.
Более точный контроль, если вам это нужно:
if (!firstSet.containsAll(secondSet)) {
// do something if needs be
}
if (!secondSet.containsAll(firstSet)) {
// do something if needs be
}
Если вам нужно получить элементы, которые находятся в одном наборе, а не в другом.
ОБНОВЛЕНИЕ: set.removeAll(otherSet) возвращает логическое значение, а не набор. Чтобы использовать removeAll(), вам нужно скопировать набор, а затем использовать его.
Set one = new HashSet<>(firstSet);
Set two = new HashSet<>(secondSet);
one.removeAll(secondSet);
two.removeAll(firstSet);
Если содержимое one и two пусто, то вы знаете, что оба набора были равны. Если нет, то у вас есть элементы, которые сделали наборы неравными.
Вы упомянули, что количество записей может быть высоким. Если базовой реализацией является HashSet, то выборка каждой записи выполняется за время O(1), так что вы не сможете получить намного лучше, чем это. TreeSet - это O(log n).
Если вы просто хотите узнать, равны ли наборы, метод 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);
}
Обратите внимание, как оптимизируются общие случаи, когда:
После этого containsAll(...) вернет false, как только найдет элемент в другом наборе, которого также нет в этом наборе. Но если все элементы присутствуют в обоих наборах, необходимо проверить все из них.
Таким образом, наихудшая производительность возникает, когда два набора равны, но не одинаковые объекты. Эта стоимость обычно составляет O(N) или O(NlogN) в зависимости от реализации this.containsAll(c).
И вы получите производительность, близкую к худшему, если наборы велики и отличаются лишь небольшим процентом элементов.
UPDATE
Если вы хотите потратить время на реализацию пользовательского набора, есть подход, который может улучшить "почти такой же" случай.
Идея состоит в том, что вам нужно предварительно рассчитать и кэшировать хеш для всего набора, чтобы вы могли получить текущее значение текущего хеш-кода в O(1). Затем вы можете сравнить хэш-код для двух наборов в качестве ускорения.
Как вы могли бы реализовать такой хэш-код? Хорошо, если установлен хеш-код:
тогда вы можете дешево обновлять установленный кэшированный хеш-код каждый раз, когда добавляете или удаляете элемент. В обоих случаях вы просто делаете XOR хеш-кода элемента с текущим установленным хеш-кодом.
Конечно, это предполагает, что хеш-коды элементов являются стабильными, в то время как элементы являются членами наборов. Также предполагается, что функция hashcode классов элементов дает хороший разброс. Это потому, что, когда два набора хеш-кодов совпадают, вам все равно придется вернуться к O(N) сравнению всех элементов.
Вы могли бы развить эту идею немного дальше... по крайней мере, в теории.
ВНИМАНИЕ - Это очень умозрительно. "Мысленный эксперимент", если хотите.
Предположим, что в вашем классе элементов set есть метод для возврата контрольной суммы крипто для элемента. Теперь реализуйте контрольные суммы, используя XOR контрольных сумм, возвращаемых для элементов.
Что это покупает нас?
Хорошо, если мы предположим, что ничего не происходит, вероятность того, что любые два неравных набора элементов имеют одинаковые 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).
Недостатком является то, что вычисление крипто контрольных сумм для элементов очень дорого, особенно с увеличением числа битов. Таким образом, вам действительно нужен эффективный механизм для запоминания контрольных сумм. И это может быть проблематично.
И другой недостаток заключается в том, что ненулевая вероятность ошибки может быть неприемлемой независимо от того, насколько мала вероятность. (Но если это так... как вы справляетесь со случаем, когда космический луч переворачивает критический бит? Или если он одновременно переворачивает один и тот же бит в двух случаях избыточной системы?)
В Guava Sets есть способ, который может помочь здесь:
public static <E> boolean equals(Set<? extends E> set1, Set<? extends E> set2){
return Sets.symmetricDifference(set1,set2).isEmpty();
}
У вас есть следующее решение из https://www.mkyong.com/java/java-how-to-compare-two-sets/
public static boolean equals(Set<?> set1, Set<?> set2){
if(set1 == null || set2 ==null){
return false;
}
if(set1.size() != set2.size()){
return false;
}
return set1.containsAll(set2);
}
Или, если вы предпочитаете использовать один оператор return:
public static boolean equals(Set<?> set1, Set<?> set2){
return set1 != null
&& set2 != null
&& set1.size() == set2.size()
&& set1.containsAll(set2);
}
Существует решение 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;
}
}
Если вы используете библиотеку Guava, это можно сделать:
SetView<Record> added = Sets.difference(secondSet, firstSet);
SetView<Record> removed = Sets.difference(firstSet, secondSet);
И затем сделайте вывод, основанный на них.
Я бы поставил 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
}
}
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;
}
Я думаю, что метод reference с методом equals можно использовать. Мы предполагаем, что тип объекта без тени сомнения имеет свой собственный метод сравнения. Здесь простой и простой пример,
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