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

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

虽然已经有几个答案,并且已经接受了答案,但这个主题仍然缺少几点.首先,共识似乎是使用流来解决这个问题仅仅是一种练习,而传统的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-loop而不是增强的"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将它们展平.(我尝试了其他几种方法,但这个方法看起来最干净.)

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

此时,数组中的每个索引值(除了最后一个)都比子列表的起始位置小1.其右边的索引是子列表的结尾.我们简单地对数组进行流式处理,并将每对索引映射到子列表中并收集输出.

讨论

流方法比for-loop版略短,但它更密集.for循环版本很熟悉,因为我们一直在用Java做这些东西,但是如果你还没有意识到这个循环应该做什么,那就不明显了.在弄清楚prev正在做什么以及为什么在循环结束后必须关闭open子列表之前,您可能必须模拟一些循环执行.(我最初忘了拥有它,但我在测试中发现了这一点.)

我认为,流方法更容易概念化正在发生的事情:获取指示子列表之间边界的列表(或数组).这是一个简单的溪流双线.正如我上面提到的那样,困难在于找到一种方法来将边缘值固定到两端.如果有更好的语法来做到这一点,例如,

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

我和2016年Devoxx Antwerp的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);
    }
}

Answer 2

我现在提出的唯一解决方案是实现自己的自定义收集器.

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

因此,您必须意识到,如果管道并行运行,它将无声地中断.

这不是理想的行为,应该避免.这就是我在组合器部分(而不是(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的答案已经出来,它似乎可以并行完成(给予他信任!).有了它,它将自定义收集器实现减少到:

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 3

解决方案是使用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;
                    });

• 第一个参数是累积的对象.
• 第二个功能累积.
• 第三种是上述组合器.

Answer 4

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

这是一个带有a Stream和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找到更优雅的解决方案,但我真的认为它不是针对这种情况设计的.正如潘先生所说,在这种情况下,我更倾向于天真的方式.

Answer 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再次方法。然后提取子问题的结果列表并将其组合为返回值。

请注意，可以轻松地使 2 个流并行（）并且由于问题的功能分解，该算法仍然可以工作。

尽管代码已经非常简洁，但它始终可以通过多种方式进行调整。举个例子，我们可以利用 上的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)并且映射/拆分列表的成本很高），但它使用简单、直观的可并行化算法表达了解决方案，没有任何副作用。

我不会深入挖掘具有停止标准和/或部分结果可用性的复杂性和优点/缺点或用例。我只是觉得有必要分享这个解决方案策略，因为其他方法只是迭代或使用不可并行化的过于复杂的解决方案算法。