如何使用Java 8流来查找更大值之前的所有值？

Question

用例

通过Katas在工作中发布的一些编码,我偶然发现了这个问题,我不知道如何解决.

使用Java 8 Streams,给定正整数列表,生成一个整数列表,其中整数前面有一个更大的值.

[10, 1, 15, 30, 2, 6]

以上输入将产生:

[1, 15, 2]

因为1在15之前,15在30之前,2在6之前.

非流解决方案

public List<Integer> findSmallPrecedingValues(final List<Integer> values) {

    List<Integer> result = new ArrayList<Integer>();
    for (int i = 0; i < values.size(); i++) {
        Integer next = (i + 1 < values.size() ? values.get(i + 1) : -1);
        Integer current = values.get(i);
        if (current < next) {
            result.push(current);
        }
    }
    return result;
}

我试过的

我遇到的问题是我无法弄清楚如何在lambda中访问下一个.

return values.stream().filter(v -> v < next).collect(Collectors.toList());

题

• 是否可以检索流中的下一个值？
• 我应该使用map并映射到a Pair以便访问下一个吗？

Answer 1

使用IntStream.range:

static List<Integer> findSmallPrecedingValues(List<Integer> values) {
    return IntStream.range(0, values.size() - 1)
        .filter(i -> values.get(i) < values.get(i + 1))
        .mapToObj(values::get)
        .collect(Collectors.toList());
}

它肯定比具有大循环的命令式解决方案更好,但对于以惯用方式"使用流"的目标仍然有点meh.

是否可以检索流中的下一个值？

不,不是真的.我知道的最好的引用是在java.util.stream包描述中:

流的元素仅在流的生命期间访问过一次.像Iteratora 一样,必须生成一个新流来重新访问源的相同元素.

(检索正在操作的当前元素之外的元素意味着它们可以被访问多次.)

我们还可以通过其他方式在技术上做到这一点:

• 有条不紊地(非常meh).
• 使用流的iterator是在技术上还是使用流.

Answer 2

这不是一个纯Java8,但最近我发布了一个名为StreamEx的小型库,它有一个完全符合这个任务的方法:

// Find all numbers where the integer preceded a larger value.
Collection<Integer> numbers = Arrays.asList(10, 1, 15, 30, 2, 6);
List<Integer> res = StreamEx.of(numbers).pairMap((a, b) -> a < b ? a : null)
    .nonNull().toList();
assertEquals(Arrays.asList(1, 15, 2), res);

该pairMap操作内部使用的自定义实现spliterator.因此,您拥有非常干净的代码,而这些代码不依赖于源代码List还是其他内容.当然,它也适用于并行流.

为此任务提供了一个测试用例.

Answer 3

它不是单线(它是双线),但这有效:

List<Integer> result = new ArrayList<>();
values.stream().reduce((a,b) -> {if (a < b) result.add(a); return b;});

而不是通过"查看下一个元素"来解决它,而是通过"查看前一个元素来解决它,它reduce()可以免费提供.我已经通过注入一个代码片段来填充它的预期用法,该片段根据比较填充列表. previous和current元素然后返回当前值,以便下一次迭代将其视为前一个元素.

一些测试代码:

List<Integer> result = new ArrayList<>();
IntStream.of(10, 1, 15, 30, 2, 6).reduce((a,b) -> {if (a < b) result.add(a); return b;});
System.out.println(result);

输出:

[1, 15, 2]

Answer 4

如果流是顺序的还是并行的，则可接受的答案会很好，但List由于对的多次调用，如果基础不是随机访问，则可能会受到影响get。

如果流是顺序的，则可以滚动此收集器：

public static Collector<Integer, ?, List<Integer>> collectPrecedingValues() {
    int[] holder = {Integer.MAX_VALUE};
    return Collector.of(ArrayList::new,
            (l, elem) -> {
                if (holder[0] < elem) l.add(holder[0]);
                holder[0] = elem;
            },
            (l1, l2) -> {
                throw new UnsupportedOperationException("Don't run in parallel");
            });
}

和用法：

List<Integer> precedingValues = list.stream().collect(collectPrecedingValues());

不过，您也可以实现一个收集器，以便对顺序流和并行流进行工作。唯一的事情是您需要应用最终的转换，但是在这里您可以控制List实现，因此不会受到get性能的影响。

这个想法是首先生成一个成对的列表（由int[]大小为2 的数组表示），其中包含由大小为2的窗口（间隔为1）切片的流中的值。当我们需要合并两个列表时，我们检查空度并将第一个列表的最后一个元素与第二个列表的第一个元素的间隙合并。然后，我们应用最终转换以仅过滤所需的值，并将它们映射为具有所需的输出。

它可能不像公认的答案那么简单，但是可以作为替代解决方案。

public static Collector<Integer, ?, List<Integer>> collectPrecedingValues() {
    return Collectors.collectingAndThen(
            Collector.of(() -> new ArrayList<int[]>(),
                    (l, elem) -> {
                        if (l.isEmpty()) l.add(new int[]{Integer.MAX_VALUE, elem});
                        else l.add(new int[]{l.get(l.size() - 1)[1], elem});
                    },
                    (l1, l2) -> {
                        if (l1.isEmpty()) return l2;
                        if (l2.isEmpty()) return l1;
                        l2.get(0)[0] = l1.get(l1.size() - 1)[1];
                        l1.addAll(l2);
                        return l1;
                    }), l -> l.stream().filter(arr -> arr[0] < arr[1]).map(arr -> arr[0]).collect(Collectors.toList()));
}

然后，您可以将这两个收集器包装在实用程序收集器方法中，检查流是否与并行，isParallel然后确定要返回哪个收集器。