连接不可变列表

Question

我有一个List<ImmutableList<T>>。我想把它压平成一个 ImmutableList<T>，它是所有内部 ImmutableLists 的串联。这些列表可能很长，所以我不希望此操作执行所有元素的副本。要展平的ImmutableLists个数会比较少，所以lookup在ImmutableLists个数中线性就好了。我强烈希望连接 return 一个 Immutable 集合。我需要它 return 一个可以在随机位置访问的 List。

有没有办法在 Guava 中做到这一点？

有 Iterables.concat，但 return 是 Iterable。再次将其转换为 ImmutableList 将与列表 IIUC 的大小成线性关系。

Answer 1

不确定仅使用 Guava classes 是否可行，但似乎不难实现，如下所示：

package com.google.common.collect;

import java.util.List;

public class ConcatenatedList<T> extends ImmutableList<T> {

    private final List<ImmutableList<T>> underlyingLists;

    public ConcatenatedList(List<ImmutableList<T>> underlyingLists) {
        this.underlyingLists = underlyingLists;
    }

    @Override
    public T get(int index) {
        for (ImmutableList<T> list : underlyingLists) {
            if (index < list.size()) return list.get(index);
            index -= list.size();
        }
        throw new IndexOutOfBoundsException();
    }

    @Override
    boolean isPartialView() {
        for (ImmutableList<T> list : underlyingLists) {
            if (list.isPartialView()) return true;
        }
        return false;
    }

    @Override
    public int size() {
        int result = 0;
        for (ImmutableList<T> list : underlyingLists) {
            result += list.size();
        }
        return result;
    }
}

注意包声明，需要这样才能访问 Guava 的 ImmutableList 包访问构造函数。请注意，此实现可能会与未来版本的 Guava 中断，因为构造函数不是 API 的一部分。同样如 ImmutableList 的 javadoc 和评论中所述，此 class 不打算由原始库作者进行子class。但是，没有充分的理由不在您控制的应用程序中使用它，并且与其他答案中建议的 MultiListView 相比，它具有在类型签名中表达不变性的额外好处。

Answer 2

根据设计，Guava 不允许您定义自己的 ImmutableList 实现（如果允许，则无法强制其不可变）。通过在 com.google.common.collect 包中定义您自己的 class 来解决这个问题是一个糟糕的想法。您违反了 Guava 库的承诺，运行坚定地处于“未定义行为”领域，没有任何好处。

查看您的要求：

您需要在亚线性时间内连接 n ImmutableList 个实例的元素。
您希望结果也是不可变的。
您需要结果来实现 List，并且可能是 ImmutableList。

如您所知，您可以通过调用 Iterables.concat() 获得前两个项目符号，但如果您需要 O(1) 随机访问 List，这将无法解决问题。没有由一系列 List 支持的标准 List 实现（在 Java 或 Guava 中），但是您自己创建一个很简单：

/**
 * A constant-time view into several {@link ImmutableList} instances, as if they were
   concatenated together. Since the backing lists are immutable this class is also
   immutable and therefore thread-safe.
 * 
 * More precisely, this class provides O(log n) element access where n is the number of
 * input lists. Assuming the number of lists is small relative to the total number of
 * elements this is effectively constant time.
 */
public class MultiListView<E> extends AbstractList<E> implements RandomAccess {
  private final ImmutableList<ImmutableList<E>> elements;
  private final int size;
  private final int[] startIndexes;

  private MutliListView(Iterable<ImmutableList<E>> elements) {
    this.elements = ImmutableList.copyOf(elements);
    startIndexes = new int[elements.size()];
    int currentSize = 0;
    for (int i = 0; i < this.elements.size(); i++) {
      List<E> ls = this.elements.get(i);
      startIndexes[i] = ls.size();
      currentSize += ls.size();
    }
  }

  @Override
  public E get(int index) {
    checkElementIndex(index, size);
    int location = Arrays.binarySearch(startIndexes, index);
    if (location >= 0) {
      return elements.get(location).get(0);
    }
    location = (~location) - 1;
    return elements.get(location).get(index - startIndexes[location]);
  }

  @Override
  public int size() {
    return size;
  }

  // The default iterator returned by AbstractList.iterator() calls .get()
  // which is likely slower than just concatenating the backing lists' iterators
  @Override
  public Iterator<E> iterator() {
    return Iterables.concat(elements).iterator();
  }

  public static MultiListView<E> of(Iterable<ImmutableList<E>> lists) {
    return new MultiListView<>(lists);
  }

  public static MultiListView<E> of(ImmutableList<E> ... lists) {
    return of(Arrays.asList(lists));
  }
}

这个 class 是不可变的，即使它没有扩展 ImmutableList 或 ImmutableCollection，因此不需要它实际扩展 ImmutableList.

关于这样的class是否应该由Guava提供；您可以在关联的 issue 中提出您的理由，但目前尚不存在的原因是很少有用户真正需要它。在使用 MultiListView.

之前，请确保没有合理的方法可以用 Iterable 解决您的问题

Answer 3

这里可能是的可读性更好的版本，它可以正确处理空列表并正确填充 startIndexes：

public class ImmutableMultiListView<E> extends AbstractList<E> implements RandomAccess {
  private final ImmutableList<ImmutableList<E>> listOfLists;
  private final int[] startIndexes;

  private final int size;

  private ImmutableMultiListView(List<ImmutableList<E>> originalListOfLists) {
    this.listOfLists =
        originalListOfLists.stream().filter(l -> !l.isEmpty()).collect(toImmutableList());
    startIndexes = new int[listOfLists.size()];
    int sumSize = 0;
    for (int i = 0; i < listOfLists.size(); i++) {
      List<E> list = listOfLists.get(i);
      sumSize += list.size();
      if (i < startIndexes.length - 1) {
        startIndexes[i + 1] = sumSize;
      }
    }
    this.size = sumSize;
  }

  @Override
  public E get(int index) {
    checkElementIndex(index, size);
    int location = Arrays.binarySearch(startIndexes, index);
    if (location >= 0) {
      return listOfLists.get(location).get(0);
    } else {
      // See Arrays#binarySearch Javadoc:
      int insertionPoint = -location - 1;
      int listIndex = insertionPoint - 1;
      return listOfLists.get(listIndex).get(index - startIndexes[listIndex]);
    }
  }

  @Override
  public int size() {
    return size;
  }

  // AbstractList.iterator() calls .get(), which is slower than just concatenating
  // the backing lists' iterators
  @Override
  public Iterator<E> iterator() {
    return Iterables.concat(listOfLists).iterator();
  }

  public static <E> ImmutableMultiListView<E> of(List<ImmutableList<E>> lists) {
    return new ImmutableMultiListView<>(lists);
  }
}

连接不可变列表

Concatenating ImmutableLists

guava

java-7