Как лучше для сравнения двух коллекций в Java и на них действуют?

голоса
39

У меня есть две коллекции одного и того же объекта, Collection<Foo> oldSetи Collection<Foo> newSet. Необходимая логика выглядит следующим образом :

  • если fooв (*) , oldSetно не newSet, вызовdoRemove(foo)
  • иначе , если fooне в oldSetно newSet, вызовdoAdd(foo)
  • иначе , если fooв обоих сборниках , но модифицированный, вызовdoUpdate(oldFoo, newFoo)
  • иначе , если !foo.activated && foo.startDate >= now, вызовdoStart(foo)
  • иначе , если foo.activated && foo.endDate <= now, вызовdoEnd(foo)

(*) «В» означает уникальные идентификаторы матчи, но не обязательно содержание.

Тока (устаревший код) делает много сравнений , чтобы выяснить removeSet, addSet, updateSet, startSetи endSet, а затем цикл действовать по каждому пункту.

Код довольно грязный (отчасти потому, что я оставил некоторую логику спагетти уже) и я пытаюсь реорганизовать его. Некоторая более справочная информация:

  • Насколько я знаю, oldSetи newSetна самом деле при поддержкеArrayList
  • Каждый набор содержит менее чем 100 пунктов, скорее всего, Макс из 20
  • Этот код называется часто (измеряется в миллионах / день), хотя наборы редко отличаются

Мои вопросы:

  • Если преобразовать oldSetи newSetв HashMap<Foo>(порядок не вызывает беспокойства здесь), с идентификаторами в качестве ключей, будет он сделал код проще читать и легче сравнить? Сколько времени и памяти , производительность является потеря на конверсию?
  • переборе бы два комплекта и выполнять соответствующие операции более эффективные и лаконичные?
Задан 22/08/2008 в 21:47
источник пользователем
На других языках...                            


8 ответов

голоса
34

Библиотека commons.collections Apache имеет класс CollectionUtils, который обеспечивает легкие в использовании методов для манипулирования Collection / проверки, таких как пересечение, разность и профсоюз.

Документы org.apache.commons.collections.CollectionUtils API находятся здесь .

Ответил 22/07/2009 в 19:29
источник пользователем

голоса
20

Вы можете использовать Java 8 потоков, например,

set1.stream().filter(s -> set2.contains(s)).collect(Collectors.toSet());

или Устанавливает класс из гуавы :

Set<String> intersection = Sets.intersection(set1, set2);
Set<String> difference = Sets.difference(set1, set2);
Set<String> symmetricDifference = Sets.symmetricDifference(set1, set2);
Set<String> union = Sets.union(set1, set2);
Ответил 26/12/2011 в 19:21
источник пользователем

голоса
9

Я создал приближение того, что я думаю, что вы ищете только с помощью Collections Framework в Java. Честно говоря, я думаю, что это, вероятно, избыточна, как Deck @ Mike указывает. Для такого небольшого набора элементов для сравнения и процесса я думаю, что массивы были бы лучшим выбором с процедурной точки зрения, но вот мое псевдо-кодом решения (потому что я ленивый). У меня есть предположение, что класс Foo сравнимый основан на уникальный идентификатор, а не все данные в его содержание:

Collection<Foo> oldSet = ...;
Collection<Foo> newSet = ...;

private Collection difference(Collection a, Collection b) {
    Collection result = a.clone();
    result.removeAll(b)
    return result;
}

private Collection intersection(Collection a, Collection b) {
    Collection result = a.clone();
    result.retainAll(b)
    return result;
}

public doWork() {
    // if foo is in(*) oldSet but not newSet, call doRemove(foo)
    Collection removed = difference(oldSet, newSet);
    if (!removed.isEmpty()) {
        loop removed {
            Foo foo = removedIter.next();
            doRemove(foo);
        }
    }
    //else if foo is not in oldSet but in newSet, call doAdd(foo)
    Collection added = difference(newSet, oldSet);
    if (!added.isEmpty()) {
        loop added  {
            Foo foo = addedIter.next();
            doAdd(foo);
        }
    }

    // else if foo is in both collections but modified, call doUpdate(oldFoo, newFoo)
    Collection matched = intersection(oldSet, newSet);
    Comparator comp = new Comparator() {
        int compare(Object o1, Object o2) {
            Foo f1, f2;
            if (o1 instanceof Foo) f1 = (Foo)o1;
            if (o2 instanceof Foo) f2 = (Foo)o2;
            return f1.activated == f2.activated ? f1.startdate.compareTo(f2.startdate) == 0 ? ... : f1.startdate.compareTo(f2.startdate) : f1.activated ? 1 : 0;
        }

        boolean equals(Object o) {
             // equal to this Comparator..not used
        }
    }
    loop matched {
        Foo foo = matchedIter.next();
        Foo oldFoo = oldSet.get(foo);
        Foo newFoo = newSet.get(foo);
        if (comp.compareTo(oldFoo, newFoo ) != 0) {
            doUpdate(oldFoo, newFoo);
        } else {
            //else if !foo.activated && foo.startDate >= now, call doStart(foo)
            if (!foo.activated && foo.startDate >= now) doStart(foo);

            // else if foo.activated && foo.endDate <= now, call doEnd(foo)
            if (foo.activated && foo.endDate <= now) doEnd(foo);
        }
    }
}

