Как эффективно выполнить вложенную итерацию по абстрактному списку?

Question

Я пытаюсь воспроизвести типичную конструкцию «обхода верхней диагональной матрицы самодекартового произведения» со списком в качестве источника.С точки зрения непрофессионала, если у меня есть массив a, я хочу сделать это:

for (int i = 0; i < a.length; i++) {
  for (int j = i; j < a.length; j++) {
    collect(a[i], a[j]);
  }
}

Но имея реферат List, я не могу рассчитывать на эффективный доступ по индексу.

Я думал об этом, который экономит память и время (так как вызов sublist использует исходный список в качестве вспомогательной структуры), но не выглядит идиоматичным для Java:

for (List<E> tail = list; !tail.isEmpty(); tail = tail.sublist(1, tail.size()) {
  E a = tail.get(0);
  for (E b : tail) {
    collect(a, b);
  }
}

Любые лучшие варианты изтам?

---

Пример:

Если входная последовательность равна [1, 2, 3], а заполнитель collect равен System.out.println, на выходе должно бытьпары, в которых (индексы, а не значения) i> = j :

1 1
1 2
1 3
2 2
2 3
3 3

и не все возможные пары (это можно сделать двумя простыми циклами).

Answer 1

public static void collect(List<Integer> data) {
    List<Integer> a = data instanceof RandomAccess ? data : new ArrayList<>(data);

    for (int i = 0; i < a.size(); i++)
        for (int j = i; j < a.size(); j++)
            collect(a.get(i), a.get(j));
}

Answer 2

Вы можете использовать метод listIterator для списка, возвращающего объект ListIterator, который будет проходить по вашему списку по порядку.Наиболее важно, что метод может быть вызван с необязательным параметром index для запуска в заданной точке списка.Также ListIterator удобно знает свой текущий индекс, который мы можем использовать для установки нашего второго итератора.

Пример может выглядеть так:

List<Integer> list = new LinkedList<Integer>(Arrays.asList(1, 2, 3));

ListIterator<Integer> i = list.listIterator();

while (i.hasNext())
{
    ListIterator<Integer> j = list.listIterator(i.nextIndex());
    int iV = i.next();
    while (j.hasNext())
    {
        collect(iV, j.next());
    }
}

, который вызывает collect дляследующие пары:

1, 1
1, 2
1, 3
2, 2
2, 3
3, 3

Как правильно сказано, это оставляет нам вызов list.listIterator(i.nextIndex()), имеющий потенциальную сложность O (n) .

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