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

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

Например.

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) .

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

ОБНОВИТЬ

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

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

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

• ноль для пустого набора и
• XOR всех хэш-кодов элементов для непустого набора,

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

Конечно, это предполагает, что хэш-коды элементов стабильны, в то время как элементы являются членами наборов. Также предполагается, что функция хэш-кода классов элементов дает хороший разброс. Это связано с тем, что, когда два набора хэш-кода совпадают, вам все равно придется вернуться к 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);
}

Или, если вы предпочитаете использовать один оператор возврата:

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

А потом сделайте на основании этого вывод.

Я бы поместил второй набор в 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;
    }

Я думаю, что можно использовать ссылку на метод с методом 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