将列表沿元素拆分为子列表

Question

我有这个列表 (List<String>):

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

我想要这样的东西：

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

换句话说，我想使用 null 值作为分隔符将我的列表拆分为子列表，以获得列表列表 (List<List<String>>)。我正在寻找 Java 8 解决方案。我试过 Collectors.partitioningBy 但我不确定这是否是我要找的。谢谢！

Answer 1

目前我想到的唯一解决方案是实现您自己的自定义收集器。

在阅读解决方案之前，我想添加一些关于此的注释。我更多地把这个问题当作一个编程练习，我不确定它是否可以用并行流来完成。

因此您必须注意，如果管道并行，它会 悄悄中断 。

这不是可取的行为，应该避免。这就是为什么我在组合器部分抛出异常（而不是 (l1, l2) -> {l1.addAll(l2); return l1;}），因为它在组合两个列表时并行使用，所以你有一个异常而不是错误的结果。

此外，由于列表复制，这不是很有效（尽管它使用本地方法复制底层数组）。

收集器实现如下：

private static Collector<String, List<List<String>>, List<List<String>>> splitBySeparator(Predicate<String> sep) {
    final List<String> current = new ArrayList<>();
    return Collector.of(() -> new ArrayList<List<String>>(),
        (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;
            }
        );
}

以及如何使用它：

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

输出：

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

作为，它似乎可以并行完成（为此归功于他！）。这样它将自定义收集器实现减少到：

private static Collector<String, List<List<String>>, List<List<String>>> splitBySeparator(Predicate<String> sep) {
    return Collector.of(() -> new ArrayList<List<String>>(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;});
}

这让关于并行性的段落有点过时，但我还是保留了它，因为它可以作为一个很好的提醒。

请注意，Stream API 并不总是替代品。有些任务使用流更容易、更适合，有些任务则不然。在您的情况下，您还可以为此创建一个实用方法：

private static <T> List<List<T>> splitBySeparator(List<T> list, Predicate<? super T> predicate) {
    final List<List<T>> 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;
}

并像 List<List<String>> list = splitBySeparator(originalList, Objects::isNull); 那样称呼它。

可以改进检查边缘情况。

Answer 2

这是另一种方法，它使用分组函数，利用列表索引进行分组。

在这里，我按该元素后的第一个索引对元素进行分组，值为 null。因此，在您的示例中，"a" 和 "b" 将映射到 2。另外，我正在将 null 值映射到 -1 索引，稍后应将其删除。

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]]

您还可以避免每次都获取 null 元素的第一个索引，方法是将当前最小索引缓存在 AtomicInteger 中。更新后的 Function 就像：

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

Answer 3

请不要投票。我没有足够的地方在评论中解释这一点。

这是一个带有 Stream 和 foreach 的解决方案，但这严格等同于 Alexis 的解决方案或 foreach 循环（不太清楚，我无法摆脱复制构造函数）：

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

我知道您想用 Java 8 找到更优雅的解决方案，但我真的认为它不是为这种情况设计的。正如勺子先生所说，在这种情况下，我更喜欢这种幼稚的方式。

Answer 4

解决方案是使用Stream.collect。使用其构建器模式创建收集器已作为解决方案给出。替代方案是另一个重载 collect 更原始一点。

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

如你所见，我制作了一个字符串列表列表，其中总是至少有一个最后（空）字符串列表。

第一个函数创建一个字符串列表的起始列表。 它指定结果（类型化）对象。
调用第二个函数来处理每个元素。 它是对部分结果和元素的操作。
第三个并没有真正用到，它在并行处理时发挥作用，当必须合并部分结果时。

带累加器的解法：

正如@StuartMarks 指出的那样，组合器没有满足并行性的约定。

由于@ArnaudDenoyelle 的评论，一个版本使用 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;
                    });

第一个参数为累计对象
第二个函数累加
第三个就是前面提到的combiner

Answer 5

这是一个很有趣的问题。我想出了一个单行解决方案。它可能不是很高效，但它确实有效。

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();

@Rohit Jain 提出了类似的想法。我将空值之间的 space 分组。如果你真的想要一个 List<List<String>> 你可以追加：

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

Answer 6

虽然已经有几个答案，并且有一个被接受的答案，但这个主题仍然缺少一些要点。首先，共识似乎是使用流解决这个问题只是一种练习，传统的 for 循环方法更可取。其次，到目前为止给出的答案忽略了一种使用数组或向量样式技术的方法，我认为这种方法可以显着改进流解决方案。

先给出一个常规方案，供大家讨论分析：

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

这大部分是直截了当的，但也有一些微妙之处。有一点是从 prev 到 cur 的挂起子列表始终处于打开状态。当我们遇到 null 我们关闭它，将它添加到结果列表中，并前进 prev。循环后我们无条件关闭子列表。

另一个观察是这是一个索引循环，而不是值本身，因此我们使用算术 for 循环而不是增强的 "for-each" 循环。但这表明我们可以使用索引流式传输来生成子范围，而不是流式传输值并将逻辑放入收集器（正如所做的那样）。

一旦我们意识到这一点，我们可以看到输入中 null 的每个位置都是子列表的分隔符：它是子列表的右端到左边，它（加一) 是右边子列表的左端。如果我们可以处理边缘情况，它会导致我们找到 null 元素出现的索引，将它们映射到子列表，并收集子列表。

结果代码如下：

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

获取 null 所在的索引非常容易。绊脚石是在左侧添加 -1 并在右侧添加 size 。我选择使用 Stream.of 进行附加，然后 flatMapToInt 将它们展平。（我尝试了其他几种方法，但这一种似乎是最干净的。）

这里的索引用数组更方便一些。首先，访问数组的表示法比访问列表更好：indexes[i] vs. indexes.get(i)。其次，使用数组可以避免装箱。

