Division de la liste en sous-Listes le long des éléments

bien qu'il y ait déjà plusieurs réponses, et une réponse acceptée, il manque encore quelques points à ce sujet. Premièrement, il semble y avoir consensus sur le fait que la résolution de ce problème à l'aide de streams n'est qu'un exercice et que l'approche conventionnelle en boucle est préférable. Deuxièmement, les réponses données jusqu'à présent ont négligé une approche utilisant des techniques de type tableau ou vecteur qui, je pense, améliore considérablement la solution de flux.

tout d'Abord, voici un solution conventionnelle, à des fins de discussion et d'analyse:

static List<List<String>> splitConventional(List<String> input) {
    List<List<String>> 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;
}

c'est assez simple, mais il y a un peu de subtilité. Un point est qu'une sous-liste en attente de prev à cur est toujours ouverte. Lorsque nous rencontrons null nous le fermons, l'ajoutons à la liste des résultats, et avancer prev . Après la boucle, nous fermons la sous-liste inconditionnellement.

une autre observation est qu'il s'agit d'une boucle sur les indices, pas sur les valeurs elles-mêmes, nous utilisons donc une boucle arithmétique au lieu de la boucle améliorée "pour chaque". Mais il suggère que nous pouvons streamer en utilisant les index pour générer des sous-séries au lieu de streamer des valeurs et de mettre la logique dans le collecteur (comme cela a été fait par la solution proposée par Joop Eggen ).

une Fois que nous avons réalisé, nous pouvons voir que chaque position de null dans l'entrée est le délimiteur d'une sous-liste: c'est le bon fin de la sous-liste à gauche, et it (plus un) est l'extrémité gauche de la sous-liste à droite. Si nous pouvons gérer les cas de bordures, cela conduit à une approche où nous trouvons les index auxquels null éléments se produisent, les mapper à des sous-listes, et de recueillir les sous-listes.

le code obtenu est le suivant:

static List<List<String>> splitStream(List<String> 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());
}

obtenir les indices auxquels null se produit est assez facile. La pierre d'achoppement est d'ajouter -1 à gauche et size à droite. J'ai choisi d'utiliser Stream.of pour faire l'ajout et puis flatMapToInt pour les aplatir. (J'ai essayé plusieurs autres approches, mais celle-ci semblait la plus propre.)

il est un peu plus commode d'utiliser des tableaux pour les index ici. Tout d'abord, la notation pour accéder à un tableau est plus agréable que pour une liste: indexes[i] vs. indexes.get(i) . Deuxièmement, l'utilisation d'un tableau évite de boxe.

à ce point, chaque indice la valeur dans le tableau (sauf pour le dernier) est une valeur de moins que la position de début d'une sous-liste. L'index à sa droite, à la fin de la sous-liste. Nous diffusons simplement sur le tableau et mappons chaque paire d'index dans une sous-liste et recueillons la sortie.

Discussion

l'approche streams est légèrement plus courte que la version for-loop, mais elle est plus dense. La version for-loop est familière, parce que nous faisons ce truc dans Java tout le temps, mais si vous n'êtes pas déjà au courant de ce que cette boucle est censé faire, ce n'est pas évident. Vous pourriez avoir à simuler quelques exécutions de boucle avant de comprendre ce que prev fait et pourquoi la sous-liste ouverte doit être fermée après la fin de la boucle. (J'ai d'abord oublié de l'avoir, mais j'ai remarqué cela dans les tests.)

l'approche streams est, je pense, plus facile à conceptualiser ce qui se passe: obtenir une liste (ou un tableau) qui indique les frontières entre les sous-listes. C'est un simple streams double-liner. La difficulté, comme je l'ai mentionné ci-dessus, est de trouver un moyen de virer de bord valeurs sur les extrémités. S'il y avait une meilleure syntaxe pour faire cela, par exemple,

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

