División de Arrays

La principal característica del nuevo Fork/Join de JavaSE 1.7 consiste en dividir una estructura de datos en partes, más o menos iguales, para ejecutar operaciones en paralelo con cada parte, y agregar los resultados obtenidos al final. Sigue la idea "Divide y vencerás".

La mayoría, por no decir todos, los ejemplos que se encuentran se limitan a dividir por la mitad, cuando lo más eficiente sería dividir en función del número de procesadores existentes.

Por eso quiero proponer un problema (que no tiene nada que ver con el uso de Fork/Join), que consiste en encontrar una manera eficiente y clara de dividir un array en partes, aproximadamente iguales.

Dada una clase como la siguiente: 

public class SplitArray<T> {

    private final T[] array;

    public SplitArray(final T[] array) {

    if (array == null || array.length == 0) {

            throw new IllegalArgumentException("array cannot be null or empty");

        }

    this.array = Arrays.copyOf(array, array.length);

    }  

    public List<T[]> splitArray(final int divisions) {

        final List<T[]> result;

        // aquí va el código que se busca

        return result;

    }

}

se trata de encontrar un código que devuelva el resultado deseado.

El parámetro divisions indica el número de divisiones deseadas.

Comments

[choces]

Se puede usar un test como el que sigue, para ayudar al desarrollo:

public class SplitTest {
public static void main(String[] args) {
final Integer[] divisions = {-4, 0, 4, 16, 17};
System.out.println("split array");
final SplitArray<Integer> splitArray = new SplitArray<Integer>(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16});
for (int i = 0; i < divisions.length; i++) {
System.out.println("divisions= " + divisions[i]);
for (Iterator<Integer[]> it = splitArray.splitArray(divisions[i]).iterator(); it.hasNext();) {
System.out.println("sub array: " + Arrays.toString(it.next()));
}
}
}

Si el código no pasa el test...

[PaMaY]

A ver si esto se aproxima:

if( divisions <= 0 ) result = new ArrayList<T[]>();
else
{
result = new ArrayList<T[]>();
if( divisions > array.length ) result.add(array);
else
{
final int tamanyo = array.length;
final int elementos = array.length / divisions;
int contador = 0;
do
{
T[] tmp = Arrays.copyOfRange(this.array, contador, contador + elementos);
result.add(tmp);

contador += elementos;
if( contador > array.length ) contador = array.length;
}
while( contador < array.length );

}
}

Saludos

[choces]

Sí, se aproxima mucho (muchísimo), pero solo funciona perfectamente con divisions > 0 al pasar el test.
Para valores negativos o cero no da ningún resultado.

Tal vez no estaba clara la especificación; la amplío ahora:

* En caso de valores negativos, el resultado debe ser el mismo que si fuesen positivos.
* En caso de cero, debe devolver el array, lo mismo que si divisions es mayor que el tamaño del array.

La idea general es que nunca devuelva un null, ni una lista vacía.

De todos modos, has resuelto la clave del problema a la perfección :)

[jcarmonaloeches]

Me dejas con la piel de gallina @choces :=)

[choces]

¡Bah!, seguro que tienes frío ;D
Empieza a abrigarte, que ya llega la nieve ;)

[choces]

Este es el método que implemento, y que pasa el test sin problemas:

public List<T[]> splitArray(final int divisions) {
final List<T[]> result;
final int size = array.length;
final int div = divisions < 0 ? -divisions : divisions;
if (div > size || div == 0) {
result = new ArrayList<>(2);
result.add(array);
} else {
result = new ArrayList<>(2 * div);
final int splits = size / div;
final int end = div - 1;
int index = 0;
for (int i = 0; i < div; i++) {
result.add(Arrays.copyOfRange(array, index, i == end ? size : index + splits));
index += splits;
}
}
return result;
}

[choces]

Se podría aplicar el mismo criterio si se trata de particionar una lista:

public class SplitList<T> {

private transient final List<T> list;

public SplitList(final List<T> list) {
if (list == null || list.isEmpty()) {
throw new IllegalArgumentException("list cannot be null or empty");
}
this.list = new ArrayList<>(list);
}

public List<List<T>> splitList(final int divisions) {
final List<List<T>> result;
final int size = list.size();
final int div = divisions < 0 ? -divisions : divisions;
if (div > size || div == 0) {
result = new ArrayList<>(2);
result.add(list);
} else {
result = new ArrayList<>(2 * div);
final int splits = size / div;
final int end = div - 1;
int index = 0;
for (int i = 0; i < div; i++) {
result.add(list.subList(index, i == end ? size : index + splits));
index += splits;
}
}
return result;
}
}