Efficient way to divide a list into lists of n size

Question

I have an ArrayList, which I want to divide into smaller List objects of n size, and perform an operation on each. My current method of doing this is implemented with ArrayList objects in Java. Any pseudocode will do.

    for (int i = 1; i <= Math.floor((A.size() / n)); i++) {
            ArrayList temp = subArray(A, ((i * n) - n),
                    (i * n) - 1);
            // do stuff with temp
        }

    private ArrayList<Comparable> subArray(ArrayList A, int start,
                int end) {
            ArrayList toReturn = new ArrayList();
            for (int i = start; i <= end; i++) {
                toReturn.add(A.get(i));
            }
            return toReturn;
        }

where A is the list and n is the size of the desired lists

I believe this way is taking too much time when working with considerably large lists of up to 1 million in size, so I'm trying to figure out what would be more efficient.

Byers

Spliterator is a mystery. – Anaclitic

For java 8 here is a sample article along with the performace of each method: e.printstacktrace.blog/… – Lissettelissi

Please stop using toReturn. It has no meaning. Might as well use r or x. Name it "partition" or "shard" or something meaningful. – Chericheria

Answer 1

You'll want to do something that makes use of List.subList(int, int) views rather than copying each sublist. To do this really easily, use Guava's Lists.partition(List, int) method:

List<Foo> foos = ...
for (List<Foo> partition : Lists.partition(foos, n)) {
  // do something with partition
}

Note that this, like many things, isn't very efficient with a List that isn't RandomAccess (such as a LinkedList).

Elegancy

There is also Iterables.partition(Iterable, int) if you have an Iterable instead of a List – Arruda

The last link has changed, I think is this one google.github.io/guava/releases/19.0/api/docs/com/google/common/…, int) – Bedfellow

I have a quick question about lists.partition what happens if the input list size is less than the expected size of sublist. Does this method handle that or client needs to validate that? – Sikkim

@user506591: Updated the Javadoc link. The last list in the partition can be smaller than the partition size. So in the case where the entire original list is smaller, the partition will contain a single list with all of its elements. – Elegancy

Answer 2

For example:

    int partitionSize = 10;
    List<List<String>> partitions = new ArrayList<>();

    for (int i=0; i<yourlist.size(); i += partitionSize) {
        partitions.add(yourlist.subList(i, Math.min(i + partitionSize, yourlist.size())));
    }

    for (List<String> list : partitions) {
        //Do your stuff on each sub list
    }

Waiwaif

Definitely best answer – Japan

Thanks for the best solution. – Backstretch

Well, the moment I feel LeetCode stuff is useful. Thanks – Bushelman

Answer 3

If you are working with a list I use the "Apache Commons Collections 4" library. It has a partition method in the ListUtils class:

...
int targetSize = 100;
List<Integer> largeList = ...
List<List<Integer>> output = ListUtils.partition(largeList, targetSize);

This method is adapted from http://code.google.com/p/guava-libraries/

Lannielanning

Answer 4

If you don't want to use a library, here's my solution

1.To partition in N equal parts:

private <T> List<List<T>> nPartition(List<T> objs, final int N) {
    return new ArrayList<>(IntStream.range(0, objs.size()).boxed().collect(
            Collectors.groupingBy(e->e%N,Collectors.mapping(e->objs.get(e), Collectors.toList())
                    )).values());
}

2. To partition in sets of N items:

private <T> List<List<T>> nPartition(List<T> objs, final int N) {
    return new ArrayList<>(IntStream.range(0, objs.size()).boxed().collect(
            Collectors.groupingBy(e->e/N,Collectors.mapping(e->objs.get(e), Collectors.toList())
                    )).values());
    }

In action here: https://ideone.com/QiQnbE

Innovation

Answer 5

// Testing data

List<Integer> list = Arrays.asList(0, 1, 2,     3, 4, 5,    6, 7, 8,    9);
int n = 3;

// One line(statement) with java 8 stream and list.subList

List<List<Integer>> partitions = IntStream.range(0, list.size())
    .filter(i -> i % n == 0)
    .mapToObj(i -> list.subList(i, Math.min(i + n, list.size() )))
    .collect(Collectors.toList());

Asta

Answer 6

