时间戳

首页 > 解决方案 > 合并多个流并写入已排序的输出流

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

问题描述

我最近在几次采访中偶然发现了这个问题。它如下：

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

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

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

标签： javaalgorithmdata-structureslinked-list

解决方案

I shall assume that there are many streams, and each gives data in increasing order.

Now your stream interface has a small problem. You can build on top of that a class that consists of pairs (lastValue, stream) which has methods peek (returns lastValue) and readNext (if stream.isClosed() returns null, else returns the pair (stream.read(), stream). And one more thing, we can add a compareTo method that first compares lastValue and then compares stream.hashCode().

What these pairs buy us is that we can put them in a PriorityQueue. Which allows us to implement something like this logic:

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

If n is the total amount of data between the streams, and m is the number of streams, this algorithm will take time O(n log(m) + m). The + m bit only shows up if you started with a lot of streams that were closed.

推荐阅读