如何连续查看排序流列表中的最低元素

Question

我开始学习 Java 流，我想知道是否可以只查看流的第一个元素而不检索它。

例如，我有多个流，每个流都有按非递减顺序排序的整数，我想获得所有整数的排序列表，所以我正在考虑使用 PrioirtyQueue<Stream> 也按非降序排序。

但是，为了让 PrioirtyQueue<Stream> 对流进行排序，我需要为流传入一个比较器以按第一个元素比较流，但我不确定如何查看第一个元素在每个流中。

例如，我有以下流。

[1, 2, 3, 5],
[0, 2, 4, 6]

我想编写一个函数 getNextInteger()，它处理 排序流 的列表。

每次我调用该方法时，它都会 returns 下一个最小整数，因此如果我调用该方法 4 次，结果可能是 [0,1,2,2]。

我想使用 PriorityQueue 按流的第一个值对流进行排序，并检索最小的值并在流不为空时重新排队。

Answer 1

Stream 是对数据源进行迭代的一种方式，它的目的是处理数据，而不是存储数据。

因此，您的问题本质上是不正确的。简短的回答是否定的。

它不是数据结构，您不能像访问 List 或 [=19= 中的元素那样访问流中的元素].

看看 documentation:

Collections and streams, while bearing some superficial similarities, have different goals. Collections are primarily concerned with the efficient management of, and access to, their elements. By contrast, streams do not provide a means to directly access or manipulate their elements, and are instead concerned with declaratively describing their source and the computational operations which will be performed in aggregate on that source.

正如我所说，stream 是一种迭代的方式，但是stream pipeline 也不同于Iterator。 Iterator 允许一个一个地检索元素。相反，stream pipeline 将被执行并产生结果（作为单个值或值的集合）并将被关闭，或者不会被执行。取决于stream有没有终端操作。

例如，这个 stream 是有效的，它可以正常编译，但不会被执行：

Stream.of("a", "b", "c").map(String::toUpperCase);

因为缺少终端操作

每个 stream 应该有一个 source 和一个触发执行的 terminal operation管道并产生结果。 map() 和 filter() 等旨在转换流的中间操作是可选的。

您无法从 stream 中获取数据而不对其进行处理。而且一经处理，就不能再使用了。

作为此问题的可能补救措施，您可以考虑用一个对象包装流，该对象将分别维护来自流源的第一个元素和流本身。

public record StreamWrapper(int first, IntStream stream) {}

可以使用该方法，通过单个值比较流就足够了，该值应该从流源中提取（如果流源允许）在生成流的同时。

更新

I want to write a function getNextInteger(), that handles a list of sorted streams.

Every time I call the method, it returns the next smallest integer, so the result might be [0,1,2,2] if I call the method 4 times.

该任务不适合流。除非你对每个流中的数据都已经排序这一事实视而不见。

如果我们将所有流合并为一个并应用排序，它不会像开始时那样造成巨大的性能损失。为了对数据流进行排序，将所有元素转储到一个数组中，在这种情况下，该数组将由排序后的子数组组成。因为引用类型的数组将使用 Timsort 进行排序，算法实现将发现所有这些排序的块。 IE。对由部分排序的子数组组成的数组进行排序与从头开始对所有这些数据进行排序不同。因此，我们可以将其视为一种可能的选择：

List<Stream<Integer>> streams =
List.of(Stream.of(1, 3), Stream.of(5), Stream.of(2, 6, 7),
        Stream.of(4, 9, 10), Stream.of(8));
        
streams.stream()
    .flatMap(Function.identity())
    .sorted()
    .forEach(num -> System.out.print(num + " "));

将产生输出：

1 2 3 4 5 6 7 8 9 10

如果打印（或存储到集合）按升序排序的整体数据似乎不令人满意，并且您坚持只检索单个值作为结果方法调用，我要重申，不可能从流中连续地一个一个地获取值。

为此你需要一个 Iterator 作为 documentation 的建议：

However, if the provided stream operations do not offer the desired functionality, the BaseStream.iterator() and BaseStream.spliterator() operations can be used to perform a controlled traversal.

您可以实施一个 custom iterator，它将在后台使用 PriorityQueue。

我假设流是实现 Comparable 的类型并且流是排序的（就像您提供的示例）。

迭代器：

public class QueueBasedIterator<T extends Comparable<T>> implements Iterator<T> {
    private Queue<IteratorWrapper<T>> nextValues = new PriorityQueue<>();
    private List<Iterator> iterators = new ArrayList<>();
    
    @SafeVarargs
    public StreamBasedIterator(Stream<T>... streams) {
        this.iterators = Stream.of(streams).map(Stream::iterator)
            .collect(Collectors.toList());
        
        for (int i = 0; i < iterators.size(); i++) {
            Iterator<T> iterator = iterators.get(i);
            if (iterator.hasNext()) 
                nextValues.add(new IteratorWrapper<T>(i, iterator.next()));
        }
    }
    
    @Override
    public boolean hasNext() {
        return !nextValues.isEmpty();
    }
    
    @Override
    public T next() {
        if (nextValues.isEmpty()) {
            throw new NoSuchElementException();
        }
        
        IteratorWrapper<T> next = nextValues.remove();
        Iterator<T> iterator = iterators.get(next.getPosition());
        if (iterator.hasNext())
            nextValues.add(new IteratorWrapper<T>(next.getPosition(), iterator.next()));
        
        return next.getValue();
    }
}

IteratorWrapper:

class IteratorWrapper<T extends Comparable<T>> implements Comparable<IteratorWrapper<T>> {
    private T value;
    private int position;
    
    public IteratorWrapper(int position, T value) {
        this.value = value;
        this.position = position;
    }
    
    public T getValue() {
        return value;
    }
    
    public int getPosition() {
        return position;
    }
    
    @Override
    public int compareTo(IteratorWrapper<T> o) {
        return this.value.compareTo(o.value);
    }
}

main() - 演示

public static void main(String[] args) {
    QueueBasedIterator<Integer> iterator =
        new QueueBasedIterator<>(Stream.of(1, 3), Stream.of(5), Stream.of(2, 6, 7),
                                 Stream.of(4, 9, 10), Stream.of(8));
    
    while (iterator.hasNext()) {
        System.out.print(iterator.next() + " ");
    }
}

输出

1 2 3 4 5 6 7 8 9 10

Answer 2

I am wondering is it possible to only peek the first element of the stream without retrieving it.

没有。 Peek 是一个 intermediate operation，如 map, sort 等。它们不会导致流开始传送数据。为此，需要 terminal operation（例如 reduce, forEach, or collector）等来启动流式传输过程。

这还允许人们在不存储任何数据的情况下执行以下操作。如果是这样，第一个语句 (series) 永远不会完成，因为它需要无限存储，因为没有限制方法。

IntStream series = IntStream.iterate(0, i->i+1);
IntStream first10 = series.limit(10);
int[] toArray = first10.toArray();

System.out.println(Arrays.toString(toArray));

版画

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

在上面的例子中，toArray()是启动流的终端操作。完成后，流将耗尽，并且可以再次使用上述分配中的 none（例如 series, first10）。

如何连续查看排序流列表中的最低元素

How to Peek the Lowest elements from a List of sorted Streams continously

java

sorting

java-stream

priority-queue

更新