Well i wrote one myself before i saw ColinD's answer (+1) and using Guava is definitely the way to go. It was too much fun to leave alone and so the below gives you a copy of the list rather than views so GUava's is definitely more efficient than this. I'm posting this because it was fun to write rather than suggesting it is as efficient:

The Hamcrest test (one of anyway):

assertThat(chunk(asList("a", "b", "c", "d", "e"), 2), 
           equalTo(asList(asList("a", "b"), asList("c", "d"), asList("e"))));

The code:

public static <T> Iterable<Iterable<T>> chunk(Iterable<T> in, int size) {
    List<Iterable<T>> lists = new ArrayList();
    Iterator<T> i = in.iterator();
    while (i.hasNext()) {
        List<T> list = new ArrayList();
        for (int j=0; i.hasNext() && j<size; j++) {
            list.add(i.next());
        }
        lists.add(list);
    }
    return lists;
}

Cheung

Answer 7

public <E> Iterable<List<E>> partition(List<E> list, final int batchSize)
{
    assert(batchSize > 0);
    assert(list != null);
    assert(list.size() + batchSize <= Integer.MAX_VALUE); //avoid overflow

    int idx = 0;

    List<List<E>> result = new ArrayList<List<E>>();

    for (idx = 0; idx + batchSize <= list.size(); idx += batchSize) {
        result.add(list.subList(idx, idx + batchSize));
    }
    if (idx < list.size()) {
        result.add(list.subList(idx, list.size()));
    }

    return result;
}

Earthaearthborn

Answer 8

# Java 9
public static <T> List<List<T>> partition(List<T> list, int size) {
    return Stream.iterate(0, i -> i <= list.size(), i -> i + size)
        .map(i -> list.subList(i, Math.min(i + size, list.size())))
        .filter(Predicate.not(List::isEmpty))
        .toList();
}

testing partition(list, 3)

[1, 2, 3, 4, 5]       > [[1, 2, 3], [4, 5]]
[1, 2, 3, 4, 5, 6]    > [[1, 2, 3], [4, 5, 6]]
[1, 2, 3, 4, 5, 6, 7] > [[1, 2, 3], [4, 5, 6], [7]]
[1]                   > [[1]]
[]                    > []

Carbonado

Answer 9

I just implemented a list partitioning, because I couldn't use a library.

So I want to share my code here:

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class ListPartitioning<T> implements Iterable<List<T>> {

  private final List<T> list;
  private final int partitionSize;

  public ListPartitioning(List<T> list, int partitionSize) {
    if (list == null) {
      throw new IllegalArgumentException("list must not be null");
    }
    if (partitionSize < 1) {
      throw new IllegalArgumentException("partitionSize must be 1 or greater");
    }
    this.list = list;
    this.partitionSize = partitionSize;
  }

  @Override
  public Iterator<List<T>> iterator() {
    return new ListPartitionIterator<T>(list, partitionSize);
  }

  private static class ListPartitionIterator<T> implements Iterator<List<T>> {

    private int index = 0;

    private List<T> listToPartition;
    private int partitionSize;
    private List<T> nextPartition;

    public ListPartitionIterator(List<T> listToPartition, int partitionSize) {
      this.listToPartition = listToPartition;
      this.partitionSize = partitionSize;
    }

    @Override
    public boolean hasNext() {
      return index < listToPartition.size();
    }

    @Override
    public List<T> next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }

      int partitionStart = index;
      int partitionEnd = Math.min(index + partitionSize, listToPartition.size());

      nextPartition = listToPartition.subList(partitionStart, partitionEnd);
      index = partitionEnd;
      return nextPartition;
    }

    @Override
    public void remove() {
      if (nextPartition == null) {
        throw new IllegalStateException("next must be called first");
      }

      nextPartition.clear();
      index -= partitionSize;
      nextPartition = null;
    }
  }
}

And the unit test based on testng.

import org.testng.Assert;
import org.testng.annotations.Test;

import java.util.*;


public class ListPartitioningTest {

  @Test(expectedExceptions = IllegalArgumentException.class)
  public void nullList() {
    ListPartitioning<String> lists = new ListPartitioning<String>(null, 1);
  }

