Moyen efficace de diviser une liste en listes de taille n

J’ai un tableau que je veux diviser en plus petits tableaux de taille n et effectuer une opération sur chacun. Ma méthode actuelle est de

implémenté avec ArrayLists en Java (n’importe quel pseudocode le fera)

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

où A est la liste, n est la taille des listes souhaitées

Je pense que cela prend trop de temps lorsque vous travaillez avec des listes très volumineuses (jusqu’à un million de taille), alors j’essaie de déterminer ce qui serait le plus efficace.

Vous voudrez faire quelque chose qui utilise les vues List.subList (int, int) plutôt que de copier chaque sous-liste. Pour faire cela très facilement, utilisez la méthode Listes.partition (Liste, int) de Guava :

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

Notez que cela, comme beaucoup d’autres choses, n’est pas très efficace avec une List qui n’est pas RandomAccess (telle qu’une LinkedList ).

Si vous travaillez avec une liste, j’utilise la bibliothèque ” Apache Commons Collections 4 “. Il a une méthode de partition dans la classe ListUtils:

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

Cette méthode est adaptée de http://code.google.com/p/guava-libraries/

Par exemple:

  int partitionSize = 10; List> partitions = new ArrayList<>(); for (int i=0; i list : partitions) { //Do your stuff on each sub list } 

Eh bien, j’ai écrit moi-même avant de voir la réponse de ColinD (+1) et l’utilisation de Guava est certainement la voie à suivre. C’était trop amusant de partir seul et le tableau ci-dessous vous donne une copie de la liste plutôt que des vues, donc celle de GUava est nettement plus efficace que cela. Je poste ceci parce que c’était amusant d’écrire plutôt que de suggérer que c’est aussi efficace:

Le test de Hamcrest (un de toute façon):

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

Le code:

 public static  Iterable> chunk(Iterable in, int size) { List> lists = newArrayList(); Iterator i = in.iterator(); while (i.hasNext()) { List list = newArrayList(); for (int j=0; i.hasNext() && j 
 public  Iterable> partition(List list, final int batchSize) { assert(batchSize > 0); assert(list != null); assert(list.size() + batchSize <= Integer.MAX_VALUE); //avoid overflow int idx = 0; List> result = new ArrayList>(); 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; } 

Je viens d’implémenter un partitionnement de liste, car je ne pouvais pas utiliser de bibliothèque.

Je veux donc partager mon code ici:

 import java.util.Iterator; import java.util.List; import java.util.NoSuchElementException; public class ListPartitioning implements Iterable> { private final List list; private final int partitionSize; public ListPartitioning(List 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> iterator() { return new ListPartitionIterator(list, partitionSize); } private static class ListPartitionIterator implements Iterator> { private int index = 0; private List listToPartition; private int partitionSize; private List nextPartition; public ListPartitionIterator(List listToPartition, int partitionSize) { this.listToPartition = listToPartition; this.partitionSize = partitionSize; } @Override public boolean hasNext() { return index < listToPartition.size(); } @Override public List 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; } } } 

Et le test unitaire basé sur testng.

 import org.testng.Assert; import org.testng.annotations.Test; import java.util.*; public class ListPartitioningTest { @Test(expectedExceptions = IllegalArgumentException.class) public void nullList() { ListPartitioning lists = new ListPartitioning(null, 1); } @Test(groups = Group.UNIT_TEST, expectedExceptions = IllegalArgumentException.class) public void wrongPartitionSize() { ListPartitioning lists = new ListPartitioning(new ArrayList(), 0); } @Test() public void iteratorTest() { List integers = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15); ListPartitioning listPartitioning = new ListPartitioning(integers, 7); Iterator> partitionIterator = listPartitioning.iterator(); Assert.assertNotNull(partitionIterator); Assert.assertTrue(partitionIterator.hasNext(), "next partition (first)"); List 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 integers = Arrays.asList(1); ListPartitioning listPartitioning = new ListPartitioning(integers, 2); Iterator> partitionIterator = listPartitioning.iterator(); List partition = partitionIterator.next(); partition = partitionIterator.next(); } @Test(expectedExceptions = IllegalStateException.class) public void removeWithoutNext() { List integers = new ArrayList(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)); ListPartitioning listPartitioning = new ListPartitioning(integers, 7); Iterator> partitionIterator = listPartitioning.iterator(); partitionIterator.remove(); } @Test() public void remove() { List integers = new ArrayList(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)); ListPartitioning listPartitioning = new ListPartitioning(integers, 7); Iterator> partitionIterator = listPartitioning.iterator(); partitionIterator.next(); partitionIterator.next(); partitionIterator.remove(); Assert.assertTrue(partitionIterator.hasNext(), "next partition "); List 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)); } } 

Si vous ne voulez pas utiliser une bibliothèque, voici ma solution

1.Pour partitionner en N parties égales:

 private  List> nPartition(List 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. Pour partitionner en ensembles de N éléments:

 private  List> nPartition(List 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()); } 

En action ici: https://ideone.com/QiQnbE

Si vous traitez avec des tableaux, vous pouvez utiliser System.arraycopy () pour cela.

  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} 

Qu’en est-il de

 Arrays.copyOfRange( original, from, to ) 

?

Comme vous souhaitez optimiser vos performances, vous devez utiliser un stream parallèle plutôt qu’une boucle for. De cette façon, vous pouvez utiliser plusieurs threads.

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

Vous pouvez également utiliser d’autres méthodes pour recueillir le stream, par exemple collecter ou cartographier si cela correspond à votre objective.

Voici un moyen de partitionner une liste en un tableau de sous-listes, ce qui garantit que tous les éléments sauf la dernière ont le même nombre d’éléments:

 static  List[] split(List 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); } 

Si vous voulez garantir la taille du tableau numPartitions vous voulez:

 static  List[] split(List 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); }