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

Question

用例

通过在工作中发布的一些编码 Katas，我偶然发现了这个我不确定如何解决的问题。

Using Java 8 Streams, given a list of positive integers, produce a list of integers where the integer preceded a larger value.
[10, 1, 15, 30, 2, 6]
The above input would yield:
[1, 15, 2]
since 1 precedes 15, 15 precedes 30, and 2 precedes 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 中访问 next。

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

问题

是否可以检索流中的下一个值？
我应该使用 map 并映射到 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());
}

它肯定比具有大循环的命令式解决方案更好，但就 "using a stream" 的目标而言，以惯用的方式仍然有点无聊。

Is it possible to retrieve the next value in a stream?

不，不是真的。我所知道的最好的引用是在 java.util.stream package description:

The elements of a stream are only visited once during the life of a stream. Like an Iterator, a new stream must be generated to revisit the same elements of the source.

（检索除当前正在操作的元素之外的元素将意味着它们可以被多次访问。）

从技术上讲，我们还可以通过其他几种方式来实现：

庄严地（非常无聊）。
使用流的 iterator 技术上 仍在使用流。

Answer 2

它不是单线（它是双线），但它有效：

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

不是通过 "looking at the next element" 来解决它，而是通过“查看 上一个 元素来解决它，reduce() 免费给你。我有通过注入一个代码片段来改变其预期用途，该代码片段根据先前元素和当前元素的比较来填充列表，然后 returns 当前元素，因此下一次迭代会将其视为其先前元素。

一些测试代码：

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 3

这不是一个纯粹的 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 operation internally implemented using custom spliterator。因此，您拥有非常干净的代码，它不依赖于源是 List 还是其他任何东西。当然它也适用于并行流。

为此任务提交了 testcase。

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 性能的影响。

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

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

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 并行，然后决定使用哪个收集器 return。

Answer 5

如果您愿意使用第三方库并且不需要并行性，那么jOOλ 提供SQL-style window 函数如下

System.out.println(
Seq.of(10, 1, 15, 30, 2, 6)
   .window()
   .filter(w -> w.lead().isPresent() && w.value() < w.lead().get())
   .map(w -> w.value())
   .toList()
);

屈服

[1, 15, 2]

lead()函数从window.

中按遍历顺序访问下一个值

免责声明：我为 jOOλ 背后的公司工作

Answer 6

您可以通过使用有界队列来存储流经流的元素来实现这一点（这是基于我在此处详细描述的想法：

下面的示例首先定义了 BoundedQueue class 的实例，它将存储通过流的元素（如果您不喜欢扩展 LinkedList 的想法，请参阅上面提到的 link 替代和更通用的方法）。稍后您只需检查两个后续元素 - 感谢助手 class:

public class Kata {
  public static void main(String[] args) {
    List<Integer> input = new ArrayList<Integer>(asList(10, 1, 15, 30, 2, 6));

    class BoundedQueue<T> extends LinkedList<T> {
      public BoundedQueue<T> save(T curElem) {
        if (size() == 2) { // we need to know only two subsequent elements
          pollLast(); // remove last to keep only requested number of elements
        }

        offerFirst(curElem);
        return this;
      }

      public T getPrevious() {
        return (size() < 2) ? null : getLast();
      }

      public T getCurrent() {
        return (size() == 0) ? null : getFirst();
      }
    }

    BoundedQueue<Integer> streamHistory = new BoundedQueue<Integer>();

    final List<Integer> answer = input.stream()
      .map(i -> streamHistory.save(i))
      .filter(e -> e.getPrevious() != null)
      .filter(e -> e.getCurrent() > e.getPrevious())
      .map(e -> e.getPrevious())
      .collect(Collectors.toList());

    answer.forEach(System.out::println);
  }
}

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

How to use Java 8 streams to find all values preceding a larger value?

java

java-8

java-stream

用例

非流解决方案

我试过的

问题

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

How to use Java 8 streams to find all values preceding a larger value?

java

java-8

java-stream

用例

非流解​​决方案

我试过的

问题

非流解决方案