cela rendrait les choses beaucoup moins encombrées. (Ce dont nous avons vraiment besoin, c'est d'une compréhension de tableau ou de liste.) Une fois que vous avez les index, il est simple de les mapper dans des sous-listes réelles et de les rassembler dans la liste de résultats.

Et bien sûr, c'est sans danger quand on fonctionne en parallèle.

mise à jour 2016-02-06

Voici une meilleure façon de créer le tableau des index des sous-listes. Il est basé sur les mêmes principes, mais il ajuste la gamme d'index et ajoute quelques conditions au filtre pour éviter d'avoir à concaténer et flatmap les index.

static List<List<String>> splitStream(List<String> 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());
}

mise à jour 2016-11-23

I co-présenté un entretien avec Brian Goetz à Devoxx Anvers 2016, "Thinking in Parallel" ( vidéo ) qui a présenté ce problème et mes solutions. Le problème présenté il y a une légère variation qui divise sur "#" au lieu de nul, mais c'est autrement la même chose. Dans le discours, j'ai mentionné que j'avais un tas de tests unitaires pour ce problème. Je les ai ajoutés ci-dessous, en tant que programme autonome, ainsi que mes implémentations de loop et streams. Un exercice intéressant pour les lecteurs est de comparez les solutions proposées dans d'autres réponses aux cas d'essai que j'ai fournis ici, et voyez lesquelles échouent et pourquoi. (Les autres solutions devront être adaptées pour se diviser sur la base d'un prédicat au lieu de se diviser sur null.)

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

import static java.util.Arrays.asList;

public class ListSplitting {
    static final Map<List<String>, List<List<String>>> 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<String> TESTPRED = "#"::equals;

    static void testAll(BiFunction<List<String>, Predicate<String>, List<List<String>>> f) {
        TESTCASES.forEach((input, expected) -> {
            List<List<String>> actual = f.apply(input, TESTPRED);
            System.out.println(input + " => " + expected);
            if (!expected.equals(actual)) {
                System.out.println("  ERROR: actual was " + actual);
            }
        });
    }

    static <T> List<List<T>> splitStream(List<T> input, Predicate<? super T> 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 <T> List<List<T>> splitLoop(List<T> input, Predicate<? super T> pred) {
        List<List<T>> 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 solution est d'utiliser Stream.collect . Pour créer un collecteur en utilisant son modèle de constructeur est déjà donnée comme solution. L'alternative est l'autre collect surchargé étant un tout petit peu plus primitif.

    List<String> strings = Arrays.asList("a", "b", null, "c", null, "d", "e");
    List<List<String>> groups = strings.stream()
            .collect(() -> {
                List<List<String>> 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);
            });

comme on le voit, je fais une liste de listes de chaînes, où il y a toujours au moins une dernière liste de chaînes (vide).

• la première fonction crée une liste de départ de listes de chaînes. il spécifie le résultat (dactylographié) de l'objet.
• la seconde fonction est appelée à traiter chaque élément. C'est une action sur le résultat partiel et d'un élément.
• le troisième n'est pas vraiment utilisé, il entre en jeu sur la parallélisation du traitement, lorsque les résultats partiels doivent être combinés.

une solution avec un accumulateur:

comme le souligne @StuartMarks, le combiner ne remplit pas le contrat de parallélisme.

en raison du commentaire de @ArnaudDenoyelle une version utilisant reduce .

    List<List<String>> groups = strings.stream()
            .reduce(new ArrayList<List<String>>(),
                    (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;
                    });

• le premier paramètre est l'objet accumulé.
• la seconde fonction s'accumule.
• La troisième est celle-ci combiner.

Merci de ne pas voter. Je n'ai pas assez de place pour l'expliquer dans les commentaires .

c'est une solution avec un Stream et un foreach mais c'est strictement équivalent à la solution D'Alexis ou une boucle foreach (et moins claire, et je n'ai pas pu me débarrasser du constructeur de copie):

List<List<String>> result = new ArrayList<>();
final List<String> 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);

je comprends que vous voulez trouver une solution plus élégante avec Java 8, mais je pense vraiment qu'il n'a pas été conçu pour ce cas. Et comme l'a dit M. cuillère, préfèrent de loin les naïfs dans ce cas.

voici une autre approche, qui utilise une fonction de groupement, qui utilise des indices de liste pour le groupement.

ici, je regroupe l'élément par le premier index qui suit cet élément, avec la valeur null . Donc ,dans votre exemple, "a" et "b" seraient mappés en 2 . En outre, je mappage null valeur à -1 index, qui devrait être supprimé plus tard.

List<String> list = Arrays.asList("a", "b", null, "c", null, "d", "e");

Function<String, Integer> 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<Integer, List<String>> 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]]

