Как я могу сделать копию итератора в 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?

Answer 1

Вы не можете копировать итераторы Java, поэтому вам придется делать это без них:

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

Answer 2

Вы можете сделать это с помощью 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³), как тогда доступ к индексу в других ответах.(Вы можете быть еще быстрее, если сначала скопируете свой список в массив, но здесь это только постоянный фактор.)

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

Answer 3

Для связанного списка (который имеет медленный доступ к индексу), я думаю, что есть способ сделать это, не вызывая замедления O (n²), о котором упоминал Пэйло. Пока вас не волнует порядок посещения списка, вы можете запустить внешний цикл с последнего элемента и выполнить итерацию назад, а также запустить внутренний цикл с первого элемента и выполнять итерацию вперед, пока не встретятся два итератора. См. iterRevIterator в коде ниже. Вызов list.listIterator(list.size()) быстрый, потому что list является LinkedList, то есть двусвязным списком, и доступ к последнему элементу не требует итерации по списку. Разница не огромная ...

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);

    }

}

Answer 4

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