在Ruby中懶散地合併N個排序的數組

Question

如何在Ruby中懶散地合併N個排序的數組（或其他類列表數據結構）？例如，在Python中，您可以使用heapq.merge。 Ruby中必須有這樣的內容，對吧？

Answer 1

我最終自己使用'算法'gem中的數據結構來編寫它。這並沒有我想象的那麼糟糕。

require 'algorithms' 

class LazyHeapMerger 
    def initialize(sorted_arrays) 
    @heap = Containers::Heap.new { |x, y| (x.first <=> y.first) == -1 } 
    sorted_arrays.each do |a| 
     q = Containers::Queue.new(a) 
     @heap.push([q.pop, q]) 
    end 
    end 

    def each 
    while @heap.length > 0 
     value, q = @heap.pop 
     @heap.push([q.pop, q]) if q.size > 0 
     yield value 
    end 
    end 
end 

m = LazyHeapMerger.new([[1, 2], [3, 5], [4]]) 
m.each do |o| 
    puts o 
end 

Answer 2

不，沒有什麼內置的做到這一點。至少，沒有什麼會立即想到。然而，幾年前有一個GSoC project來實現相關的數據類型，您可以使用它。

Answer 3

下面是一個（略golfed）解決方案，應該在支持#first，#shift，並#empty?任何名單樣「收藏的數組。請注意，它具有破壞性 - 每次撥打lazymerge時，都會從一個集合中刪除一個項目。

def minheap a,i 
    r=(l=2*(m=i)+1)+1 #get l,r index 
    m = l if l< a.size and a[l].first < a[m].first 
    m = r if r< a.size and a[r].first < a[m].first 
    (a[i],a[m]=a[m],a[i];minheap(a,m)) if (m!=i) 
end 


def lazymerge a 
    (a.size/2).downto(1){|i|minheap(a,i)} 
    r = a[0].shift 
    a[0]=a.pop if a[0].empty? 
    return r 
end 

p arrs = [ [1,2,3], [2,4,5], [4,5,6],[3,4,5]] 
v=true 
puts "Extracted #{v=lazymerge (arrs)}. Arr= #{arrs.inspect}" while v 

輸出：

[[1, 2, 3], [2, 4, 5], [4, 5, 6], [3, 4, 5]] 
Extracted 1. Arr= [[2, 3], [2, 4, 5], [4, 5, 6], [3, 4, 5]] 
Extracted 2. Arr= [[3], [2, 4, 5], [4, 5, 6], [3, 4, 5]] 
Extracted 2. Arr= [[4, 5], [3], [4, 5, 6], [3, 4, 5]] 
Extracted 3. Arr= [[4, 5], [3, 4, 5], [4, 5, 6]] 
Extracted 3. Arr= [[4, 5], [4, 5], [4, 5, 6]] 
Extracted 4. Arr= [[5], [4, 5], [4, 5, 6]] 
Extracted 4. Arr= [[5], [5], [4, 5, 6]] 
Extracted 4. Arr= [[5, 6], [5], [5]] 
Extracted 5. Arr= [[6], [5], [5]] 
Extracted 5. Arr= [[5], [6]] 
Extracted 5. Arr= [[6]] 
Extracted 6. Arr= [[]] 
Extracted . Arr= [[]] 

還要注意，這種算法也懶得保持堆的特性 - 它不保持通話之間。這可能會導致它做更多的工作，因爲它會在每次後續的呼叫中完成堆積。這可以通過先完成一次完整的堆垛來修復，然後在return r之前呼叫minheap(a,0)。

Answer 4

這是一個應該在任何Enumerable上工作的實現，甚至是無限的。它返回枚舉器。

def lazy_merge *list 
    list.map!(&:enum_for) # get an enumerator for each collection 
    Enumerator.new do |yielder| 
    hash = list.each_with_object({}){ |enum, hash| 
     begin 
     hash[enum] = enum.next 
     rescue StopIteration 
     # skip empty enumerators 
     end 
    } 
    loop do 
     raise StopIteration if hash.empty? 

     enum, value = hash.min_by{|k,v| v} 
     yielder.yield value 
     begin 
     hash[enum] = enum.next 
     rescue StopIteration 
     hash.delete(enum) # remove enumerator that we already processed 
     end 
    end 
    end 
end 

Infinity = 1.0/0 # easy way to get infinite range 

p lazy_merge([1, 3, 5, 8], (2..4), (6..Infinity), []).take(12) 
#=> [1, 2, 3, 3, 4, 5, 6, 7, 8, 8, 9, 10]