  @Test(groups = Group.UNIT_TEST, expectedExceptions = IllegalArgumentException.class)
  public void wrongPartitionSize() {
    ListPartitioning<String> lists = new ListPartitioning<String>(new ArrayList<String>(), 0);
  }


  @Test()
  public void iteratorTest() {
    List<Integer> integers = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
    ListPartitioning<Integer> listPartitioning = new ListPartitioning<Integer>(integers, 7);
    Iterator<List<Integer>> partitionIterator = listPartitioning.iterator();
    Assert.assertNotNull(partitionIterator);

    Assert.assertTrue(partitionIterator.hasNext(), "next partition (first)");
    List<Integer> partition = partitionIterator.next();
    Assert.assertEquals(partition, Arrays.asList(0, 1, 2, 3, 4, 5, 6));

    Assert.assertTrue(partitionIterator.hasNext(), "next partition (second)");
    partition = partitionIterator.next();
    Assert.assertEquals(partition, Arrays.asList(7, 8, 9, 10, 11, 12, 13));

    Assert.assertTrue(partitionIterator.hasNext(), "next partition (third)");
    partition = partitionIterator.next();
    Assert.assertEquals(partition, Arrays.asList(14, 15));

    Assert.assertFalse(partitionIterator.hasNext());
  }

  @Test(expectedExceptions = NoSuchElementException.class)
  public void noSuchElementException() {
    List<Integer> integers = Arrays.asList(1);
    ListPartitioning<Integer> listPartitioning = new ListPartitioning<Integer>(integers, 2);
    Iterator<List<Integer>> partitionIterator = listPartitioning.iterator();
    List<Integer> partition = partitionIterator.next();
    partition = partitionIterator.next();
  }

  @Test(expectedExceptions = IllegalStateException.class)
  public void removeWithoutNext() {
    List<Integer> integers = new ArrayList<Integer>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
    ListPartitioning<Integer> listPartitioning = new ListPartitioning<Integer>(integers, 7);
    Iterator<List<Integer>> partitionIterator = listPartitioning.iterator();
    partitionIterator.remove();
  }

  @Test()
  public void remove() {
    List<Integer> integers = new ArrayList<Integer>(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
    ListPartitioning<Integer> listPartitioning = new ListPartitioning<Integer>(integers, 7);
    Iterator<List<Integer>> partitionIterator = listPartitioning.iterator();

    partitionIterator.next();
    partitionIterator.next();

    partitionIterator.remove();
    Assert.assertTrue(partitionIterator.hasNext(), "next partition ");
    List<Integer> partition = partitionIterator.next();
    Assert.assertEquals(partition, Arrays.asList(14, 15));

    Assert.assertFalse(partitionIterator.hasNext());

    Assert.assertEquals(integers, Arrays.asList(0, 1, 2, 3, 4, 5, 6, 14, 15));
  }
}

Dehypnotize

Answer 10

Since you want to optimise your performance you should use a parallel stream instead of a for loop. This way you can use multiple threads.

Lists.partition(A, n).parallelStream().forEach({
    //do stuff with temp
});

You can also use other ways to work with the stream for example collect or map if it matches your purpose.

Burgage

Note that Lists.partition() seems to be a Google Guava specific implementation. – Bespatter

Answer 11

One line using Java 8:

IntStream.range(0, list.size() / batchSize + 1)
        .mapToObj(i -> list.subList(i * batchSize,
                Math.min(i * batchSize + batchSize, list.size())))
        .filter(s -> !s.isEmpty()).collect(Collectors.toList());

Caudate

Answer 12

Had I compelled to do this without relying on any 3^rd party library, I'd go with something like

<T> List<List<T>> partitionList(List<T> src, int maxPartitionSize) {
  final List<List<T>> res = new ArrayList<>();

  for (int i = 0; i < src.size(); i++) {
    if (i % maxPartitionSize == 0) {
      res.add(new ArrayList<>());
    }

    res.get(i / maxPartitionSize).add(src.get(i));
  }

  return res;
}

Complete example:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ListPartitionDemo {
  public static void main(String[] args) {
    final List<Integer> toPartition = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
    System.out.println(partitionList(toPartition, 2));
  }

  // public static <T> List<List<T>> partitionList(List<T> src, int maxPartitionSize) { ... }
}

resulting in

[[1, 2], [3, 4], [5, 6], [7, 8], [9]]

Amyamyas

Answer 13

If you are dealing with arrays, you can use System.arraycopy() for that.