此时，数组中的每个索引值（最后一个除外）都比子列表的起始位置小1。其右侧的索引是子列表的末尾。我们简单地流过数组并将每对索引映射到一个子列表并收集输出。

讨论

流方法比 for 循环版本略短，但更密集。 for 循环版本很熟悉，因为我们一直在 Java 中执行这些操作，但是如果您还不知道这个循环应该做什么，那么它并不明显。在弄清楚 prev 正在做什么以及为什么在循环结束后必须关闭打开的子列表之前，您可能必须模拟几次循环执行。（我最初忘记了，但我在测试中发现了这个。）

我认为流方法更容易概念化正在发生的事情：获取指示子列表之间边界的列表（或数组）。这是一个简单的两层流。正如我上面提到的，困难在于找到一种将边缘值附加到末端的方法。如果有更好的语法可以做到这一点，例如

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

它会让事情变得不那么混乱。（我们真正需要的是数组或列表理解。）一旦有了索引，将它们映射到实际的子列表并将它们收集到结果列表中就是一件简单的事情。

当然，当运行并行时，这是安全的。

更新 2016-02-06

这是创建子列表索引数组的更好方法。它基于相同的原则，但它调整了索引范围并向过滤器添加了一些条件以避免必须连接和平面映射索引。

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

更新 2016-11-23

我在 Devoxx Antwerp 2016 上与 Brian Goetz 共同发表了一个演讲，"Thinking In Parallel" (video) 重点介绍了这个问题和我的解决方案。出现的问题有一个细微的变化，在“#”而不是 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);
    }
}

Answer 7

好吧，经过一些工作，您已经想出了一个基于流的单行解决方案。它最终使用 reduce() 进行分组，这似乎是自然的选择，但是将字符串放入 reduce 所需的 List<List<String>> 中有点难看：

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();

它是但是1行！

当运行输入问题时，

System.out.println(result);

生产：

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

Answer 8

在我的StreamEx library there's a groupRuns方法中可以帮助你解决这个问题：

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();

groupRuns 方法接受一个 BiPredicate，对于相邻元素对 returns 如果它们应该被分组，则为 true。之后我们删除包含空值的组并将其余部分收集到列表中。

此解决方案是并行友好的：您也可以将其用于并行流。它也适用于任何流源（不仅是像其他一些解决方案中的随机访问列表），而且它比基于收集器的解决方案要好一些，因为在这里你可以使用你想要的任何终端操作而不会浪费中间内存。

Answer 9

虽然简洁、直观且并行安全 （最好），但我想分享另一个不需要 start/end 边界技巧。

如果我们查看问题域并考虑并行性，我们可以使用分而治之的策略轻松解决这个问题。与其将问题视为我们必须遍历的序列列表，不如将问题视为同一基本问题的组合：在 null 值处拆分列表。我们可以很容易地直观地看到，我们可以使用以下递归策略递归分解问题：

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)

在这种情况下，我们首先搜索任何 null 值，一旦找到，我们立即切割列表并对子列表调用递归调用。如果我们没有找到 null（基本情况），我们就完成了这个分支，只是 return 列表。连接所有结果将 return 我们正在搜索的列表。

一图胜千言：

该算法简单而完整：我们不需要任何特殊技巧来处理列表 start/end 的边缘情况。我们不需要任何特殊技巧来处理边缘情况，例如空列表或只有 null 值的列表。或以 null 结尾或以 null.

开头的列表

此策略的简单天真实现如下所示：

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());

}

我们首先在列表中搜索任何 null 值的索引。如果找不到，我们会 return 列表。如果我们找到一个，我们将列表分成 2 个子列表，流过它们并再次递归调用 split 方法。然后提取并合并子问题的结果列表以获得 return 值。

请注意，这 2 个流可以很容易地并行化（），并且由于问题的功能分解，该算法仍然有效。

虽然代码已经很简洁了，但它总是可以以多种方式进行调整。举个例子，我们可以在 OptionalInt 到 return 列表的结束索引上利用 orElse 方法，而不是在基本情况下检查可选值，使我们能够重新使用第二个流并另外过滤掉空列表：

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

给出该示例仅是为了说明递归方法的简单性、适应性和优雅性。事实上，如果输入为空 （因此可能需要额外的空检查），此版本会引入一个小的性能损失并失败。

在这种情况下，递归可能不是最佳解决方案（Stuart Marks 查找索引的算法仅是 O(N) 和 mapping/splitting 列表具有显着的成本），但它通过简单、直观的可并行化算法表达了解决方案，没有任何副作用。

我不会深入探讨复杂性和 advantages/disadvantages 或具有停止条件 and/or 部分结果可用性的用例。我只是觉得有必要分享这个解决方案策略，因为其他方法只是迭代或使用无法并行化的过于复杂的解决方案算法。

Answer 10

这是 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);

声明：我是AbacusUtil的开发者

Answer 11

使用字符串可以做到：

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

如果所有顺序集合（因为 String 是一个字符序列）都有这种抽象，这对它们也是可行的：

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

如果我们将原始问题限制在字符串列表（并对它的元素内容施加一些限制），我们可以像这样破解它：

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());

（不过请不要当真:)）

否则，普通的旧递归也可以工作：

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

（注意在这种情况下必须将 null 附加到输入列表）

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

Answer 12

每当您发现 null（或分隔符）时，按不同的标记分组。我在这里使用了一个不同的整数（作为持有者使用原子）

然后重新映射生成的地图，将其转换为列表列表。

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

Answer 13

我在看 Stuart 的平行思考视频。所以决定在看到他在视频中的回应之前解决它。将随时间更新解决方案。现在

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

将列表沿元素拆分为子列表

Splitting List into sublists along elements

java

list

java-8

collectors