Efficient way to divide a list into lists of n size
JavaArraylistPartitioningJava Problem Overview
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.
Java Solutions
Solution 1 - Java
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).
Solution 2 - Java
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
}
Solution 3 - Java
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/
Solution 4 - Java
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
Solution 5 - Java
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;
}
Solution 6 - Java
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;
}
Solution 7 - Java
// 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());
Solution 8 - Java
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));
}
}
Solution 9 - Java
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.
Solution 10 - Java
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());
Solution 11 - Java
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}
Solution 12 - Java
Here is a way to partition a List
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);
}
Solution 13 - Java
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]
Solution 14 - Java
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
Solution 15 - Java
What about
Arrays.copyOfRange( original, from, to )
?