 int[] a = {1,2,3,4,5};

 int[] b = new int[2];
 int[] c = new int[3];

 System.arraycopy(a, 0, b, 0, 2); // b will be {1,2}
 System.arraycopy(a, 2, c, 0, 3); // c will be {3,4,5}

Malissa

Answer 14

Here is a way to partition a List into an array of sublists, which ensures all but the last sublist have equal number of elements:

static <T> List<T>[] split(List<T> source, int numPartitions) {
    if (numPartitions < 2)
        return new List[]{source};

    final int sourceSize = source.size(),
        partitions = numPartitions > sourceSize ? sourceSize: numPartitions,
        increments = sourceSize / partitions;

    return IntStream.rangeClosed(0, partitions)
        .mapToObj(i -> source.subList(i*increments, Math.min((i+1)*increments, sourceSize)))
        .toArray(List[]::new);
}

If you want to guarantee numPartitions array size then you want:

static <T> List<T>[] split(List<T> source, int numPartitions) {
    if (numPartitions < 2)
        return new List[]{source};

    final int sourceSize = source.size(),
        partitions = numPartitions > sourceSize ? sourceSize: numPartitions,
        increments = sourceSize / partitions;

    return IntStream.range(0, partitions)
        .mapToObj(i -> source.subList(i*increments, i == partitions-1 ? sourceSize : (i+1)*increments))
        .toArray(List[]::new);
}

Marshallmarshallese

If you want to guarantee numPartitions array size What does this mean? – Criswell

Answer 15

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubListTest
{
    public static void main(String[] args)
    {
        List<String> alphabetNames = new ArrayList<String>();

        // populate alphabetNames array with AAA,BBB,CCC,.....
        int a = (int) 'A';
        for (int i = 0; i < 26; i++)
        {
            char x = (char) (a + i);
            char[] array = new char[3];
            Arrays.fill(array, x);
            alphabetNames.add(new String(array));
        }

        int[] maxListSizes = new int[]
        {
            5, 10, 15, 20, 25, 30
        };

        for (int maxListSize : maxListSizes)
        {
            System.out.println("######################################################");
            System.out.println("Partitioning original list of size " + alphabetNames.size() + " in to sub lists of max size "
                + maxListSize);

            ArrayList<List<String>> subListArray = new ArrayList<List<String>>();
            if (alphabetNames.size() <= maxListSize)
            {
                subListArray.add(alphabetNames);
            }
            else
            {
                // based on subLists of maxListSize X
                int subListArraySize = (alphabetNames.size() + maxListSize - 1) / maxListSize;
                for (int i = 0; i < subListArraySize; i++)
                {
                    subListArray.add(alphabetNames.subList(i * maxListSize,
                        Math.min((i * maxListSize) + maxListSize, alphabetNames.size())));
                }
            }

            System.out.println("Resulting number of partitions " + subListArray.size());

            for (List<String> subList : subListArray)
            {
                System.out.println(subList);
            }
        }
    }
}

Output:

######################################################
Partitioning original list of size 26 in to sub lists of max size 5
Resulting number of partitions 6
[AAA, BBB, CCC, DDD, EEE]
[FFF, GGG, HHH, III, JJJ]
[KKK, LLL, MMM, NNN, OOO]
[PPP, QQQ, RRR, SSS, TTT]
[UUU, VVV, WWW, XXX, YYY]
[ZZZ]
######################################################
Partitioning original list of size 26 in to sub lists of max size 10
Resulting number of partitions 3
[AAA, BBB, CCC, DDD, EEE, FFF, GGG, HHH, III, JJJ]
[KKK, LLL, MMM, NNN, OOO, PPP, QQQ, RRR, SSS, TTT]
[UUU, VVV, WWW, XXX, YYY, ZZZ]
######################################################
Partitioning original list of size 26 in to sub lists of max size 15
Resulting number of partitions 2
[AAA, BBB, CCC, DDD, EEE, FFF, GGG, HHH, III, JJJ, KKK, LLL, MMM, NNN, OOO]
[PPP, QQQ, RRR, SSS, TTT, UUU, VVV, WWW, XXX, YYY, ZZZ]
######################################################
Partitioning original list of size 26 in to sub lists of max size 20
Resulting number of partitions 2
[AAA, BBB, CCC, DDD, EEE, FFF, GGG, HHH, III, JJJ, KKK, LLL, MMM, NNN, OOO, PPP, QQQ, RRR, SSS, TTT]
[UUU, VVV, WWW, XXX, YYY, ZZZ]
######################################################
Partitioning original list of size 26 in to sub lists of max size 25
Resulting number of partitions 2
[AAA, BBB, CCC, DDD, EEE, FFF, GGG, HHH, III, JJJ, KKK, LLL, MMM, NNN, OOO, PPP, QQQ, RRR, SSS, TTT, UUU, VVV, WWW, XXX, YYY]
[ZZZ]
######################################################
Partitioning original list of size 26 in to sub lists of max size 30
Resulting number of partitions 1
[AAA, BBB, CCC, DDD, EEE, FFF, GGG, HHH, III, JJJ, KKK, LLL, MMM, NNN, OOO, PPP, QQQ, RRR, SSS, TTT, UUU, VVV, WWW, XXX, YYY, ZZZ]

Barrows

Answer 16

Based on @BrownRecluse[ response][1], you can implement this method:

public HashMap<Integer,Object> splitListInSubLists(List<? extends Object> originalList, Integer sizeSublist){
    HashMap<Integer,Object> sublistHashMap =  new HashMap<Integer, Object>();
    if ((originalList!=null) && (sizeSublist!=null)) {
        for (int i=0; i<originalList.size(); i += sizeSublist) {
            sublistHashMap.put(i, (Object) originalList.subList(i, Math.min(i + sizeSublist, originalList.size())));
        }
    }
    return sublistHashMap;
}

And this is a example:

// Example - Split original List in sublists
List<String> myLongList = Arrays.asList("a","b","c","d","e","f","g","h");
        
HashMap<Integer, Object> sublists = splitListInSubLists(myLongList , 3);
            
for (Object sublist : sublists.values()) {// Iterate
    List<String> mySublist= (List<String>) sublist;
       // Your code ...
}

,,, 
  [1]: https://stackoverflow.com/users/5143356/brownrecluse

Asthenopia

Answer 17

The JEP 461: Stream Gatherers Java 22 preview language feature adds built-in support for partitioning a stream into lists of a given size. This can be used to partition the elements of your List and then perform your operation on each partition.

// Processes each of the following sub-lists: [[0, 1, 2], [3, 4, 5], [6]]
Stream<List<Integer>> stream = List.of(0, 1, 2, 3, 4, 5, 6).stream()
        .gather(Gatherers.windowFixed(3))
        .forEach((List<Integer> window) -> {
            // Do stuff with the window
        });

This uses the new Stream.gather method with the new built-in Gatherers.windowFixed gatherer to convert the Stream<T> of elements from the List to a Stream<List<T>>.

Javadocs

Gatherer:

An intermediate operation that transforms a stream of input elements into a stream of output elements, optionally applying a final action when the end of the upstream is reached. […]

[…]

There are many examples of gathering operations, including but not limited to: grouping elements into batches (windowing functions); de-duplicating consecutively similar elements; incremental accumulation functions (prefix scan); incremental reordering functions, etc. The class Gatherers provides implementations of common gathering operations.

Stream.gather:

Returns a stream consisting of the results of applying the given gatherer to the elements of this stream.

Gatherers.windowFixed

Returns a Gatherer that gathers elements into windows -- encounter-ordered groups of elements -- of a fixed size. If the stream is empty then no window will be produced. The last window may contain fewer elements than the supplied window size.

Example:

// will contain: [[1, 2, 3], [4, 5, 6], [7, 8]]
List<List<Integer>> windows =
    Stream.of(1,2,3,4,5,6,7,8).gather(Gatherers.windowFixed(3)).toList();

Kickapoo

Answer 18

What about

Arrays.copyOfRange( original, from, to )

?

Acetylate

What about the items after to? – Criswell