vous pouvez aussi éviter obtenir le premier index de l'élément null à chaque fois, en cachant l'index min courant dans un AtomicInteger . La mise à jour Function serait comme:

AtomicInteger currentMinIndex = new AtomicInteger(-1);

Function<String, Integer> 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;
        }
    };

bien que la answer of Marks Stuart est concis, intuitif et parallèle sûr (et le meilleur) , je veux partager une autre solution intéressante qui n'a pas besoin de l'astuce de début/fin limites.

si nous regardons le domaine des problèmes et que nous pensons au parallélisme, nous pouvons facilement résoudre ce problème avec une stratégie de diviser pour mieux régner. Au lieu de considérer le problème comme une liste en série que nous devons parcourir, nous pouvons regarder le problème comme une composition du même problème de base: diviser une liste à une valeur null . Nous pouvons intuitivement voir assez facilement que nous pouvons briser récursivement le problème avec la stratégie récursive suivante:

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)

dans ce cas, nous recherchons d'abord n'importe quelle valeur null et au moment de trouver une, nous coupons immédiatement la liste et invoquons un appel récursif sur les sous-listes. Si nous ne trouvons pas null (le cas de base), nous sommes finis avec cette branche et il suffit de retourner la liste. En concaténant tous les résultats, vous obtiendrez la liste que nous recherchons.

Une image vaut mille mots:

l'algorithme est simple et complet: nous n'avons pas besoin d'astuces spéciales pour gérer les cas de bord du début/fin de la liste. Nous n'avons pas besoin d'astuces spéciales pour traiter les cas extrêmes tels que les listes vides ou les listes avec seulement les valeurs null . Ou des listes se terminant par null ou commençant par null .

Un simple naïve de la mise en œuvre de cette stratégie se présente comme suit:

public List<List<String>> split(List<String> input) {

    OptionalInt index = IntStream.range(0, input.size())
                                 .filter(i -> input.get(i) == null)
                                 .findAny();

    if (!index.isPresent())
        return asList(input);

    List<String> firstHalf  = input.subList(0, index.getAsInt());
    List<String> secondHalf = input.subList(index.getAsInt()+1, input.size());

    return asList(firstHalf, secondHalf).stream()
                 .map(this::split)
                 .flatMap(List::stream)
                 .collect(toList());

}

nous cherchons d'abord l'index de toute valeur null dans la liste. Si on n'en trouve pas, on renvoie la liste. Si nous en trouvons une, nous divisons la liste en 2 sous-listes, les diffusons et appelons récursivement la méthode split à nouveau. Les listes résultant de la sous-problème sont ensuite extraites et combinés pour la valeur de retour.

remarque que les 2 flux peuvent facilement être rendus parallèles () et l'algorithme fonctionnera toujours en raison de la décomposition fonctionnelle du problème.

bien que le code soit déjà assez concis, il peut toujours être adapté de nombreuses façons. Pour un exemple, au lieu de vérifier la valeur optionnelle dans le cas de base, nous pourrions profiter de la méthode orElse sur le OptionalInt pour retourner l'index final de la liste, nous permettant de réutiliser le second flux et filtrer en plus les listes vides:

public List<List<String>> split(List<String> 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());
}

