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

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

Например,

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

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

Спасибо

Шекхар

вопрос задан 27.07.2010
Shekhar
2926 репутация

9 ответов


  • 123 рейтинг
    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 = firstSet;
    Set two = secondSet
    one.removeAll(secondSet);
    two.removeAll(firstSet);
    

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

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

    ответ дан Noel M, с репутацией 11684, 27.07.2010
  • 53 рейтинг

    Если вы просто хотите узнать, равны ли наборы, метод 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-код элемента с текущим установленным хэш-кодом.

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


    Вы могли бы пойти дальше этой идеи. , , по крайней мере, в теории.

    Предположим, что в вашем классе элементов set есть метод для возврата контрольных сумм шифрования для элемента. Теперь реализуйте контрольные суммы набора, 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 ().

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

    ответ дан Stephen C, с репутацией 499789, 27.07.2010
  • 14 рейтинг

    В Гуаве есть метод Sets, который может помочь здесь:

    public static   boolean equals(Set
     set1, Set
     set2){
    return Sets.symmetricDifference(set1,set2).isEmpty();
    }
    
    ответ дан husayt, с репутацией 6365, 17.12.2014
  • 3 рейтинг

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

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

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

    ответ дан riwnodennyk, с репутацией 5790, 13.10.2016
  • 3 рейтинг

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

    • наборы оба отсортированы
    • оба отсортированы в одном порядке

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

        public class SortedSetComparitor > 
                implements Comparator> {
    
            @Override
            public int compare( SortedSet arg0, SortedSet arg1 ) {
                Iterator 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;
            }
        }
    
    ответ дан Philip Couling, с репутацией 6481, 24.12.2014
  • 1 рейтинг
    public boolean equals(Object o) {
            if (o == this)
                return true;
            if (!(o instanceof Set))
                return false;
    
            Set a = this;
            Set b = o;
            Set thedifference_a_b = new HashSet(a);
    
    
            thedifference_a_b.removeAll(b);
            if(thedifference_a_b.isEmpty() == false) return false;
    
            Set thedifference_b_a = new HashSet(b);
            thedifference_b_a.removeAll(a);
    
            if(thedifference_b_a.isEmpty() == false) return false;
    
            return true;
        }
    
    ответ дан Zahran, с репутацией 126, 29.11.2014
  • 1 рейтинг

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

    HashMap hm = new HashMap(secondSet.size());
    int i = 0;
    for(Record secondRecord : secondSet){
        hm.put(i,secondRecord);
        i++;
    }
    for(Record firstRecord : firstSet){
        for(int i=0; i
    ответ дан Sahin Habesoglu, с репутацией 43, 31.03.2015
  • 0 рейтинг

    У вас есть следующее решение от https: // www. mkyong. com / java / java-как-сравнить-два набора /

    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);
    }
    
    ответ дан ilopezluna, с репутацией 1980, 27.09.2018
  • -1 рейтинг

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

    Set set = new HashSet<>();
    set.addAll(Arrays.asList("leo","bale","hanks"));
    
    Set set2 = new HashSet<>();
    set2.addAll(Arrays.asList("hanks","leo","bale"));
    
    Predicate pred = set::equals;
    boolean result = pred.test(set2);
    System.out.println(result);   // true
    
    ответ дан snr, с репутацией 4821, 7.06.2017