Загрузка...

Ruby & Rails: веб-разработка с удовольствием

Ruby on Rails — фреймворк для создания веб-приложений. Является открытым программным обеспечением (лицензия MIT). Здесь мы обсуждаем новости RoR, делимся учебными материалами и интересными находками С RoR даже сложные веб-приложения могут быть написаны за считанные дни. Это действительно разработка с удовольствием!
     

10. Metaprogramming patterns. 15 кю. Ленивые контейнеры

20.04.09, 01:58
Автор artem.voroztsov

Этот пост также отчасти навеян статьей Томаса Дейва про pipelines. Если бы мне пришло в голову делать в ruby аналог команды pipe "|" для командной строки, то я бы лучше добавил метод to_lazy для Enumerables, который возвращал бы LazyEnumerable. Есть по крайней мере три концептуально разных способа реализации LazyEnumerable - 1) с помощью вложенных лямбд и 2) с помощью alias_method_chain 3)  с помощью Fiber.

Способы 1 и 2 похожи. Можно сказать, что способ 1 неявно использует идею alias_method_chain, про которую уже неоднократно писалось в этом блоге. С помощью alias_method_chain можно было бы расширять метод each различными фичами связанными с преобразованиями (map) и фильтрацией (select, uniq, delete_if, ..). Здесь я продемонстрирую лишь способ 1.

Итак,

Задача. Необходимо реализовать класс LazyContainer так, чтобы код

Emumerator.module_eval do
  def to_lazy
    LazyContainer.new(this)
  end
end
container.map{|i| f(i)}.select{|i| g(i)}.uniq.each {|i| puts i}

не создавал бы в памяти три промежуточных массива, а осуществлял передачу данных по некоторой незримой "трубе".

Напишу сразу на ruby, так как переводить это на русский довольно сложно и не факт, что нужно. Лишь одна подсказка @pipe_lambda - это лямбда, которая постепенно наращивается (по мере применения различных методов-итераторов map, select, uniq, delete_if, ...). Эта лямбда получает в аргументе элемент исходного контейнера и  возвращает пару - новый преобразованный элемент контейнера и флаг, определяющий нужно его возвращать или нет (он может быть отфильтрован одним из фильтрующих методов (select, uniq, delete_if, take, ...)).

Итак, вот файл lazyenum.rb:

module LazyEnumerable
  include Enumerable
  
  ZERO_PIPE_LAMBDA  = lambda {|i| [i,true]}
  ZERO_RESET_LAMBDA = lambda {}
  def self.included(klass)
    klass.class_eval < < -EOE
      alias each_orig each
      def each(&block)
        @pipe_lambda ||= ZERO_PIPE_LAMBDA
        each_orig do |elem|
          value,take = @pipe_lambda[elem]
          block[value] if take
        end
        @reset_lambda ||= ZERO_RESET_LAMBDA
        @reset_lambda.call
      end
    EOE
  end
    
  def map!(&block)
    old_pipe = @pipe_lambda ||= ZERO_PIPE_LAMBDA
    @pipe_lambda = lambda do |i|
      value,take = old_pipe[i]
      take ? [block[value], take] : [nil, false]
    end
    self
  end
  
  def select!(&block)
    old_pipe = @pipe_lambda ||= ZERO_PIPE_LAMBDA
    @pipe_lambda = lambda do |i|
      value,take = old_pipe[i]
      take ? [value, block[value]] : [nil, false]
    end
    self
  end
  
  def uniq!(&block)
    old_pipe  = @pipe_lambda ||= ZERO_PIPE_LAMBDA
    old_reset = @reset_lambda ||= ZERO_RESET_LAMBDA
    filter = Hash.new{|h,k| h[k]={}}
    
    @reset_lambda = lambda do
      old_reset.call
      filter[self].clear
    end
    
    @pipe_lambda = lambda do |i|
      value,take = old_pipe[i]
      take ? (
        if filter[self][value]
          [nil, false]
        else
          filter[self][value] = true
          [value, true]
        end
      ) : [nil, false]
    end
    self
  end
  make_nobang :uniq, :map, :select
end
class LazyContainer
  def initialize(enum)
    @enum = enum
  end
  def each(&block)
    @enum.each(&block)
  end
  include LazyEnumerable
end

Метод  make_nobang мы реализовали здесь.

Чтобы проверить, что возникла экономия памяти, напишем метод mem_used и задействуем gnuplot:

require 'lazyenum'
def mem_used(gc_start=false,&block)
    GC.start; 
    before = `ps -o rss= -p #$$`.to_i 
    block.call
    GC.start if gc_start
    after = `ps -o rss= -p #$$`.to_i 
    after - before
end
res = []
x  = []
y1 = []
y2 = []
(1..10).each do |a|
  size = a * 10000
  x < < size
  cnt = (0..size)
  l = lambda do 
    res < < cnt.map{|i| i/2}.uniq.select{|i| i % 3 == 0}.to_a
    puts res.last.size
  end
  y1 < < mem_used(&l)
  cnt = cnt.to_lazy
  y2 < < mem_used(&l)
end
require 'rubygems'
require 'gnuplot'
Gnuplot.open do |gp|
  Gnuplot::Plot.new( gp ) do |plot|
      
    plot.title  "Memory usage of LazyContainer"
    plot.xlabel "container size"
    plot.ylabel "memory, Kb"
      
    ds1 = Gnuplot::DataSet.new( [x,y1] ) do |ds|
      ds.title = "array"
      ds.with = "lines"
      ds.linewidth = 4
    end
    ds2 = Gnuplot::DataSet.new( [x,y2] ) do |ds|
      ds.title = "lazy enum"
      ds.with = "lines"
      ds.linewidth = 4
    end
    plot.data < < ds1
    plot.data < < ds2
  end
end

Все файлы прикрепил. Файл lazyenum.rb содержит также небольшой unit-test.

Задание для самостоятельного решения

1. Реализуйте LazyEnumerable с помощью Fiber. Убедитесь что проходятся все тесты из прикреплённого файла lazyenum.rb. (12 кю)

2. Реализуйте LazyEnumerable с помощью alias_method_chain применяемого к методу each. Убедитесь, что проходятся все тесты из прикреплённого файла lazyenum.rb. (13 кю)

3. Для модуля LazyEnumerable допишите ленивые реализации методов [], delete_if, take_while, skip_first(n=1). (15 кю)

4. Реализуйте кеширование внутри модуля LazyEnumerable (это полезно если метод each вызывается несколько раз). (13 кю)

5. Реализуйте ленивый контейнер, который содержит ВСЕ (то есть бесконечное количество элементов) числа Фибоначчи и при итерировании на каждое число F(n) тратит время не более O(log(n)). (15 кю)

Удачи!

См. также

Предыдущий пост:

9. Metaprogramming patterns — 13 кю. Метод serialize и управление методами dump & load отдельных частей

список файлов:
lazycontainer.jpg
lazyenum.rb
lazyenumtest.rb

Комментарии

Идея навеяна LINQ-ом?

Нет. С LINQ не знаком. Но заинтересовался и почитал. Пока не смог найти каким образом LINQ мог бы это навеять. Идея навеяна парой Haskell + pipelines

Войдите, чтобы оставить комментарий