尽管已经有几个答案,并且已经接受了答案,但这个主题仍然缺少一些要点。首先,共识似乎是使用流解决这个问题只是一种练习,传统的 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
to cur
始终开放。当我们遇到null
我们关闭它,将其添加到结果列表中,然后前进prev
。循环结束后,我们无条件关闭子列表。
另一个观察结果是,这是索引上的循环,而不是值本身的循环,因此我们使用算术 for 循环而不是增强的“for-each”循环。但它表明我们可以使用索引流式传输来生成子范围,而不是流式传输值并将逻辑放入收集器中(如Joop Eggen 提出的解决方案 https://stackoverflow.com/a/29098447/1441122).
一旦我们意识到这一点,我们就可以看到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 循环版本很熟悉,因为我们一直在 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 共同发表了演讲“并行思考”(video https://www.youtube.com/watch?v=2nup6Oizpcw)介绍了这个问题和我的解决方案。所提出的问题有一个轻微的变化,即在“#”而不是空上分割,但在其他方面是相同的。在演讲中,我提到我对这个问题进行了一系列单元测试。我将它们作为独立程序附加在下面,以及我的循环和流实现。对于读者来说,一个有趣的练习是针对我在这里提供的测试用例运行其他答案中提出的解决方案,并查看哪些解决方案失败以及原因。 (其他解决方案必须适应基于谓词的拆分,而不是基于 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);
}
}