java - 合并多个流并写入排序的输出流

Question

我最近在几次采访中偶然发现了这个问题。它是这样的:

您有一个可以异步读取的数字流列表。给定一个消费者的写入流，您将如何从流中读取数字，对它们进行合并和排序，最后写入输出流？

Input:

 1. stream 1: 1, 2, 3, 4...
 2. stream 2: 1, 2, 3, 4, 5...

Output: 1, 1, 2, 2, 3, 3, 4, 4, 5....

我们可以假设合约如下:

final class Stream {
   public interface boolean isClosed();
   public interface int read();
}

// utility method to write numbers to consumer stream
public void write(Integer number);

我对这个问题的最初想法是它类似于 LRU cache buffer .但是，这有两个问题:

• 如何合并和维护读取流的顺序和同步？
• 您如何确保没有任何延迟地写入数字？一旦执行写入，就无法再确保流中任何其他数字的写入顺序？

我确信这里有一个警告我误解了或完全错过了。在这方面的任何帮助都会很棒。谢谢。

Answer 1

我假设有很多流，每个流都按递增顺序提供数据。

现在你的流接口(interface)有一个小问题。您可以在此基础上构建一个由 (lastValue, stream) 对组成的类，该类具有方法 peek(返回 lastValue)和 readNext(如果 stream.isClosed() 返回 null，否则返回对 (stream.read(), stream) .还有一件事，我们可以添加一个compareTo方法，它首先比较lastValue，然后比较stream.hashCode()。

这些对给我们带来的是，我们可以将它们放在 PriorityQueue 中.这允许我们实现类似这样的逻辑:

construct initial pairs from streams
put them into a priority queue named pq
while 0 < pq.size()
    take the smallest pair p
    print p.peek()
    pNext = p.readNext()
    if pNext != null
        add pNext to pq

如果n是流之间的数据总量，m是流的数量，这个算法需要时间O(n log( m) + m)。 + m 位仅在您从关闭的大量流开始时显示。