l'exemple n'est donné que pour indiquer la simplicité, l'adaptabilité et l'élégance d'une approche récursive. En effet, cette version introduirait une petite pénalité de performance et échouerait si l'entrée était vide (et en tant que tel pourrait avoir besoin d'une vérification supplémentaire vide) .

dans ce cas, la récursion pourrait ne pas être la meilleure solution ( Stuart Marks algorithme pour trouver des indices est seulement O(N) et la cartographie/listes de partage a un coût important), mais il exprime la solution avec un algorithme simple et intuitif parallélisable sans aucun effet secondaire.

Je ne vais pas creuser plus profondément dans la complexité et les avantages / inconvénients ou utiliser des cas avec des critères stop et / ou résultat partiel disponibilité. J'ai juste senti le besoin de partager cette stratégie de solution, puisque les autres approches étaient simplement itératives ou utilisant un algorithme de solution trop complexe qui n'était pas parallélisable.

C'est un problème intéressant. J'ai trouvé une solution en une ligne. Ce n'est peut-être pas très performant, mais ça marche.

List<String> list = Arrays.asList("a", "b", null, "c", null, "d", "e");
Collection<List<String>> 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();

c'est une idée similaire que @Rohit Jain a inventé. Je regroupe l'espace entre les valeurs nulles. Si vous voulez vraiment un List<List<String>> , vous pouvez ajouter:

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

Eh bien, après un peu de travail U ont trouvé une solution de flux en une seule ligne. Il utilise finalement reduce() pour faire le groupement, qui semblait le choix naturel, mais il était un peu laid obtenir les cordes dans le List<List<String>> requis par réduire:

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

Il est toutefois 1 ligne!

Lorsqu'il est exécuté avec l'entrée de la question,

System.out.println(result);

produit:

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

voici le code de AbacusUtil

List<String> 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);

Déclaration： je suis le développeur de AbacusUtil.

dans mon StreamEx bibliothèque Il ya un groupRuns méthode qui peut vous aider à résoudre ce problème:

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

la méthode groupRuns prend un BiPredicate qui pour la paire d'éléments adjacents retourne vrai si elles doivent être groupées. Après cela, nous supprimons les groupes contenant des nulls et recueillons le reste de la liste.

cette solution est facile à utiliser en parallèle: vous pouvez l'utiliser pour stream ainsi. En outre, il fonctionne bien avec n'importe quelle source de flux (non seulement des listes d'accès aléatoires comme dans d'autres solutions) et il est un peu mieux que les solutions de collecteur que vous pouvez ici utiliser n'importe quelle opération de terminal que vous voulez sans perte de mémoire intermédiaire.

Avec de la Ficelle, on peut le faire:

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

si toutes les collections séquentielles (comme la chaîne est une séquence de caractères) avaient cette abstraction cela pourrait être faisable pour eux aussi:

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

si nous limitons le problème original à la liste des chaînes (et en imposant quelques restrictions sur son contenu d'éléments) nous pourrions le hacker comme ceci:

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

(merci de ne pas le prendre au sérieux :))

sinon, la simple vieille récursion fonctionne aussi:

List<List<String>> part(List<String> input, List<List<String>> acc, List<String> 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);
}

(note dans ce cas null doit être ajouté à la liste d'entrée)

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

Groupe par différents jeton à chaque fois que vous trouvez une valeur null (ou séparateur). J'ai utilisé ici un entier différent (utilisé atomique juste comme support)

Puis reconfigurer la carte générée pour la transformer en une liste de listes.

AtomicInteger i = new AtomicInteger();
List<List<String>> 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);

je regardais la vidéo sur la pensée en parallèle par Stuart. Alors décidé de le résoudre avant de voir sa réponse dans la vidéo. Mettra à jour la solution avec le temps. pour l'instant

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<String>(abc.subList(0, index[i])));
                    }else{

                    sublist.add(new ArrayList<String>(abc.subList(index[i]-1, index[i])));
                    }
                }
    sublist.add(new ArrayList<String>(abc.subList(index[index.length-1]+1, abc.size())));
});