将列表按元素拆分成子列表

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

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

我想要这样的东西:

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

换句话说,我想要使用null值作为分隔符将列表拆分到子列表中,以获取列表( List<List<String>> )。 我正在寻找一个Java 8解决scheme。 我已经与Collectors.partitioningBy尝试,但我不知道这是我在找什么。 谢谢!

我现在想出的唯一解决scheme是实现您自己的自定义收集器。

在阅读解决scheme之前,我想添加一些关于这个的注释。 我把这个问题作为一个编程练习,我不确定是否可以用一个并行stream来完成。

所以你必须意识到,如果pipe道并行运行,它将会静静地中断

不是一个理想的行为,应该避免 。 这就是为什么我在组合器部分抛出一个exception(而不是(l1, l2) -> {l1.addAll(l2); return l1;} ),因为它在组合这两个列表时是并行使用的,一个exception,而不是一个错误的结果。

由于列表复制(尽pipe它使用本地方法复制底层数组),这也不是很有效。

所以这里是收集器的实现:

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

正如Joop Eggen的答案已经出来 ,似乎可以并行完成(让他相信这一点!)。 因此,它将自定义收集器实现减less到:

 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并不总是替代品。 有些任务更容易,更适合使用stream,有些任务不是。 在你的情况下,你也可以创build一个实用的方法:

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

它可以改进检查边缘情况。

虽然已经有了几个答案,并且已经接受了答案,但是这个主题还是有一些问题。 首先,共识似乎是用stream来解决这个问题仅仅是一个练习,传统的for-loop方法是可取的。 其次,到目前为止给出的答案已经忽略了使用arrays或vector式技术的方法,我认为这大大改进了stream解决scheme。

首先,为了讨论和分析的目的,这是一个传统的解决scheme:

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

这大多是直截了当的,但有一点微妙之处。 有一点是,从prevcur的未决子列表总是打开的。 当我们遇到null我们closures它,把它添加到结果列表中,并提前prev 。 循环之后,我们无条件closures子列表。

另一个观察是,这是一个循环索引,而不是数值本身,因此我们使用算术for循环而不是增强的“for-each”循环。 但是这表明我们可以使用索引来生成子范围,而不是通过数据stream进行stream式处理,并将逻辑放入收集器(正如Joop Eggen提出的解决scheme所做的那样)。

一旦我们意识到这一点,我们可以看到,input中null每个位置都是一个子列表的分隔符:它是子列表左端的右端,它(加一)是子列表的左端,正确的。 如果我们能够处理边缘情况,就会导致我们find出现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 。 我select使用Stream.of进行追加,然后使用flatMapToInt将其平铺。 (我尝试了其他几种方法,但是这个看起来最干净。)

在这里使用索引数组更方便一些。 首先,访问数组的符号比List更好: indexes[i] vs indexes.get(i) 。 其次,使用数组避免拳击。

此时,数组中的每个索引值(除了最后一个)都小于子列表的起始位置。 其右侧的索引是子列表的结尾。 我们只是简单地将数组stream过,并将每对索引映射到一个子列表中并收集输出。

讨论

stream方法比for循环版本略短,但是更密集。 for循环的版本是很熟悉的,因为我们一直在用Java来做这个东西,但是如果你还没有意识到这个循环应该做什么,那就不是很明显。 您可能必须先模拟几个循环执行,然后才能确定prev正在执行什么以及在循环结束后必须closures打开的子列表。 (我最初忘记了,但是我在testing中发现了这个)。

我认为,stream方法更容易概念化发生的事情:获取一个列表(或一个数组),表示子列表之间的界限。 这是一个简单的stream程双线。 正如我上面提到的那样,困难是find一种方法来把边缘值加到两端。 如果这样做有更好的语法,例如,

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

它会使事情less得多。 (我们真正需要的是数组或列表理解。)一旦拥有索引,将它们映射到实际的子列表并将其收集到结果列表中是一件简单的事情。

并行运行当然是安全的。

更新2016-02-06

这里有一个更好的方法来创build子列表索引数组。 它基于相同的原则,但是它调整了索引范围,并为filter添加了一些条件,以避免连接和平面化索引。

 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安特卫普2016上与Brian Goetz共同发表了一篇题为“并行思考”( video )的演讲,讨论了这个问题和我的解决scheme。 这里提出的问题有一个细微的变化,在“#”而不是null分裂,但它是相同的。 在谈话中,我提到我有一堆针对这个问题的unit testing。 我在下面附加了它们,作为一个独立的程序,以及我的循环和stream实现。 对读者来说,一个有趣的练习就是针对我在这里提供的testing用例运行其他解决scheme中提出的解决scheme,并查看哪些解决scheme失败以及为什么。 (其他解决scheme将不得不根据谓词进行分割,而不是分割为空)。

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

解决scheme是使用Stream.collect 。 已经给出了使用其构build器模式创build收集器的解决scheme。 另一种方法是将另一个重载的集合稍微原始一点。

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

