División de lista en sublistas a lo largo de los elementos

Tengo esta lista ( List ):

 ["a", "b", null, "c", null, "d", "e"] 

Y me gustaría algo como esto:

 [["a", "b"], ["c"], ["d", "e"]] 

En otras palabras, quiero dividir mi lista en sublistas usando el valor null como separador, para obtener una lista de listas ( List<List> ). Estoy buscando una solución Java 8. Lo he intentado con Collectors.partitioningBy pero no estoy seguro de que sea lo que estoy buscando. ¡Gracias!

La única solución que se me ocurre por el momento es implementar tu propio coleccionista personalizado.

Antes de leer la solución, quiero agregar algunas notas sobre esto. Tomé esta pregunta más como un ejercicio de progtwigción, no estoy seguro si se puede hacer con un flujo paralelo.

Por lo tanto, debe tener en cuenta que se romperá silenciosamente si la tubería se ejecuta en paralelo .

Este no es un comportamiento deseable y debe evitarse . Es por eso que arrojo una excepción en la parte del combinador (en lugar de (l1, l2) -> {l1.addAll(l2); return l1;} ), ya que se usa en paralelo cuando se combinan las dos listas, para que tenga una excepción en lugar de un resultado incorrecto.

Además, esto no es muy eficiente debido a la copia de listas (aunque utiliza un método nativo para copiar la matriz subyacente).

