Efficient way to divide a list into lists of n size

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.

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

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
    }

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/

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

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

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

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

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

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

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.

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}

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

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]

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

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

What about

Arrays.copyOfRange( original, from, to )

?