- PVSM.RU - https://www.pvsm.ru -
Недавно мой патч Enumerable::Lazy
был принят [1] в ruby trunk. А это значит что в ruby 2.0 мы сможем:
a = [1,2,3,4,2,5].lazy.map { |x| x * 10 }.select { |x| x > 30 } #=> вычисление не происходит
a.to_a #=> [40, 50], объект вычисляется за один проход.
Ruby прекрасен, и, являясь императивным языком, тем не менее позволяет нам писать элегантный "функциональный" код. К примеру:
data.map(&:split).map(&:reverse)
выглядит намного читабельней чем:
data.map { |l| l.split.reverse }
Однако, первый пример является неэффективным: преобразовывая data
, Ruby дважды проходится по данным, генерируя промежуточный массив. До тех пор пока объем данных невелик, этот недостаток не является критичным. Но, предположим, мы парсим огромный файл:
File.open("text") do |f|
f.each.flat_map(&:split).grep(/ruby/)
end
В этом случае двойной проход по массиву недопустим. К счастью, с появлением Enumerable::Lazy
это уже не проблема. Ленивые версии функций map
, select
и многих других, переопределенные в классе Enumerable::Lazy
, не производят вычисление сразу. Вместо этого они возвращают экземпляр Enumerable::Lazy
, позволяя строить цепочки ленивых вычислений.
Трудно сказать, кто первым придумал как с помощью Enumerator
можно реализовать в Ruby ленивые вычисления. Возможно этот пост [2] 2008 года был одним из первых. Идея реализации проста и основана на замечательном свойстве объктов Enumerator — их можно соединять в цепочки. С тех пор было опубликовано [3] множество [4] статей [5], а в enumerator.c были добавлены комментарии с пояснениями идеи. Дискуссия на ruby-lang [6] длилась более трех лет, и наконец Matz проголосовал [7] за реализацию Yataka Hara [8].
В ней был предложен метод Enumerable::lazy
, который "оборачивает" массив в экземпляр Enumerable::Lazy
, который, в свою очередь, используется для построения ленивой цепочки. Был озвучен запрос патча [9] на Си и я незамедлительно принял вызов. К слову, я совсем недавно заинтересовался функциональным программированием, да и покопаться во внутренностях Ruby было очень интерестно. В результате я сподобился на пул реквест [10], который, после незначительного рефакторинга, был принят [1] несколько дней назад. Вмерджили его в trunk и он выйдет в Ruby 2.0 (смотреть roadmap [11]).
Для тех, кто не в курсе что такое обычный Enumerator и с чем его едят:
enum = [1, 2].each
puts enum.next #=> 1
puts enum.next #=> 2
puts enum.next #=> StopIteration exception raised
enum = Enumerator.new do |yielder|
yielder << 1
yielder << 2
end
puts enum.next #=> 1
puts enum.next #=> 2
puts enum.next #=> StopIteration exception raised
enum = "xy".enum_for(:each_byte)
enum.each { |b| puts b }
# => 120
# => 121
o = Object.new
def o.each
yield
yield 'hello'
yield [1, 2]
end
enum = o.to_enum
p enum.next #=> nil
p enum.next #=> 'hello'
p enum.next #=> [1, 2]
enum = %w{foo bar baz}.map
puts enum.with_index { |w, i| "#{i}:#{w}" } # => ["0:foo", "1:bar", "2:baz"]
# защита данных от изменений
a = [1, 2, 3]
some_method(a.enum_for)
[1,2,3].cycle.take(10) #=> [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]
Как вы уже наверное догадались, методы #to_enum
и #enum_for
находятся в модуле Kernel
, а значит доступны любому объекту. Примеры взяты из enumerator.c [12], если интерестно можно глянуть еще и тут: test/ruby/test_enumerator.rb [13]. Сишные внутренности Enumerator
наверное заслуживают отдельного поста, но стоит заметить, что вся эта магия с next
реализована с помощью Fiber.
Чтобы понять как работает Enumerable::Lazy достаточно взглянуть на этот код:
module Enumerable
class Lazy < Enumerator
def initialize(obj)
super() do |yielder|
obj.each do |val|
if block_given?
yield(yielder, val)
else
yielder << val
end
end
end
end
def map
Lazy.new(self) do |yielder, val|
yielder << yield(val)
end
end
end
end
a = Enumerable::Lazy.new([1,2,3])
a = a.map { |x| x * 10 }.map { |x| x - 1 }
puts a.next #=> 9
puts a.next #=> 19
Эта типичная реализация на Ruby, которую предложил Yutaka [14]. Но обратите внимание — в этом примере я не использую &block
как параметр метода (чтобы сконвертить в Proc и вызывать call
). Вместо этого мы можем yield
ить прямо внутри блока для each
! block_given?
также работает как полагается. Более того, находясь внутри блока, мы все равно можем вызывать self
(как и return
). Здорово, не правда ли? Замечательный пост на эту тему [15] от Yehuda Katz (еще один [16]).
Сам по себе код достаточно прост, но давайте разберемся подробнее: Как уже было сказано, основная идея в построении цепочки. Поэтому Enumerable::Lazy#map
создает новый экземпляр Enumerable::Lazy
передавая ему "предыдущий" объект как аргумент. При вызове to_a
(next
, each
с блоком, take
и т.п.) происходит вычисление: Ruby возвращается обратно к началу цепочки (Рис. 1), получает следующее значение из первоначального объекта и возвращает его наружу, последовательно модифицируя блоками ленивых методов (в том же порядке, в котором они были "навешены").
Рис.1 Цепочка ленивых енумераторов.
Мой патч на Си [17] полностью повторяет имплементацию на Ruby. За исключением того факта, что вместо вызова super
напрямую внутри lazy_initialize
я создаю и инициализирую генератор (Enumerator::Generator
), который передается как аргумент енумератору.
В финальном патчe [18] nobu [19] слегка отрефакторил код: if-else условие внутри функции-блока он разделил на два отдельных метода (lazy_init_block_i
and lazy_init_block
), а само условия перенес в lazy_initialize
.
Также, вместо того, чтобы передавать Ruby массив как параметр в функцию-блок, он конструирует обычный Си массив с параметрами. Соответственно, теперь не нужно использовать rb_ary_entry
, чтобы получить yielder
и значение внутри блока.
Например, это:
static VALUE lazy_map_func(VALUE val, VALUE m, int argc, VALUE *argv)
{
VALUE result = rb_funcall(rb_block_proc(), id_call, 1,
rb_ary_entry(val, 1));
return rb_funcall(rb_ary_entry(val, 0), id_yield, 1, result);
}
превратилось в это:
static VALUE lazy_map_func(VALUE val, VALUE m, int argc, VALUE *argv)
{
VALUE result = rb_yield_values2(argc - 1, &argv[1]);
return rb_funcall(argv[0], id_yield, 1, result);
}
Откровенно говоря, я был абсолютным новичком во внутренностях Ruby, поэтому потребовалось два уикенда, чтобы написать этот достаточно тривиальный пулл реквест. Более того, сначала я попробовал пойти по другому пути: пытаясь сохранять блоки ленивых методов как процы в самом енумераторе. Первый сумасшедший пулл реквест смотреть здесь [20]. Когда вызывался Enumerator#next
, все процы "применялись" один за другим над очередным значением. Ленивые map
и select
работали замечательно, но, когда я попытался подправить Enumerator#each
, понял, что получается как-то уж слишком сложно (или нет?).
Ты крепкий орешек раз добрался сюда, так что, если планируешь что-нибудь пропатчить в руби, есть куча [21] замечательных [22] статей [23]. В качестве бонуса еще однa статья [4] о том, почему мы должны быть ленивыми.
Сейчас Enumerator::Lazy
имеет в своем арсенале select
, map
, reject
, grep
(добавленные первым патчем), flat_map
, zip
, take
, take_while
, drop
, drop_while
, cycle
(добавлены недавно shugo [24]). Девелопмент и обсуждение API активно продолжается, но если хочешь "облениться" прямо сейчас — достаточно скомпилить Ruby из trunk и наслаждаться.
Enumerable::Lazy
теперь стал Enumerator::Lazy
super()
в примере на руби должен вызываться именно так — со скобками, иначе руби автоматически передаст ему все аргументыP.S. Это перевод моей статьи [25] c английского языка.
Автор: gregolsen
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/ruby/3931
Ссылки в тексте:
[1] принят: http://bugs.ruby-lang.org/projects/ruby-trunk/repository/revisions/34951
[2] этот пост: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/19679
[3] опубликовано: http://spin.atomicobject.com/2011/03/31/enumerating-ruby-lazy-chains/
[4] множество: http://railsillustrated.com/how-to-be-lazy-in-ruby-and-why-you-should.html
[5] статей: http://www.michaelharrison.ws/weblog/?p=163
[6] Дискуссия на ruby-lang: http://bugs.ruby-lang.org/issues/708
[7] Matz проголосовал: http://bugs.ruby-lang.org/issues/708#note-7
[8] реализацию Yataka Hara: http://bugs.ruby-lang.org/issues/4890
[9] запрос патча: http://bugs.ruby-lang.org/issues/4890#note-18
[10] пул реквест: http://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fruby%2Fruby%2Fpull%2F101&sa=D&sntz=1&usg=AFQjCNF_J2ITFxxFNmh6c_OGokfGzjnmjQ
[11] смотреть roadmap: http://bugs.ruby-lang.org/projects/ruby-trunk/versions/6
[12] enumerator.c: https://github.com/ruby/ruby/blob/trunk/enumerator.c
[13] test/ruby/test_enumerator.rb: https://github.com/ruby/ruby/blob/trunk/test/ruby/test_enumerator.rb
[14] Yutaka: https://github.com/yhara/enumerable-lazy/blob/master/lib/enumerable/lazy.rb
[15] Замечательный пост на эту тему: http://yehudakatz.com/2010/02/07/the-building-blocks-of-ruby/
[16] еще один: http://yehudakatz.com/2012/01/10/javascript-needs-blocks/
[17] патч на Си: https://github.com/ruby/ruby/pull/101
[18] финальном патчe: http://bugs.ruby-lang.org/projects/ruby-trunk/repository/revisions/34951/diff/enumerator.c
[19] nobu: https://github.com/nobu
[20] Первый сумасшедший пулл реквест смотреть здесь: https://github.com/ruby/ruby/pull/100/files
[21] куча: http://www.ruby-doc.org/docs/ProgrammingRuby/html/ext_ruby.html
[22] замечательных: http://tenderlovemaking.com/2009/12/18/writing-ruby-c-extensions-part-1/
[23] статей: http://clalance.blogspot.com/2011/01/writing-ruby-extensions-in-c-part-1.html
[24] shugo: https://github.com/shugo
[25] моей статьи: http://blog.railsware.com/2012/03/13/ruby-2-0-enumerablelazy/
Нажмите здесь для печати.