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

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() "equal" new Cat()? Ваш пример подсказывает, что он делает !!
• Что вы подразумеваете под «разницей»? Вы имеете в виду разницу в настройках?
• Что вы хотите, если два массива имеют одинаковую длину?
• Является ли это разовым сравнением или это происходит неоднократно для тех же массивов?
• Сколько элементов в массивах (в среднем)?
• Почему вы используете массивы?

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

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

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

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

Answer 2

Ну, вы можете использовать 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 3

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

// 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/calculating-intersection-of-two-java.html

Answer 4

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

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

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

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

UPDATE:

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

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

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

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

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

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

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

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

Answer 5

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

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

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

Edit:

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