我有这个列表（List<String>）：
["a", "b", null, "c", null, "d", "e"]
我想要这样的东西：
[["a", "b"], ["c"], ["d", "e"]]
换句话说，我想使用null值作为分隔符将我的列表拆分为子列表，以获得列表列表（List<List<String>>）。我正在寻找 Java 8 解决方案。我试过了，Collectors.partitioningBy但我不确定这是我要找的。谢谢！
问问题
35705 次
13 回答
76
尽管已经有几个答案和一个公认的答案，但这个主题仍然缺少几点。首先，共识似乎是使用流解决这个问题只是一种练习，而传统的 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;
}
这主要是直截了当的，但也有一些微妙之处。一点是从prevto的待处理子列表cur始终是打开的。当我们遇到null我们关闭它时，将它添加到结果列表中，然后前进prev。在循环之后，我们无条件地关闭子列表。
另一个观察是这是一个索引循环，而不是值本身，因此我们使用算术 for 循环而不是增强的“for-each”循环。但它表明我们可以使用索引流式传输来生成子范围，而不是流式传输值并将逻辑放入收集器（正如Joop Eggen 提出的解决方案所做的那样）。
一旦我们意识到这一点，我们可以看到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)。其次，使用数组可以避免装箱。
此时，数组中的每个索引值（最后一个除外）都比子列表的开始位置小一。紧挨着它的索引是子列表的结尾。我们简单地流过数组并将每对索引映射到一个子列表并收集输出。
讨论
流方法比 for 循环版本略短，但更密集。for-loop 版本很熟悉，因为我们一直在 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 共同发表了一次演讲，“并行思考”（视频），其中介绍了这个问题和我的解决方案。出现的问题有一个细微的变化，在“#”而不是 null 上分裂，但在其他方面是相同的。在演讲中，我提到我有一堆针对这个问题的单元测试。我在下面附加了它们，作为一个独立的程序，以及我的循环和流实现。对读者来说，一个有趣的练习是针对我在此处提供的测试用例运行其他答案中提出的解决方案，并查看哪些失败以及原因。（其他解决方案必须适应基于谓词的拆分，而不是基于 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);
}
}
于 2015-03-17T22:36:57.420 回答
32
目前我想出的唯一解决方案是实现您自己的自定义收集器。
在阅读解决方案之前，我想对此添加一些注释。我把这个问题更多地当作一个编程练习，我不确定它是否可以用并行流来完成。
所以你必须知道，如果管道并行运行，它会默默地中断。
这不是一个可取的行为，应该避免。这就是我在组合器部分（而不是(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]]
由于Joop Eggen 的答案是 out，看来它可以并行完成（为此感谢他！）。这样，它将自定义收集器实现减少到：
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);.
可以改进它以检查边缘情况。
于 2015-03-17T10:30:12.403 回答
23
解决方案是使用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;
});
- 第一个参数是累积的对象。
- 第二个函数累加。
- 第三个是前面提到的组合器。
于 2015-03-17T11:55:23.833 回答
8
请不要投票。我没有足够的地方在评论中解释这一点。
这是一个带有 aStream和 a的解决方案，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 找到更优雅的解决方案，但我真的认为它不是为这种情况设计的。正如勺子先生所说，在这种情况下，非常喜欢幼稚的方式。
于 2015-03-17T11:16:06.857 回答
5
尽管Marks Stuart 的答案简洁、直观且并行安全（也是最好的），但我想分享另一个不需要开始/结束边界技巧的有趣解决方案。
如果我们查看问题域并考虑并行性，我们可以通过分而治之的策略轻松解决这个问题。与其将问题视为我们必须遍历的序列列表，不如将问题视为相同基本问题的组合：将列表拆分为一个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（基本情况），我们就完成了这个分支并返回列表。连接所有结果将返回我们正在搜索的列表。
一张图片胜过千言万语：
该算法简单而完整：我们不需要任何特殊技巧来处理列表开始/结束的边缘情况。我们不需要任何特殊技巧来处理诸如空列表或只有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列表中任何值的索引。如果我们没有找到，我们返回列表。如果我们找到一个，我们将列表分成 2 个子列表，流过它们并再次递归调用该split方法。然后提取子问题的结果列表并将其组合为返回值。
请注意，这两个流可以很容易地并行（），并且由于问题的功能分解，算法仍然可以工作。
尽管代码已经非常简洁，但它总是可以通过多种方式进行调整。举个例子，我们可以利用 上的orElse方法OptionalInt来返回列表的结束索引，而不是检查基本情况中的可选值，从而使我们能够重用第二个流并额外过滤掉空列表：
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)并且映射/拆分列表的成本很高），但它用一种简单、直观的可并行算法来表达解决方案，没有任何副作用。
我不会深入研究具有停止标准和/或部分结果可用性的复杂性和优点/缺点或用例。我只是觉得有必要分享这个解决方案策略，因为其他方法只是迭代或使用不可并行化的过于复杂的解决方案算法。
于 2016-11-13T11:47:01.080 回答
4
这是另一种方法，它使用分组函数，它利用列表索引进行分组。
在这里，我按该元素后面的第一个索引对元素进行分组，值为 value 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;
}
};
于 2015-03-17T11:07:33.193 回答
3
这是一个非常有趣的问题。我想出了一个单行解决方案。它可能不是很高效，但它可以工作。
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());
于 2015-03-17T13:07:00.260 回答
3
好吧，经过一番工作，你想出了一个基于流的单行解决方案。它最终用于进行分组，这似乎是自然的选择，但是将字符串变成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]]
于 2015-03-18T14:23:55.280 回答
1
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的开发者。
于 2016-11-24T17:06:30.303 回答
0
在我的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方法采用BiPredicatewhich 对相邻元素返回 true。之后，我们删除包含空值的组并将其余的收集到列表中。
这个解决方案是并行友好的：你也可以将它用于并行流。它也适用于任何流源（不仅仅是像其他一些解决方案中的随机访问列表）并且它比基于收集器的解决方案要好一些，因为在这里您可以使用任何您想要的终端操作而不会浪费中间内存。
于 2015-07-15T10:20:25.667 回答
0
使用 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 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)
于 2016-12-08T19:02:28.463 回答
0
每当您找到空值（或分隔符）时，按不同的标记分组。我在这里使用了一个不同的整数（使用原子作为持有人）
然后重新映射生成的地图以将其转换为列表列表。
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);
于 2017-01-19T13:57:38.173 回答
0
我正在观看 Stuart 的 Thinking in Parallel 视频。所以决定在看到他在视频中的回应之前解决它。将随着时间的推移更新解决方案。目前
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())));
});
于 2017-07-04T20:45:38.487 回答