正如我们所看到的,我列出了一个string列表,其中至less有一个最后一个(空的)string列表。

  • 第一个函数创build一个string列表的起始列表。 它指定结果(键入)的对象。
  • 调用第二个函数来处理每个元素。 这是对部分结果和元素的一个行动。
  • 第三个是没有被真正使用的,它在进行并行处理时发挥作用,当部分结果必须被组合时。

带有累加器的解决scheme:

正如@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; }); 
  • 第一个参数是累积的对象。
  • 第二个function积累。
  • 第三个是前面提到的组合器。

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

这是一个Stream和一个foreach的解决scheme,但这是严格相当于亚历克西斯的解决scheme或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); 

我明白,你想find一个与Java 8更优雅的解决scheme,但我真的认为它并没有被devise为这种情况。 正如汤普先生所说,在这种情况下,高度偏爱天真的做法。

这里有另一种方法,它使用分组function,它使用列表索引进行分组。

在这里,我是通过元素后面的第一个索引对元素进行分组,值为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元素的第一个索引,方法是将当前最小索引caching在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; } }; 

虽然马克斯·斯图亚特的答案是简洁,直观和平行安全(和最好的) ,我想分享另一个有趣的解决scheme,不需要开始/结束边界的伎俩。

如果我们看问题领域并考虑并行性,我们可以用分而治之的策略轻松解决这个问题。 我们不必将问题看作是序列列表,而是将其看作是一个基本问题的组合:将列表以null值进行分割。 我们可以很直观地看到,我们可以用下面的recursion策略recursion地分解这个问题:

 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) 

在这种情况下,我们首先search任何null值,并立即find一个,我们立即削减列表,并调用子列表的recursion调用。 如果我们没有findnull (基本情况),我们完成了这个分支,只是返回列表。 连接所有结果将返回我们正在search的列表。

一张图片胜过千言万语:

在这里输入图像说明

该algorithm简单而完整:我们不需要任何特殊的技巧来处理列表开始/结束的边缘情况。 我们不需要任何特殊的技巧来处理边界情况,比如空列表或者只有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()); } 

我们首先search列表中任何null值的索引。 如果我们找不到一个,我们返回列表。 如果我们find一个,我们将这个列表分成两个子列表,在它们之间stream转,然后recursion调用split方法。 然后提取出结果的子问题列表并将其合并为返回值。

注意这两个stream可以很容易地并行(),并且由于问题的function分解,algorithm仍然可以工作。

虽然代码已经非常简洁,但它总能以多种方式进行调整。 举例来说,我们可以利用orElse上的orElse方法来返回列表的结束索引,而不是检查基本情况下的可选值,从而使我们能够重新使用第二个stream,过滤掉空列表:

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

这个例子只是为了说明recursion方法的简单性,适应性和优雅性。 事实上,这个版本会引入一个小的性能损失,如果input是空的,就会失败(因此可能需要额外的空检查)

在这种情况下,recursion可能不是最好的解决scheme( Stuart Marksalgorithmfind索引只有O(N)和映射/分裂列表有很大的代价),但是它expression了一个简单的,直观的并行algorithm的解决scheme,没有任何副作用。

我不会深入挖掘复杂性和优点/缺点或使用停止标准和/或部分结果可用性的情况。 我只是觉得有必要分享这个解决scheme策略,因为其他方法仅仅是迭代的,或者使用了一个不可并行化的非常复杂的解决schemealgorithm。

这是一个非常有趣的问题。 我想出了一个解决scheme。 它可能不是很高性能,但它的工作。

 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提出了一个类似的想法。 我将空值之间的空格分组。 如果你真的想要一个List<List<String>>你可以附加:

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

那么,经过一些工作,我想出了一个基于stream的解决scheme。 它最终使用reduce()来进行分组,这似乎是自然的select,但是将string获取到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行!

当从问题的input运行时,

 System.out.println(result); 

生产:

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

这里是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的开发人员。

在我的StreamEx库中,有一个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 ,如果它们应该被分组,则这对相邻的元素返回true。 之后,我们删除包含空值的组,并将其余的收集到列表中。

这个解决scheme是并行友好的:您也可以将它用于并行stream。 它也适用于任何stream源(不仅仅是像其他一些解决scheme一样的随机访问列表),它比基于收集器的解决scheme好一些,因为在这里你可以使用任何你想要的terminal操作而不会中间浪费内存。

用String可以做到:

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

如果所有顺序集合(如string是一个字符序列)有这样的抽象,这也可以为他们做:

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

如果我们将原来的问题限制在string列表(并对其元素内容施加一些限制),我们可以像这样破解它:

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

(请不要认真对待:))

否则,普通的旧recursion也适用:

 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必须被附加到input列表)

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

每当find空(或分隔符)时,按不同标记分组。 我在这里使用了一个不同的整数(使用primefaces就像持有者)

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

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

我正在看斯图尔特关于并​​行思考的video。 所以决定在video中看到他的回应之前解决它。 随着时间更新解决scheme。 目前

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