比较数组并获取差异

Question

我可以如何比较两个可能长度不同的数组，并得到每个数组之间的差异呢？

例如：

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

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

我该如何比较这两个数组并返回 Alligator 的实例？

- user238033

---

为了避免进一步的误解，您能否请修正您的例子，不要让它们成为对象，否则我们将在解决方案中遇到问题，因为您需要比较每个对象内的某些内容才能确定它们是否相等，例如 new Cat() == new Cat() = false，因为它们是两个不同的对象。 - James Black

@Gnarly - 不，你没有。Animal、Cat、Dog和Alligator都是类（不是原始类型）...所以它们的实例是对象，问题仍然存在。 - Stephen C

如果你想要一个对象数组，那么没问题，答案中的所有假设都是错误的。 - James Black

哦，我明白你的意思了。好了，我修好它了……九个月后。 - user238033

Answer 1

我建议您澄清一下问题。目前，每个人都在猜测您实际上在问什么。

- 数组是否旨在表示集合、列表或两者之间的某种东西？换句话说，元素顺序是否重要，是否可以有重复项？ - "相等"是什么意思？new Cat()是否与new Cat()相等？您的示例表明它确实如此！ - “差异”是什么意思？您是否指集合差异？ - 如果两个数组长度相同，您希望发生什么？ - 这是一次性比较还是针对相同数组重复出现？ - 数组中有多少个元素（平均）？ - 您为什么要使用数组？

假设这些数组旨在成为真正的集合，则您可能应该使用HashSet而不是数组，并使用集合操作（例如addAll和retainAll）来计算集合差异。

另一方面，如果数组用于表示列表，则“差异”的含义并不清楚。

如果代码运行速度很关键，那么您肯定需要重新考虑数据结构。如果您始终从数组开始，您将无法在一般情况下快速计算“差异”。

最后，如果您要使用任何依赖于equals（Object）方法的内容（包括任何Java集合类型），则确实需要清楚地了解在您的应用程序中“equals”应该意味着什么。所有Cat实例是否相等？他们都不同吗？一些Cat实例相等，而其他实例则不相等吗？如果您没有弄清楚这一点，并相应地实现equals和hashCode方法，则会得到令人困惑的结果。

- Stephen C

---

@Gnarly - 例子应该准确...否则人们会浪费时间尝试回答你不是真正想问的问题。例如，参考@James Black的评论。 - Stephen C

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 中的对象）。

- functional

---

@Gnarly - 你可能想先尝试这个建议并获取一些时间信息，因为它可能已经足够快满足你的需求了，因为程序的其他部分可能会拖慢解决方案。在优化之前，也就是增加更多复杂性之前，你应该知道减速发生在哪里，然后你可以回来说你需要一种方法，在x毫秒内遍历两个大小为n（某个数字）的数组。 - James Black

它需要每5毫秒循环一次。 - user238033

这不会起作用，因为两个相同类的实例不会被视为相同。new Cat() == new Cat() 总是为 false。 - Steve Kuo

@Steve Kuo - 如果您查看“functional”下的第一条评论，您会发现它不应该是关于对象的，因此，如果您因此而对所有人进行了负面评价，您可能需要重新考虑。 - James Black

@James，你说得对。这个问题的措辞是错误的。 - Steve Kuo

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

- Karel Petranek

---

交集将告诉您它们共有的元素，因此您需要从这两个列表中删除这些元素，以了解它们之间的差异，即它们共同拥有的剩余元素。 - James Black

@James Black：是的，可以通过functional建议的removeAll来实现。交集通常指的是你可以获取任意两个集合中“重叠”的元素。 - Karel Petranek

正如我所提到的，为了得到OP所要求的内容，您需要再进行另一步操作；您可能需要更新您的答案。 - James Black

Answer 4

您可能需要查看这篇文章以获取更多信息：

http://download-llnw.oracle.com/javase/tutorial/collections/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次，您可以了解每个更改带来的改进。

- James Black

Answer 5

我不关心我的用途的性能（除非你有充分的理由，并且通过分析器发现这段代码是瓶颈），你也不应该。

我的做法类似于functional的回答。我使用LINQ集合运算符来获取每个列表上的异常：

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

编辑：

抱歉，我没有注意到这是Java。对不起，我在C#的世界里迷失了，它们看起来非常相似 :)

- Merlyn Morgan-Graham