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.

[Spliterator](https://docs.oracle.com/javase/8/docs/api/java/util/Spliterator.html) is a mystery. — AlikElzin-kilaka, Nov 28 '18 at 18:36
For java 8 here is a sample article along with the performace of each method: https://e.printstacktrace.blog/divide-a-list-to-lists-of-n-size-in-Java-8/ — Brooklyn99, Jan 03 '20 at 20:57
Please stop using *toReturn*. It has no meaning. Might as well use *r* or *x*. Name it "partition" or "shard" or something meaningful. — Buffalo, Feb 10 '22 at 11:05

score 123 · Accepted Answer · edited Mar 09 '22 at 17:14

123

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).

edited Mar 09 '22 at 17:14

Maow

661
5
8

answered Apr 28 '11 at 20:56

ColinD

108,630
30
201
202

2

There is also `Iterables.partition(Iterable, int)` if you have an `Iterable` instead of a `List` – Krease Dec 16 '15 at 00:16
The last link has changed, I think is this one https://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/Lists.html#partition(java.util.List, int) – bogdan.rusu Dec 20 '16 at 09:44
1

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? – user506591 Jan 27 '17 at 00:40
1

@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. – ColinD Jan 27 '17 at 17:52

score 42 · Answer 2 · answered Jan 27 '17 at 16:32

42

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
    }

answered Jan 27 '17 at 16:32

BrownRecluse

1,638
1
16
19

3

Definitely best answer – Anatolii Shuba Oct 05 '17 at 23:22
Thanks for the best solution. – pujan kc Jan 06 '21 at 11:24

score 22 · Answer 3 · answered Nov 03 '15 at 09:50

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/

Anshu Srivastava · Answer 4 · 2018-06-01T16:19:24.860

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

score 5 · Answer 5 · answered Jun 09 '20 at 05:25

// 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());

score 4 · Answer 6 · answered Jul 14 '16 at 05:56

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

score 4 · Answer 7 · edited Jul 02 '19 at 10:13

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

score 1 · Answer 8 · answered Aug 11 '16 at 11:38

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

L. Schilling · Answer 9 · 2021-09-23T13:52:22.007

1

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.

edited Sep 23 '21 at 13:52

answered Jun 08 '18 at 14:02

L. Schilling

79
8

1

Note that `Lists.partition()` seems to be a Google Guava specific implementation. – Arman Jan 03 '22 at 21:32

score 1 · Answer 10 · edited Nov 12 '18 at 09:22

1

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

edited Nov 12 '18 at 09:22

Mark

5,089
2
20
31

answered Nov 12 '18 at 08:34

Yong

21
1

score 0 · Answer 11 · answered Jun 13 '18 at 15:11

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

`If you want to guarantee numPartitions array size ` What does this mean? — Koray Tugay, Nov 30 '18 at 14:31

score 0 · Answer 12 · answered Nov 29 '18 at 13:28

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]

score 0 · Answer 13 · answered Apr 28 '11 at 20:52

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}

score 0 · Answer 14 · answered Apr 22 '22 at 15:53

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

polarfish · Answer 15 · 2022-12-07T10:31:08.840

# 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]]
[]                    > []

score 0 · Answer 16 · answered Apr 03 '23 at 13:14

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]]

score -1 · Answer 17 · answered Apr 28 '11 at 21:07

-1

What about

Arrays.copyOfRange( original, from, to )

?

answered Apr 28 '11 at 21:07

Omnaest

3,096
1
19
18

What about the items after `to`? – Koray Tugay Nov 30 '18 at 14:34

Efficient way to divide a list into lists of n size

17 Answers17

Linked

Related