Así que aquí está la implementación del recostackdor:

 private static Collector>, List>> splitBySeparator(Predicate sep) { final List current = new ArrayList<>(); return Collector.of(() -> new ArrayList>(), (l, elem) -> { if (sep.test(elem)) { l.add(new ArrayList<>(current)); current.clear(); } else { current.add(elem); } }, (l1, l2) -> { throw new RuntimeException("Should not run this in parallel"); }, l -> { if (current.size() != 0) { l.add(current); return l; } ); } 

Y cómo usarlo:

 List> ll = list.stream().collect(splitBySeparator(Objects::isNull)); 

Salida:

 [[a, b], [c], [d, e]] 

Como la respuesta de Joop Eggen está fuera , parece que se puede hacer en paralelo (¡dale crédito por eso!). Con eso, reduce la implementación del recostackdor personalizado a:

 private static Collector>, List>> splitBySeparator(Predicate sep) { return Collector.of(() -> new ArrayList>(Arrays.asList(new ArrayList<>())), (l, elem) -> {if(sep.test(elem)){l.add(new ArrayList<>());} else l.get(l.size()-1).add(elem);}, (l1, l2) -> {l1.get(l1.size() - 1).addAll(l2.remove(0)); l1.addAll(l2); return l1;}); } 

que deja el párrafo sobre el paralelismo un poco obsoleto, sin embargo lo dejo, ya que puede ser un buen recordatorio.


Tenga en cuenta que Stream API no siempre es un sustituto. Hay tareas que son más fáciles y más adecuadas utilizando las transmisiones y hay tareas que no lo son. En su caso, también podría crear un método de utilidad para eso:

 private static  List> splitBySeparator(List list, Predicate predicate) { final List> finalList = new ArrayList<>(); int fromIndex = 0; int toIndex = 0; for(T elem : list) { if(predicate.test(elem)) { finalList.add(list.subList(fromIndex, toIndex)); fromIndex = toIndex + 1; } toIndex++; } if(fromIndex != toIndex) { finalList.add(list.subList(fromIndex, toIndex)); } return finalList; } 

y llámalo como List> list = splitBySeparator(originalList, Objects::isNull); .

Se puede mejorar para verificar casos extremos.

Aunque ya hay varias respuestas y una respuesta aceptada, todavía faltan algunos puntos en este tema. En primer lugar, el consenso parece ser que resolver este problema utilizando flujos es simplemente un ejercicio, y que el enfoque convencional para el bucle es preferible. En segundo lugar, las respuestas dadas hasta ahora han pasado por alto un enfoque que utiliza técnicas de matriz o de estilo vectorial que creo que mejora la solución de secuencias considerablemente.

Primero, aquí hay una solución convencional, a los fines de discusión y análisis:

 static List> splitConventional(List input) { List> result = new ArrayList<>(); int prev = 0; for (int cur = 0; cur < input.size(); cur++) { if (input.get(cur) == null) { result.add(input.subList(prev, cur)); prev = cur + 1; } } result.add(input.subList(prev, input.size())); return result; } 

Esto es más sencillo, pero hay un poco de sutileza. Un punto es que una sublista pendiente de prev a cur siempre está abierta. Cuando nos encontramos con null lo cerramos, lo agregamos a la lista de resultados, y avanzamos prev . Después del ciclo cerramos la sublista incondicionalmente.

Otra observación es que se trata de un bucle de índices, no de los valores en sí mismos, por lo tanto, usamos un aritmético for-loop en lugar del bucle mejorado "for-each". Pero sugiere que podemos transmitir utilizando los índices para generar subintervalos en lugar de transmitir los valores y poner la lógica en el recostackdor (como lo hizo la solución propuesta por Joop Eggen ).

Una vez que nos damos cuenta de eso, podemos ver que cada posición de null en la entrada es el delimitador de una sublista: es el extremo derecho de la sublista a la izquierda, y (más uno) es el extremo izquierdo de la sublista para el derecho. Si podemos manejar los casos extremos, esto nos lleva a un enfoque en el que encontramos los índices en los que se producen elementos null , los asignamos a sublistas y recogemos las sublistas.

El código resultante es el siguiente:

 static List> splitStream(List input) { int[] indexes = Stream.of(IntStream.of(-1), IntStream.range(0, input.size()) .filter(i -> input.get(i) == null), IntStream.of(input.size())) .flatMapToInt(s -> s) .toArray(); return IntStream.range(0, indexes.length-1) .mapToObj(i -> input.subList(indexes[i]+1, indexes[i+1])) .collect(toList()); } 

Obtener los índices en los que se produce null es bastante fácil. El obstáculo es agregar -1 a la izquierda y el size en el extremo derecho. He optado por utilizar Stream.of para Stream.of y luego flatMapToInt para aplanarlos. (Probé varios otros enfoques, pero este parecía el más limpio).

Es un poco más conveniente usar arreglos para los índices aquí. En primer lugar, la notación para acceder a una matriz es más agradable que para una lista: indexes[i] vs. indexes.get(i) . En segundo lugar, el uso de una matriz evita el boxeo.

En este punto, cada valor de índice en la matriz (excepto el último) es uno menos que la posición inicial de una sublista. El índice a su derecha inmediata es el final de la sublista. Simplemente transmitimos el conjunto y correlacionamos cada par de índices en una sublista y recostackmos el resultado.

Discusión

El enfoque de secuencias es ligeramente más corto que la versión for-loop, pero es más denso. La versión for-loop es familiar, porque hacemos todo esto en Java todo el tiempo, pero si aún no estás al tanto de lo que se supone que está haciendo este bucle, no es obvio. Puede que tenga que simular algunas ejecuciones de bucle antes de averiguar qué está haciendo prev y por qué la sublista abierta debe cerrarse después del final del bucle. (Inicialmente me olvidé de tenerlo, pero descubrí esto en las pruebas).

El enfoque de flujos es, creo, más fácil de conceptualizar lo que está sucediendo: obtener una lista (o una matriz) que indique los límites entre las sublistas. Es un flujo fácil de dos líneas. La dificultad, como mencioné anteriormente, es encontrar una manera de virar los valores del borde en los extremos. Si hubiera una mejor syntax para hacer esto, por ejemplo,

  // Java plus pidgin Scala int[] indexes = [-1] ++ IntStream.range(0, input.size()) .filter(i -> input.get(i) == null) ++ [input.size()]; 

haría las cosas mucho menos desordenadas. (Lo que realmente necesitamos es una matriz o una lista de comprensión.) Una vez que tenga los índices, es una simple cuestión mapearlos en sublistas reales y recostackrlos en la lista de resultados.

Y, por supuesto, esto es seguro cuando se ejecuta en paralelo.

ACTUALIZACIÓN 2016-02-06

Aquí hay una manera más agradable de crear la matriz de índices de sublista. Se basa en los mismos principios, pero ajusta el rango de índice y agrega algunas condiciones al filtro para evitar tener que concatenar y asignar un mapa plano a los índices.

 static List> splitStream(List input) { int sz = input.size(); int[] indexes = IntStream.rangeClosed(-1, sz) .filter(i -> i == -1 || i == sz || input.get(i) == null) .toArray(); return IntStream.range(0, indexes.length-1) .mapToObj(i -> input.subList(indexes[i]+1, indexes[i+1])) .collect(toList()); } 

ACTUALIZACIÓN 2016-11-23

Co-presenté una charla con Brian Goetz en Devoxx Antwerp 2016, "Thinking In Parallel" ( video ) que presentó este problema y mis soluciones. El problema que se presenta es una pequeña variación que se divide en "#" en lugar de nulo, pero de lo contrario es lo mismo. En la charla, mencioné que tenía un montón de pruebas de unidad para este problema. Los he añadido a continuación, como un progtwig independiente, junto con mis implementaciones de bucle y secuencias. Un ejercicio interesante para los lectores es ejecutar soluciones propuestas en otras respuestas contra los casos de prueba que he proporcionado aquí, y ver cuáles fallan y por qué. (Las otras soluciones deberán adaptarse para dividirse en base a un predicado en lugar de dividirse en nulo).

 import java.util.*; import java.util.function.*; import java.util.stream.*; import static java.util.Arrays.asList; public class ListSplitting { static final Map, List>> TESTCASES = new LinkedHashMap<>(); static { TESTCASES.put(asList(), asList(asList())); TESTCASES.put(asList("a", "b", "c"), asList(asList("a", "b", "c"))); TESTCASES.put(asList("a", "b", "#", "c", "#", "d", "e"), asList(asList("a", "b"), asList("c"), asList("d", "e"))); TESTCASES.put(asList("#"), asList(asList(), asList())); TESTCASES.put(asList("#", "a", "b"), asList(asList(), asList("a", "b"))); TESTCASES.put(asList("a", "b", "#"), asList(asList("a", "b"), asList())); TESTCASES.put(asList("#"), asList(asList(), asList())); TESTCASES.put(asList("a", "#", "b"), asList(asList("a"), asList("b"))); TESTCASES.put(asList("a", "#", "#", "b"), asList(asList("a"), asList(), asList("b"))); TESTCASES.put(asList("a", "#", "#", "#", "b"), asList(asList("a"), asList(), asList(), asList("b"))); } static final Predicate TESTPRED = "#"::equals; static void testAll(BiFunction, Predicate, List>> f) { TESTCASES.forEach((input, expected) -> { List> actual = f.apply(input, TESTPRED); System.out.println(input + " => " + expected); if (!expected.equals(actual)) { System.out.println(" ERROR: actual was " + actual); } }); } static  List> splitStream(List input, Predicate pred) { int[] edges = IntStream.range(-1, input.size()+1) .filter(i -> i == -1 || i == input.size() || pred.test(input.get(i))) .toArray(); return IntStream.range(0, edges.length-1) .mapToObj(k -> input.subList(edges[k]+1, edges[k+1])) .collect(Collectors.toList()); } static  List> splitLoop(List input, Predicate pred) { List> result = new ArrayList<>(); int start = 0; for (int cur = 0; cur < input.size(); cur++) { if (pred.test(input.get(cur))) { result.add(input.subList(start, cur)); start = cur + 1; } } result.add(input.subList(start, input.size())); return result; } public static void main(String[] args) { System.out.println("===== Loop ====="); testAll(ListSplitting::splitLoop); System.out.println("===== Stream ====="); testAll(ListSplitting::splitStream); } } 

La solución es usar Stream.collect . Para crear un colector utilizando su patrón de constructor ya se da como solución. La alternativa es que la otra collect sobrecargada es un poco más primitiva.

  List strings = Arrays.asList("a", "b", null, "c", null, "d", "e"); List> groups = strings.stream() .collect(() -> { List> list = new ArrayList<>(); list.add(new ArrayList<>()); return list; }, (list, s) -> { if (s == null) { list.add(new ArrayList<>()); } else { list.get(list.size() - 1).add(s); } }, (list1, list2) -> { // Simple merging of partial sublists would // introduce a false level-break at the beginning. list1.get(list1.size() - 1).addAll(list2.remove(0)); list1.addAll(list2); }); 

Como se ve, hago una lista de listas de cadenas, donde siempre hay al menos una última lista de cadenas (vacía).

  • La primera función crea una lista de inicio de listas de cadenas. Especifica el objeto del resultado (tipeado).
  • La segunda función se llama para procesar cada elemento. Es una acción en el resultado parcial y un elemento.
  • El tercero no se usa realmente, entra en juego al paralelizar el procesamiento, cuando se deben combinar resultados parciales.

Una solución con un acumulador:

Como @StuartMarks señala, el combinador no cumple el contrato de paralelismo.

Debido al comentario de @ArnaudDenoyelle una versión que usa reduce .

  List> groups = strings.stream() .reduce(new ArrayList>(), (list, s) -> { if (list.isEmpty()) { list.add(new ArrayList<>()); } if (s == null) { list.add(new ArrayList<>()); } else { list.get(list.size() - 1).add(s); } return list; }, (list1, list2) -> { list1.addAll(list2); return list1; }); 
  • El primer parámetro es el objeto acumulado.
  • La segunda función se acumula.
  • El tercero es el combinador antes mencionado.

Por favor no votes No tengo suficiente lugar para explicar esto en los comentarios .

Esta es una solución con Stream y foreach pero esto es estrictamente equivalente a la solución de Alexis o un bucle foreach (y menos claro, y no pude deshacerme del constructor de copias):

 List> result = new ArrayList<>(); final List current = new ArrayList<>(); list.stream().forEach(s -> { if (s == null) { result.add(new ArrayList<>(current)); current.clear(); } else { current.add(s); } } ); result.add(current); System.out.println(result); 

Entiendo que desea encontrar una solución más elegante con Java 8, pero realmente creo que no se ha diseñado para este caso. Y como dijo Mr. Cuchara, preferiría mucho la manera ingenua en este caso.

Aquí hay otro enfoque, que utiliza una función de agrupación, que hace uso de índices de lista para agrupar.

Aquí estoy agrupando el elemento por el primer índice que sigue a ese elemento, con valor null . Entonces, en su ejemplo, "a" y "b" se mapearían a 2 . Además, estoy mapeando el valor null en el índice -1 , que debería eliminarse más adelante.

 List list = Arrays.asList("a", "b", null, "c", null, "d", "e"); Function indexGroupingFunc = (str) -> { if (str == null) { return -1; } int index = list.indexOf(str) + 1; while (index < list.size() && list.get(index) != null) { index++; } return index; }; Map> grouped = list.stream() .collect(Collectors.groupingBy(indexGroupingFunc)); grouped.remove(-1); // Remove null elements grouped under -1 System.out.println(grouped.values()); // [[a, b], [c], [d, e]] 

También puede evitar obtener el primer índice de elemento null cada vez, almacenando en caché el índice mínimo actual en un AtomicInteger . La Function actualizada sería como:

 AtomicInteger currentMinIndex = new AtomicInteger(-1); Function indexGroupingFunc = (str) -> { if (str == null) { return -1; } int index = names.indexOf(str) + 1; if (currentMinIndex.get() > index) { return currentMinIndex.get(); } else { while (index < names.size() && names.get(index) != null) { index++; } currentMinIndex.set(index); return index; } }; 

Aunque la respuesta de Marks Stuart es concisa, intuitiva y paralelamente segura (y la mejor) , quiero compartir otra solución interesante que no necesita el truco de límites de inicio / finalización.

Si miramos el dominio del problema y pensamos en el paralelismo, podemos resolverlo fácilmente con una estrategia de dividir y vencer. En lugar de pensar en el problema como una lista en serie que tenemos que atravesar, podemos ver el problema como una composición del mismo problema básico: dividir una lista en un valor null . Podemos ver intuitivamente con bastante facilidad que podemos analizar recursivamente el problema con la siguiente estrategia recursiva:

 split(L) : - if (no null value found) -> return just the simple list - else -> cut L around 'null' naming the resulting sublists L1 and L2 return split(L1) + split(L2) 

En este caso, primero buscamos cualquier valor null y en el momento en que encontremos uno, inmediatamente cortamos la lista e invocamos una llamada recursiva en las sublistas. Si no encontramos null (el caso base), terminamos con esta twig y solo devolvemos la lista. Concatenando todos los resultados devolverá la Lista que estamos buscando.

Una imagen vale mas que mil palabras:

enter image description here

El algoritmo es simple y completo: no necesitamos ningún truco especial para manejar los casos extremos del inicio / final de la lista. No necesitamos ningún truco especial para manejar casos extremos como listas vacías, o listas con solo valores null . O listas que terminan con null o comienzan con null .

Una simple implementación ingenua de esta estrategia se ve de la siguiente manera:

 public List> split(List input) { OptionalInt index = IntStream.range(0, input.size()) .filter(i -> input.get(i) == null) .findAny(); if (!index.isPresent()) return asList(input); List firstHalf = input.subList(0, index.getAsInt()); List secondHalf = input.subList(index.getAsInt()+1, input.size()); return asList(firstHalf, secondHalf).stream() .map(this::split) .flatMap(List::stream) .collect(toList()); } 

Primero buscamos el índice de cualquier valor null en la lista. Si no encontramos uno, devolvemos la lista. Si encontramos uno, dividimos la lista en 2 sublistas, los transmitimos y recursivamente llamamos al método de split nuevamente. Las listas resultantes del sub-problema se extraen y combinan para el valor de retorno.

Observe que las 2 secuencias se pueden hacer fácilmente paralelas () y el algoritmo seguirá funcionando debido a la descomposición funcional del problema.

Aunque el código ya es bastante conciso, siempre se puede adaptar de muchas maneras. En aras de un ejemplo, en lugar de verificar el valor opcional en el caso base, podríamos aprovechar el método orElse en OptionalInt para devolver el índice final de la lista, lo que nos permite reutilizar la segunda secuencia y, adicionalmente, filtrar listas vacías:

 public List> split(List input) { int index = IntStream.range(0, input.size()) .filter(i -> input.get(i) == null) .findAny().orElse(input.size()); return asList(input.subList(0, index), input.subList(index+1, input.size())).stream() .map(this::split) .flatMap(List::stream) .filter(list -> !list.isEmpty()) .collect(toList()); } 

El ejemplo solo se da para indicar la mera simplicidad, adaptabilidad y elegancia de un enfoque recursivo. De hecho, esta versión introduciría una pequeña penalización de rendimiento y fallaría si la entrada estuviera vacía (y como tal podría necesitar una verificación vacía adicional) .

En este caso, la recursión probablemente no sea la mejor solución (el algoritmo de Stuart Marks para encontrar índices es solo O (N) y las listas de mapeo / división tienen un costo significativo), pero expresa la solución con un algoritmo paralelo simple e intuitivo sin ninguna efectos secundarios.

No profundizaré en la complejidad y las ventajas / desventajas ni en los casos de uso con criterios de detención y / o disponibilidad de resultados parciales. Simplemente sentí la necesidad de compartir esta estrategia de solución, ya que los otros enfoques eran meramente iterativos o usaban un algoritmo de solución demasiado complejo que no era paralelizable.

Este es un problema muy interesante. Se me ocurrió una solución de una línea. Puede que no sea muy eficiente, pero funciona.

 List list = Arrays.asList("a", "b", null, "c", null, "d", "e"); Collection> cl = IntStream.range(0, list.size()) .filter(i -> list.get(i) != null).boxed() .collect(Collectors.groupingBy( i -> IntStream.range(0, i).filter(j -> list.get(j) == null).count(), Collectors.mapping(i -> list.get(i), Collectors.toList())) ).values(); 

Es una idea similar que se le ocurrió a @Rohit Jain. Estoy agrupando el espacio entre los valores nulos. Si realmente desea una List> , puede agregar:

 List> ll = cl.stream().collect(Collectors.toList()); 

Bueno, después de un poco de trabajo, U vino con una solución de una línea basada en secuencias. En última instancia, usa reduce() para hacer la agrupación, lo que parecía ser la opción natural, pero era un poco feo al poner las cadenas en la List> requerida por reduce:

 List> result = list.stream() .map(Arrays::asList) .map(x -> new LinkedList(x)) .map(Arrays::asList) .map(x -> new LinkedList>(x)) .reduce( (a, b) -> { if (b.getFirst().get(0) == null) a.add(new LinkedList()); else a.getLast().addAll(b.getFirst()); return a;}).get(); 

Sin embargo, es 1 línea!

Cuando se ejecuta con la entrada de la pregunta,

 System.out.println(result); 

Produce:

 [[a, b], [c], [d, e]] 

Aquí está el código de AbacusUtil

 List list = N.asList(null, null, "a", "b", null, "c", null, null, "d", "e"); Stream.of(list).splitIntoList(null, (e, any) -> e == null, null).filter(e -> e.get(0) != null).forEach(N::println); 

Declaración: soy el desarrollador de AbacusUtil.

En mi biblioteca StreamEx hay un método groupRuns que puede ayudarte a resolver esto:

 List input = Arrays.asList("a", "b", null, "c", null, "d", "e"); List> result = StreamEx.of(input) .groupRuns((a, b) -> a != null && b != null) .remove(list -> list.get(0) == null).toList(); 

El método groupRuns toma BiPredicate que para el par de elementos adyacentes devuelve verdadero si deben agruparse. Después de eso eliminamos los grupos que contienen valores nulos y recogemos el rest en la Lista.

Esta solución es paralelamente amigable: también puede usarla para transmisión paralela. También funciona bien con cualquier fuente de flujo (no solo listas de acceso aleatorio como en otras soluciones) y es algo mejor que las soluciones basadas en recostackdores, ya que aquí puede usar cualquier operación de terminal que desee sin desperdicio de memoria intermedia.

Con String uno puede hacer:

 String s = ....; String[] parts = s.split("sth"); 

Si todas las colecciones secuenciales (como la Cadena es una secuencia de caracteres) tuvieran esta abstracción, esto también podría ser factible para ellas:

 List l = ... List> parts = l.split(condition) (possibly with several overloaded variants) 

Si restringimos el problema original a List of Strings (e imponemos algunas restricciones sobre sus contenidos), podríamos hackearlo de esta manera:

 String als = Arrays.toString(new String[]{"a", "b", null, "c", null, "d", "e"}); String[] sa = als.substring(1, als.length() - 1).split("null, "); List> res = Stream.of(sa).map(s -> Arrays.asList(s.split(", "))).collect(Collectors.toList()); 

(Por favor, no te lo tomes en serio) 🙂

De lo contrario, la vieja recursión simple también funciona:

 List> part(List input, List> acc, List cur, int i) { if (i == input.size()) return acc; if (input.get(i) != null) { cur.add(input.get(i)); } else if (!cur.isEmpty()) { acc.add(cur); cur = new ArrayList<>(); } return part(input, acc, cur, i + 1); } 

(tenga en cuenta que en este caso nulo tiene que ser anexado a la lista de entrada)

 part(input, new ArrayList<>(), new ArrayList<>(), 0) 

Agrupe por token diferente cada vez que encuentre un nulo (o separador). Utilicé aquí un número entero diferente (usado atómico solo como titular)

Luego reasigne el mapa generado para transformarlo en una lista de listas.

 AtomicInteger i = new AtomicInteger(); List> x = Stream.of("A", "B", null, "C", "D", "E", null, "H", "K") .collect(Collectors.groupingBy(s -> s == null ? i.incrementAndGet() : i.get())) .entrySet().stream().map(e -> e.getValue().stream().filter(v -> v != null).collect(Collectors.toList())) .collect(Collectors.toList()); System.out.println(x); 

Estaba viendo el video en Thinking in Parallel de Stuart. Así que decidí resolverlo antes de ver su respuesta en el video. Actualizará la solución con el tiempo. por ahora

 Arrays.asList(IntStream.range(0, abc.size()-1). filter(index -> abc.get(index).equals("#") ). map(index -> (index)).toArray()). stream().forEach( index -> {for (int i = 0; i < index.length; i++) { if(sublist.size()==0){ sublist.add(new ArrayList(abc.subList(0, index[i]))); }else{ sublist.add(new ArrayList(abc.subList(index[i]-1, index[i]))); } } sublist.add(new ArrayList(abc.subList(index[index.length-1]+1, abc.size()))); }); 
Intereting Posts