Forma eficiente de dividir una lista en listas de n tamaño

Question

Tengo una matriz, que quiero dividir en matrices más pequeñas de n tamaño, y realizar una operación en cada una. Mi método actual de hacer esto es

implementar con ArrayLists en Java (cualquier pseudocódigo hará)

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

donde A es la lista, n es el tamaño de las listas deseadas

creo de esta manera, se está tomando demasiado tiempo cuando se trabaja con listas considerablemente grandes (de hasta 1 millón de tamaño), así que estoy tratando de descubrir qué sería más eficiente.

Answer 1

Usted querrá hacer algo que hace uso de List.subList(int, int) vistas en lugar de copiar cada sublista. Para hacer esto con mucha facilidad, utilice Guava 's Lists.partition(List, int) método:

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

Tenga en cuenta que esto, como muchas cosas, no es muy eficiente con un List que no es RandomAccess (tales como LinkedList).

Answer 2

Si se trata de matrices, puede usar System.arraycopy() para eso.

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} 

Answer 3

¿Qué hay de

Arrays.copyOfRange(original, from, to) 

?

Answer 4

Bueno, yo mismo escribí uno antes de ver la respuesta de ColinD (+1) y usar Guava definitivamente es el camino a seguir. Fue demasiado divertido dejarlo solo y, por lo tanto, a continuación le ofrecemos una copia de la lista en lugar de vistas, por lo que GUava es definitivamente más eficiente que esto. Quiero poner esta porque era divertido escribir en lugar de sugerir que es tan eficiente:

La prueba Hamcrest (uno de todos modos):

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

El código:

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

Answer 5

Si Estás trabajando con una lista. Utilizo la biblioteca "Apache Commons Collections 4". Tiene un método de partición en la clase ListUtils:

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

Este método es una adaptación de http://code.google.com/p/guava-libraries/

Answer 6

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

Answer 7

acabo implementado una partición de la lista, porque no podía usar una biblioteca.

así que quiero compartir mi código aquí:

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

Y la prueba de la unidad basada en 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)); 
    } 
} 

Answer 8

Por ejemplo:

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 
    }