使用 Lists.partition 或 Iterable.partition 将集合拆分为子集

Question

我想知道将集合分成子集的有效方法是什么？

Iterable<List<Long>> partitions = Iterables.partition(numbers, 10);

或者

List<List<Long>> partitions = Lists.partition(numbers, 10);

时间复杂度有什么区别？

谢谢

Answer 1

我们看一下内部实现

可迭代对象的方法partition()

529  public static <T> Iterable<List<T>> partition(final Iterable<T> iterable, final int size) {
530    checkNotNull(iterable);
531    checkArgument(size > 0);
532    return new FluentIterable<List<T>>() {
533      @Override
534      public Iterator<List<T>> iterator() {
535        return Iterators.partition(iterable.iterator(), size);
536      }
537    };
538  }

列表的方法partition()

681  public static <T> List<List<T>> partition(List<T> list, int size) {
682    checkNotNull(list);
683    checkArgument(size > 0);
684    return (list instanceof RandomAccess)
685        ? new RandomAccessPartition<T>(list, size)
686        : new Partition<T>(list, size);
687  }

在上面的 2 个实现中，如果您分析代码，Lists检查list instanceof RandomAccess是否为 true，则使用 RandomAccess Interface 来评估分区。

现在，如果我们看到RandomAccess 的文档：

公共接口 RandomAccess
Marker 接口由 List 实现使用，以指示它们支持快速（通常是恒定时间）随机访问。该接口的主要目的是允许通用算法改变其行为，以便在应用于随机或顺序访问列表时提供良好的性能。

所以，我认为后者的性能更好。

list如果我们的不是接口实例怎么办RandomAccess？

Lists用于执行分区的核心类（源码）

689  private static class Partition<T> extends AbstractList<List<T>> {
690    final List<T> list;
691    final int size;
692
693    Partition(List<T> list, int size) {
694      this.list = list;
695      this.size = size;
696    }
697
698    @Override
699    public List<T> get(int index) {
700      checkElementIndex(index, size());
701      int start = index * size;
702      int end = Math.min(start + size, list.size());
703      return list.subList(start, end);
704    }
705
706    @Override
707    public int size() {
708      return IntMath.divide(list.size(), size, RoundingMode.CEILING);
709    }
710
711    @Override
712    public boolean isEmpty() {
713      return list.isEmpty();
714    }
715  }

Iterators以及用于执行分区的核心类（ source）

605  private static <T> UnmodifiableIterator<List<T>> partitionImpl(
606      final Iterator<T> iterator, final int size, final boolean pad) {
607    checkNotNull(iterator);
608    checkArgument(size > 0);
609    return new UnmodifiableIterator<List<T>>() {
610      @Override
611      public boolean hasNext() {
612        return iterator.hasNext();
613      }
614      @Override
615      public List<T> next() {
616        if (!hasNext()) {
617          throw new NoSuchElementException();
618        }
619        Object[] array = new Object[size];
620        int count = 0;
621        for (; count < size && iterator.hasNext(); count++) {
622          array[count] = iterator.next();
623        }
624        for (int i = count; i < size; i++) {
625          array[i] = null; // for GWT
626        }
627
628        @SuppressWarnings("unchecked") // we only put Ts in it
629        List<T> list = Collections.unmodifiableList(
630            (List<T>) Arrays.asList(array));
631        return (pad || count == size) ? list : list.subList(0, count);
632      }
633    };
634  }

现在如果我们分析最后两个代码，如果不进行全面分析，任何人都很难找出哪个更好。但是，我们可以说，如果我们的列表是RandomAccess接口的实例，那么肯定Lists.partition(lists, pivot);会更快。