可以在同一列表的另一个迭代中迭代列表吗？

Question

我在 ArrayList 中有一些对象，我想执行碰撞检测等。可以做这样的事情吗：

List<Person> A;
iterA0 = A.iterator();
while (iterA0.hasNext()) {
    Person A = iterA.next();
    iterA1 = A.iterator();
    while (iterA1.hasNext()){
        Person B = iterA1.next();
        A.getsDrunkAndRegretsHookingUpWith(B);
    }
}

这一定是糟糕的编码，对吧？我将如何正确执行此嵌套迭代？

Answer 1

您可以同时多次迭代同一个列表，只要它在任何迭代期间都没有被修改。例如：

List<Person> people = ...;
for (Person a : people) {
    for (Person b : people)
        a.getsDrunkAndRegretsHookingUpWith(b);
}

只要 getsDrunkAndRegretsHookingUpWith 方法不更改 people 列表，就没有问题。

Answer 2

这是经典握手问题的一个例子。在一个充满 n 人的房间里，有 n 种选择 2 种不同的可能的握手方式。你无法避免二次运行时间。

@Chris 的回答向您展示了一种更好的编码方法。

---

回复：OP评论

我一直在编写一些代码，其中一个事件会导致粒子爆炸，从而导致附近所有粒子爆炸......连锁反应。对象存储在一个列表中，未爆炸粒子仅在爆炸粒子的定义半径内才会爆炸。所以我可以提出一些条件来使其更快一点，但仍然需要 n^2 遍历。

您不应该不使用列表来存储粒子。如果您要对二维粒子进行建模，请使用四叉树。如果是 3 维，则为 八叉树。

Answer 3

如果您遇到以下情况，则可以减少迭代次数：

• A.getsDrunkAndRegretsHookingUpWith(B) 也意味着 B.getsDrunkAndRegretsHookingUpWith(A)，
• 并且 A.getsDrunkAndRegretsHookingUpWith(A) 对于所有元素总是相同的

，那么您可以采取更传统的方法，而不是使用迭代器或 foreach，并排除与自身以及与已经发生 withc 比较的元素的碰撞。

List<Person> people;
for (int i=0; i<people.size(); i++){
    a = people.get(i);
    for (int j=i+1; j<people.size();j++){ // compare with next element and onwards in the list
        a.getsDrunkAndRegretsHookingUpWith(people.get(j)); // call method
    }
}

Answer 4

这一定是糟糕的编码，对吧？

大多数人可能会同意，如果您使用的是 Java 5+，并且没有特别需要公开迭代器对象，那么您应该通过使用“foreach”循环来简化代码。然而，这应该不会影响性能，当然也不会影响复杂性。

不必要地暴露迭代器当然不是糟糕的编程。按照 1 到 10 的糟糕编码风格评分，这只是 1 或 2。（任何告诉你其他情况的人最近都没有见过任何真正糟糕的编码......）

那么如何对自己做n^2呢？

你原来的问题太做作，无法回答这个问题。

根据真实关系是什么，您也许能够利用对称性/反对称性或关联性来减少工作量。

但是，如果没有该信息（或其他域信息），您就无法改进此解决方案。

---

对于您的真实示例（涉及粒子），您可以通过将屏幕划分为多个区域来避免 O(N^2) 比较问题；例如使用四叉树。然后迭代相同和相邻区域中的点。