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

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

提问by Pete

Use Case

用例

Through some coding Katas posted at work, I stumbled on this problem that I'm not sure how to solve.

通过在工作中发布的一些编码 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.

使用 Java 8 Streams，给定一个正整数列表，生成一个整数列表，其中整数位于更大的值之前。

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

上述输入将产生：

[1, 15, 2]

因为1在15之前，15在30之前，2在6之前。

Non-Stream Solution

非流解决方案

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;
}

What I've Tried

我试过的

The problem I have is I can't figure out how to access next in the lambda.

我遇到的问题是我不知道如何在 lambda 中访问 next 。

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

Question

题

• Is it possible to retrieve the next value in a stream?
• Should I be using mapand mapping to a Pairin order to access next?

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

采纳答案by Radiodef

Using IntStream.range:

使用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());
}

It's certainly nicer than an imperative solution with a large loop, but still a bit meh as far as the goal of "using a stream" in an idiomatic way.

它当然比带有大循环的命令式解决方案更好，但就以惯用方式“使用流”的目标而言，它仍然有点不合理。

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

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

Nope, not really. The best cite I know of for that is in the java.util.streampackage description:

不，不是真的。我所知道的最好的引用是在java.util.stream包描述中：

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，必须生成新的流以重新访问源的相同元素。

(Retrieving elements besides the current element being operated on would imply they could be visited more than once.)

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

We could also technically do it in a couple other ways:

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

• Statefully (very meh).
• Using a stream's iteratoris technicallystill using the stream.

• 有状态（非常meh）。
• 使用流iterator在技术上仍然是使用流。

回答by Bohemian

It's not a one-liner (it's a two-liner), but this works:

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

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

Rather than solving it by "looking at the next element", this solves it by "looking at the previouselement, which reduce()give you for free. I have bent its intended usage by injecting a code fragment that populates the list based on the comparison of previous and current elements, then returns the current so the next iteration will see it as its previous element.

这不是通过“查看下一个元素”来解决它，而是通过“查看前一个元素来解决它，它reduce()免费为您提供。我通过注入一个代码片段来弯曲它的预期用途，该代码片段基于比较前一个和当前元素，然后返回当前元素，以便下一次迭代将其视为其前一个元素。

---

---

Some test code:

一些测试代码：

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);

Output:

输出：

[1, 15, 2]

回答by Tagir Valeev

That's not a pure Java8, but recently I've published a small library called StreamExwhich has a method exactly for this task:

这不是纯 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);

The pairMapoperation internally implemented using custom spliterator. As a result you have quite clean code which does not depend on whether the source is Listor anything else. Of course it works fine with parallel stream as well.

该pairMap操作使用自定义的内部实现spliterator。因此，您拥有非常干净的代码，不依赖于源是List还是其他任何东西。当然，它也适用于并行流。

Committed a testcasefor this task.

为此任务提交了一个测试用例。

回答by Alexis C.

The accepted answer works fine if either the stream is sequential or parallel but can suffer if the underlying Listis not random access, due to multiple calls to get.

如果流是顺序的或并行的，则接受的答案工作正常，但如果底层List不是随机访问，则可能会受到影响，因为多次调用get.

If your stream is sequential, you might roll this collector:

如果您的流是连续的，您可能会滚动此收集器：

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");
            });
}

and a usage:

和用法：

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

Nevertheless you could also implement a collector so thats works for sequential and parallel streams. The only thing is that you need to apply a final transformation, but here you have control over the Listimplementation so you won't suffer from the getperformance.

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

The idea is to generate first a list of pairs (represented by a int[]array of size 2) which contains the values in the stream sliced by a window of size two with a gap of one. When we need to merge two lists, we check the emptiness and merge the gap of the last element of the first list with the first element of the second list. Then we apply a final transformation to filter only desired values and map them to have the desired output.

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

It might not be as simple as the accepted answer, but well it can be an alternative solution.

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

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()));
}

You can then wrap these two collectors in a utility collector method, check if the stream is parallel with isParallelan then decide which collector to return.

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

回答by Lukas Eder

If you're willing to use a third party library and don't need parallelism, then jOOλoffers SQL-style window functions as follows

如果你愿意使用第三方库并且不需要并行，那么jOOλ提供了 SQL 风格的窗口函数如下

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()
);

Yielding

屈服

[1, 15, 2]

The lead()function accesses the next value in traversal order from the window.

该lead()函数从窗口中按遍历顺序访问下一个值。

Disclaimer: I work for the company behind jOOλ

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

回答by walkeros

You can achieve that by using a bounded queue to store elements which flows through the stream (which is basing on the idea which I described in detail here: Is it possible to get next element in the Stream?

您可以通过使用有界队列来存储流经流的元素来实现这一点（这是基于我在此处详细描述的想法：Is it possible to get next element in the Stream?

Belows example first defines instance of BoundedQueue class which will store elements going through the stream (if you don't like idea of extending the LinkedList, refer to link mentioned above for alternative and more generic approach). Later you just examine the two subsequent elements - thanks to the helper class:

下面的示例首先定义了 BoundedQueue 类的实例，该类将存储通过流的元素（如果您不喜欢扩展 LinkedList 的想法，请参阅上面提到的链接以获取替代和更通用的方法）。稍后您只需检查两个后续元素 - 感谢 helper 类：

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);
  }
}