Сравнение массива и получение разницы

Question

Как мне сравнить два массива, которые могут иметь разную длину, и получить разницу между каждым массивом?

Например:

Cat cat = new Cat();
Dog dog = new Dog();
Alligator alligator = new Alligator();

Animal animals[] = { cat, dog };
Animal animals2[] = { cat, dog, alligator };

Как бы я сравнилэти два массива и заставить его вернуть экземпляр Alligator?

Answer 1

Я бы предложил, чтобы ваш вопрос был уточнен.В настоящее время все гадают о том, что вы на самом деле спрашиваете.

• Предназначены ли массивы для представления наборов, списков или чего-то промежуточного?Другими словами, имеет ли значение порядок элементов и могут ли быть дубликаты?
• Что означает «равно»?new Cat() "равно" new Cat()?Ваш пример показывает, что это так !!
• Что вы подразумеваете под "разницей"?Вы имеете в виду разность множеств?
• Что вы хотите, чтобы произошло, если два массива имеют одинаковую длину?
• Является ли это разовым сравнением или оно повторяется для одних и тех же массивов?
• Сколько элементов в массивах (в среднем)?
• Почему вы вообще используете массивы?

Делая предположение, что эти массивы предназначены для использованиячтобы быть истинными наборами, тогда вам, вероятно, следует использовать HashSet вместо массивов и использовать операции сбора, такие как addAll и retainAll, для вычисления разности множеств.

С другой стороны, если массивыпредназначены для представления списков, не совсем понятно, что означает «различие».

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

Наконец, если вы собираетесь использовать что-либо, что зависит отМетод equals(Object) (и который включает в себя любой из типов коллекций Java, вам действительно необходимо четко понимать, что «равно» должно означать в вашем приложении. Все ли экземпляры Cat равны? Они все разные?некоторые Cat экземпляры равны, а другие нет? Если вы не поймете это и не реализуете методы equals и hashCode соответственно, вы получите путанные результаты.

Answer 2

Я предлагаю вам поместить ваши объекты в наборы, а затем использовать пересечение наборов:

// Considering you put your objects in setA and setB

Set<Object> intersection = new HashSet<Object>(setA);
intersection.retainAll(setB);

После этого вы можете использовать removeAll, чтобы получить разницу для любого из двух наборов:

setA.removeAll(intersection);
setB.removeAll(intersection);

По мотивам: http://hype -free.blogspot.com / 2008/11 / calculation-intersection-of-two-java.html

Answer 3

Вы можете посмотреть эту статью для получения дополнительной информации:

http://download -llnw.oracle.com / javase / tutorial / collection / interfaces / set.html

Как уже упоминалось, removeAll() создан для этого, но вы захотите сделать это дважды, чтобы вы могли создать список всего, чего не хватает в обоих, и затем вы можете объединить эти два результата, чтобы получитьсписок всех различий.

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

ОБНОВЛЕНИЕ:

Похоже, мое предположение о том, что находится в массиве, неверно, поэтому removeAll() не будет работать, но с требованием 5 мс, в зависимости от количества элементовпоиск может быть проблемой.

Таким образом, может показаться, что HashMap<String, Animal> будет лучшим вариантом, поскольку он быстр в поиске.

Animal - это интерфейс с хотя бы одним свойствомString name.Для каждого класса, который реализует Animal, напишите код для Equals и hashCode.Вы можете найти некоторые обсуждения здесь: http://www.ibm.com/developerworks/java/library/j-jtp05273.html. Таким образом, если вы хотите, чтобы хеш-значение было комбинацией типа животного и имени, тогда это будет хорошо.

Итак, основнойАлгоритм состоит в том, чтобы хранить все в хэш-картах, а затем искать различия, просто получить массив ключей и выполнить поиск, чтобы выяснить, содержится ли этот ключ в другом списке, и если он не помещен в List<Object>, сохраняя значение там.Вы захотите сделать это дважды, поэтому, если у вас есть по крайней мере двухъядерный процессор, вы можете получить некоторую выгоду от того, что оба поиска выполняются в отдельных потоках, но тогда вы захотите использовать один из одновременных добавленных типов данных.в JDK5, чтобы вам не приходилось беспокоиться о синхронизации в комбинированном списке различий.

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

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

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

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

Answer 4

Ну, вы можете вместо этого использовать Set и использовать метод removeAll().

Или вы можете использовать следующий простой и медленный алгоритм для выполнения:

List<Animal> differences = new ArrayList<Animal>();

    for (Animal a1 : animals) {
       boolean isInSecondArray = false;
       for (Animal a2 : animals2) {
           if (a1 == a2)  {
                isInSecondArray = true;
                break;
           }
       } 

       if (!isInSecondArray)
           differences.add(a1)
    }

differences будет иметь все объекты, которые находятся в массиве animals, но не в массиве animals2.Аналогичным образом вы можете сделать наоборот (получить все объекты, которые находятся в animals2, но не в animals).

Answer 5

Меня не волнует перфект для моего использования (и вы тоже не должны этого делать, если у вас нет веских причин для этого, и вы узнаете через свой профилировщик, что этот код является узким местом).

То, что я делаю, похоже на ответ функционала.Я использую операторы множеств LINQ, чтобы получить исключение в каждом списке:

http://msdn.microsoft.com/en-us/library/bb397894.aspx

Редактировать:

Извините, я этого не заметилэто Java.Извините, я в C # la-la land, и они выглядят очень похоже:)