如何有效地对抽象列表进行嵌套迭代？

Question

我正在尝试复制 "walking the upper diagonal matrix of the self Cartesian product" 的典型构造，并将列表作为源。通俗地说，如果我有一个数组 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:

和不是所有可能的对（可以用两个简单的循环完成）。

Answer 1

您可以对返回 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）并复制您的数据在这样的列表中应该不是这样。

Answer 2

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

如何有效地对抽象列表进行嵌套迭代？

How to do a nested iteration over an abstract list efficiently?

java

iteration

idioms

list

cartesian-product