如何在Java中制作迭代器的副本？

Question

我们有一个元素列表，并且有一个非常简单的碰撞检测，其中我们检查每个对象与其他每个对象。

这个检查是可交换的，所以为了避免重复两次，我们在C++中会这样做：

for (list<Object>::iterator it0 = list.begin(); it0 != list.end(); ++it0)
{
    for (list<Object>::iterator it1 = it0; it1 != list.end(); ++it1)
    {
        Test(*it0, *it1);
    }
}

关键在于复制部分

it1 = it0

你如何用Java来编写这个？

- Luis

Answer 1

您可以使用ListIterator来实现此操作：

for(ListIterator<O> outer = list.listIterator(); outer.hasNext() ; ) {
    O oVal = outer.next();
    for(ListIterator<O> inner = list.listIterator(outer.nextIndex()); inner.hasNext(); ) {
         Test(oVal, inner.next());
    }
}

对于链表（索引访问速度较慢的数据结构），list.listIterator(index)仍然需要迭代到正确的位置。 但这种方法仅为O(n²)，而不是其他答案中的索引访问O(n³)。 （如果您首先将列表复制到数组中，可能会更快，但这只是一个常数因子。） 当然，如果通常需要基于索引的访问（或此迭代器克隆），最好使用基于数组的列表（或其迭代器支持克隆的自定义列表）。

- Paŭlo Ebermann

Answer 2

你无法复制Java迭代器，因此你必须在没有它们的情况下完成它：

for(int i=0; i<list.size(); i++){
    for(int j=i; j<list.size(); j++){
        Test(list.get(i), list.get(j));
    }
}

- Michael Borgwardt

---

有一种Java类型支持.size()和通过数组样式下标访问元素吗？ - aroth

只有使用数组结构它才能很好地工作，而链表则不行。 - Danila Manturov

Answer 3

对于一个链表（索引访问较慢），我认为有一种方法可以避免Paŭlo提到的O(n²)的减速。只要您不关心列表被访问的顺序，您可以从最后一个元素开始外部循环并向后迭代，从第一个元素开始内部循环并向前迭代，直到两个迭代器相遇。请参见下面代码中的iterRevIterator。调用list.listIterator(list.size())很快，因为list是一个双向链接列表，访问最后一个元素不需要通过整个列表进行迭代。 差别并不是很大...

iterIndex: 384.59ms sum=29656666
iterIterator: 1.91ms sum=29656666
iterRevIterator: 1.55ms sum=29656666

但仍然很重要。

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;


public class TestIter {

    public static int iterIndex(List<Integer> list) {
        int sum = 0;
        for(int i = 0; i < list.size(); ++i) {
            for(int j = i+1; j < list.size(); ++j) {
                sum += list.get(i) * list.get(j);
            }
        }
        return sum;
    }

    public static int iterIterator(List<Integer> list) {
        int sum = 0;
        for(ListIterator<Integer> outer = list.listIterator(); outer.hasNext() ; ) {
            Integer oVal = outer.next();
            for(ListIterator<Integer> inner = list.listIterator(outer.nextIndex()); inner.hasNext(); ) {
                sum += oVal * inner.next();
            }
        }
        return sum;
    }

    public static int iterRevIterator(List<Integer> list) {
        int sum = 0;
        for(ListIterator<Integer> outer = list.listIterator(list.size()); outer.hasPrevious() ; ) {
            Integer oVal = outer.previous();
            for(ListIterator<Integer> inner = list.listIterator(); inner.nextIndex() <= outer.previousIndex(); ) {
                sum += oVal * inner.next();
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int size = 1000;
        int rep = 100;
        int sum = 0;
        // List<Integer> list = new ArrayList<Integer>();
        List<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < size; ++i) {
            list.add(i);
        }

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < rep; ++i) {
            sum = iterIndex(list);
        }
        System.out.println("iterIndex: " + (float)(System.currentTimeMillis() - startTime)/rep + "ms sum=" + sum);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < rep; ++i) {
            sum = iterIterator(list);
        }
        System.out.println("iterIterator: " + (float)(System.currentTimeMillis() - startTime)/rep + "ms sum=" + sum);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < rep; ++i) {
            sum = iterRevIterator(list);
        }
        System.out.println("iterRevIterator: " + (float)(System.currentTimeMillis() - startTime)/rep + "ms sum=" + sum);

    }

}

- Luca Citi

---

我没有提到O(n²)的减速，我说你总是需要O(n²) - 不管你使用哪种数据结构。你的例子稍微快一点（通过一个常数因子），但它仍然是O(n²)。如果你需要访问每个（无序）元素对一次，你仍然有n·(n-1)/2个元素访问，这是O(n²)，不管你怎么做。 - Paŭlo Ebermann

当然，你是对的。它仍然是$O(n^2)$。已经有一段时间了，我不知道我在想什么。 - Luca Citi