Split a set to sub sets using Lists.partition or Iterable.partition

Question

I was wondering what is the efficient way to split a set into sub sets?

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

OR

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

What is the difference in Time Complexity?

Thanks

Answer 1

Let's look at the inner implementation

method partition() for iterables

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  }

method partition() for Lists

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  }

In the above 2 implementations, if you analyse the code, Lists checks for list instanceof RandomAccess and if it's true, then RandomAccess Interface is used to evaluate the partition.

Now if we see the documentation of RandomAccess:

public interface RandomAccess
Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

So, I guess the latter have better performance.

---

What if our list isn't an instance of RandomAccess interface?

The core class used by Lists to perform partition (source)

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  }

and the core class used by Iterators to perform partition(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  }

Now if we analyze the last 2 codes, it's really not easy for anyone to figure out which would be better without doing comprehensive analysis. However, we can say that if our list is an instance of RandomAccess interface, then definitely Lists.partition(lists, pivot); is faster.