Efficient way to divide a list into lists of n siz

问题:

I have an array, which I want to divide into smaller arrays of n size, and perform an operation on each. My current method of doing this is

implemented with ArrayLists 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, 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.

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

回答2:

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/

回答3:

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
    }

回答4:

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 = newArrayList();
    Iterator<T> i = in.iterator();
    while (i.hasNext()) {
        List<T> list = newArrayList();
        for (int j=0; i.hasNext() && j<size; j++) {
            list.add(i.next());
        }
        lists.add(list);
    }
    return lists;
}

回答5:

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

回答6:

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

回答7:

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

回答8:

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}

回答9:

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 wort with the stream for example collect or map if it matches your purpose.

回答10:

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

回答11:

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]

回答12:

What about

Arrays.copyOfRange( original, from, to )

?

回答13:

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