Сливать N отсортированных массивов в ruby ​​лениво - PullRequest
Новая
       5

Сливать N отсортированных массивов в ruby ​​лениво

5 голосов
/ 26 апреля 2011

Как можно лениво объединять N отсортированных массивов (или других структур, подобных списку) в Ruby? Например, в Python вы бы использовали heapq.merge. Должно быть что-то вроде этого, встроенное в Ruby, верно?

Ответы [ 4 ]

1 голос
/ 26 апреля 2011

Вот реализация, которая должна работать с любыми перечисляемыми, даже бесконечными. Возвращает перечислитель. 

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]
1 голос
/ 26 апреля 2011

Вот решение (слегка приглушенное), которое должно работать с массивами любых коллекций типа списка, которые поддерживают #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= [[]]

Обратите также внимание, что этот алгоритм также ленив о поддержании свойства кучи - он не поддерживается между вызовами.Это, вероятно, заставляет его выполнять больше работы, чем необходимо, поскольку он выполняет полную кучи при каждом последующем вызове.Это можно исправить, выполнив полную кучу один раз, затем вызвав minheap(a,0) перед строкой return r.

1 голос
/ 26 апреля 2011

Я закончил писать сам, используя структуры данных из гема «алгоритм». Это было не так плохо, как я ожидал. 

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
0 голосов
/ 26 апреля 2011

Нет, для этого нет ничего встроенного.По крайней мере, ничего, что мгновенно приходит на ум.Однако пару лет назад существовал GSoC-проект для реализации соответствующих типов данных, которые вы могли бы использовать.

...