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

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缓存缓冲区。但是，这有两个问题：

• 如何合并和维护读取流的顺序和同步？
• 你如何确保数字是毫不拖延地写出来的？因为一旦执行了写入，就无法再确保流中任何其他数字的写入顺序？

我

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

Answer 1

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

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

这些货币对给我们买的是，我们可以将它们放在优先级队列中。 这允许我们实现类似这样的逻辑：

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位。