Насколько ваши вопросы: Если я конвертировать oldSet и Newset в HashMap (порядка не вызывает беспокойства здесь), с идентификаторами в качестве ключей, будет он сделал код проще читать и легче сравнить? Сколько времени и памяти, производительность является потеря на конверсию? Я думаю, что вы, вероятно, сделать код более удобным для чтения с помощью карты, но ... вы бы, вероятно, использовать больше памяти и времени во время преобразования.

переборе бы два комплекта и выполнять соответствующие операции более эффективные и лаконичные? Да, это было бы лучшее из обоих миров, особенно если вы следовали рекомендации Шарек @ Mike «s из Подвижной свой собственный список со специализированными методами или после что-то вроде шаблона Visitor дизайна для запуска через вашу коллекцию и обработать каждый элемент.

Ответил 23/08/2008 в 04:54
источник пользователем

голоса
2

Я думаю, что самый простой способ сделать это с помощью Apache коллекции апи - CollectionUtils.subtract (песни1, List2) до тех пор, списки одного и того же типа.

Ответил 23/06/2010 в 19:29
источник пользователем

голоса
2

Я бы перейти к спискам и решить это следующим образом:

  1. Сортировка оба списка по идентификатору возрастанию с помощью пользовательского компаратора , если объекты в списках не Сопоставимые
  2. Перебирать элементы в обоих списках , как в фазе слияния в алгоритме сортировки слиянием , но вместо слияния списков, вы проверяете вашу логику.

Код будет более или менее, как это:

/* Main method */
private void execute(Collection<Foo> oldSet, Collection<Foo> newSet) {
  List<Foo> oldList = asSortedList(oldSet);
  List<Foo> newList = asSortedList(newSet);

  int oldIndex = 0;
  int newIndex = 0;
  // Iterate over both collections but not always in the same pace
  while( oldIndex < oldList.size() 
      && newIndex < newIndex.size())  {
    Foo oldObject = oldList.get(oldIndex);
    Foo newObject = newList.get(newIndex);

    // Your logic here
    if(oldObject.getId() < newObject.getId()) {
      doRemove(oldObject);
      oldIndex++;
    } else if( oldObject.getId() > newObject.getId() ) {
      doAdd(newObject);
      newIndex++;
    } else if( oldObject.getId() == newObject.getId() 
            && isModified(oldObject, newObject) ) {
      doUpdate(oldObject, newObject);
      oldIndex++;
      newIndex++;
    } else {
      ... 
    }
  }// while

  // Check if there are any objects left in *oldList* or *newList*

  for(; oldIndex < oldList.size(); oldIndex++ ) {
    doRemove( oldList.get(oldIndex) );  
  }// for( oldIndex )

  for(; newIndex < newList.size(); newIndex++ ) {
    doAdd( newList.get(newIndex) );
  }// for( newIndex ) 
}// execute( oldSet, newSet )

/** Create sorted list from collection 
    If you actually perform any actions on input collections than you should 
    always return new instance of list to keep algorithm simple.
*/
private List<Foo> asSortedList(Collection<Foo> data) {
  List<Foo> resultList;
  if(data instanceof List) {
     resultList = (List<Foo>)data;
  } else {
     resultList = new ArrayList<Foo>(data);
  }
  Collections.sort(resultList)
  return resultList;
}
Ответил 31/08/2008 в 18:58
источник пользователем

голоса
0
public static boolean doCollectionsContainSameElements(
        Collection<Integer> c1, Collection<Integer> c2){

    if (c1 == null || c2 == null) {
        return false;
    }
    else if (c1.size() != c2.size()) {
        return false;
    } else {    
        return c1.containsAll(c2) && c2.containsAll(c1);
    }       
}
Ответил 09/02/2016 в 15:44
источник пользователем

голоса
-1

Для набора, что маленький, как правило, не стоит того, чтобы конвертировать из массива в HashMap / набор. На самом деле, вы, вероятно, лучше от держать их в массиве, а затем их сортировки по ключу и итерация в обоих списках одновременно, чтобы сделать сравнение.

Ответил 22/08/2008 в 21:57
источник пользователем

голоса
-2

Для comaparing списка или набора мы можем использовать Arrays.equals(object[], object[]). Он будет проверять только значение. Для того, чтобы получить , Object[]мы можем использовать Collection.toArray()метод.

Ответил 17/12/2010 в 11:05
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more