Combinar matrices ordenadas N en ruby ​​perezosamente

Question

¿Cómo fusiona ordenadamente N matrices ordenadas (u otras estructuras de datos similares a listas) en Ruby? Por ejemplo, en Python usaría heapq.merge. Debe haber algo como esto integrado en Ruby, ¿verdad?

Answer 1

Terminé escribiéndolo usando las estructuras de datos de la gema 'algoritmo'. No fue tan malo como esperaba.

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

No, no hay nada integrado para hacer eso. Al menos, nada que salte al instante a la mente. Sin embargo, hubo un GSoC project para implementar los tipos de datos relevantes hace un par de años, que podría utilizar.

Answer 3

Aquí hay una solución (ligeramente golfizada) que debería funcionar en arreglos de cualquier colección 'lista-como' que soporte #first, #shift y #empty?. Tenga en cuenta que es destructivo: cada llamada al lazymerge elimina un elemento de una colección.

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 

Salida:

[[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= [[]] 

Tenga en cuenta también que este algoritmo también es vago sobre el mantenimiento de la propiedad del montículo - no se mantiene entre las llamadas. Esto probablemente hace que trabaje más de lo necesario, ya que realiza una heapificación completa en cada llamada posterior. Esto podría solucionarse haciendo un heapify completo una vez en el frente, luego llamando al minheap(a,0) antes de la línea return r.

Answer 4

Aquí hay una implementación que debería funcionar en cualquier Enumerable, incluso infinitos. Devuelve el Enumerador.

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]