Семинар 5: Ленивые вычисления

alt text

Осознание проблемы

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

Если попытаться сначала считать файлы, будет не очень хорошо. Не очень хорошо будет потому, что файлы запишутся в оперативную память и, если эти файлы очень большие, они ее попросту сожрут.

Что делать?

Анализ возможных вариантов действий

Алгоритм действий

  1. открыть файл 1;
  2. открыть файл 2;
  3. ???
  4. PROFIT

alt text

Решение - делать лениво

Концепция мы ничего не делаем до тех пор, пока нам это действительно сильно не понадобится.

В нашем случае открываем файлы и читаем по строчке. Обрабатываем по строчке. В ОП не лежит больше одной строчки из файла.

Это и есть концепция ленивых вычислений.

IRL

Пример с файлами несколько надуманный, он не очень хорошо иллюстрирует реальные задачи, которые встречаются в разработке и которые удобно решать с помощью ленивых вычислений. В реальной жизни ленивые вычисления помогают при работе с базами данных. Существуют специальные библиотеки, которые позволяют представлять таблицы в БД с помощью классов, а запросы - с помощью методов. Для реализации сложных запросов, особенно учитывая специфику языка Ruby, принято объединять методы в цепочки. Если бы ленивых вычислений не было, то каждый метод в цепочке делал бы один запрос к базе данных и чем больше таких последовательных методов будет, тем медленнее будет работать наше программа.

Пример на Ruby

Пять первых чисел бесконечной последовательности

(1..Float::INFINITY).lazy.first(5)

Есть бесконечная последовательность. То есть она не закончится никогда. Ruby гарантирует. И при этом по ней можно итерироваться! Но что же произойдет в таком случае? Программа просто зациклится.

Но что если вдруг нам нужна только какая-то часть этой последовательности? Например, первые 5, 10, 25 или n чисел? Ruby предоставляет возможность сделать это лениво:

  1. Мы говорим интерпретатору "чувак, тут бесконечная последовательность, но ты ее пока не вычисляй, просто прими к сведению".
  2. Интерпретатор отвечает "ок, я создаю специальный объект, который уже на низком старте для бесконечного цикла, но пока ничего не делает".

Мы получаем такой объект

Мы можем записать его в переменную и хранить там до тех пор, пока он нам не понадобится.

А потом мы можем с помощью этого Enumerator::Lazy взять те самые первые n чисел.

Для чего это собственно нужно? Ведь можно просто сделать цикл.

Это действительно так. На самом деле помимо того, чтобы взять первые n чисел, в Ruby можно лениво идти по последовательности до тех пор, пока выполняется нужное нам условие. То есть можно считать с заданной точностью любые выражения. И делать это довольно удобно.

Что такое Enumerator?

Это класс, который позволяет итерироваться по существующей коллекции или генерировать значения в коллекции на каждой итерации. Вот тут Enumerator используется

[1, 2, 3].each do |x|
  p x
end
    1
    2
    3

А вот так его можно получить

enum = [1, 2, 3].each
enum.class
    Enumerator
enum.next
enum.next
    1
    2
enum.next
    3

А дальше?

enum.next
    StopIteration: iteration reached an end

    <main>:in `next'

    <main>:in `<main>'

    /var/lib/gems/2.3.0/gems/iruby-0.3/lib/iruby/backend.rb:44:in `eval'

    /var/lib/gems/2.3.0/gems/iruby-0.3/lib/iruby/backend.rb:44:in `eval'

    /var/lib/gems/2.3.0/gems/iruby-0.3/lib/iruby/backend.rb:12:in `eval'

    /var/lib/gems/2.3.0/gems/iruby-0.3/lib/iruby/kernel.rb:87:in `execute_request'

    /var/lib/gems/2.3.0/gems/iruby-0.3/lib/iruby/kernel.rb:47:in `dispatch'

    /var/lib/gems/2.3.0/gems/iruby-0.3/lib/iruby/kernel.rb:37:in `run'

    /var/lib/gems/2.3.0/gems/iruby-0.3/lib/iruby/command.rb:70:in `run_kernel'

    /var/lib/gems/2.3.0/gems/iruby-0.3/lib/iruby/command.rb:34:in `run'

    /var/lib/gems/2.3.0/gems/iruby-0.3/bin/iruby:5:in `<top (required)>'

    /usr/local/bin/iruby:23:in `load'

    /usr/local/bin/iruby:23:in `<main>'

Enumerator - это отдельный класс, есть еще примесь Enumerable. Enumerator и Enumerable делают по сути одну и ту же работу.

Как создать свой Enumerator?

Конструктор класса Enumerator принимает блок кода, который должен выполняться внутри него. Это может быть как конечный, так и бесконечный цикл.

Пример конечного цикла - накопим сумму всех чисел на отрезке [1, 10].

Для этого передадим в Enumerator блок кода, в котором содержится специальная переменная, накапливающая сумму, и цикл, в котором эта сумма обновляется.

Далее мы возвращаем значение из Enumerator. Однако return в данном случае писать нельзя, так как Enumerator не может возвращать значения как функция.

ex_enum = Enumerator.new do |yielder|
  sum = 0
  
  (1..10).each do |x|
    sum += x
  end
  
  sum
end

ex_enum

Мы получили объект, который умеет итерироваться по последовательности (пока выполняется внутренний цикл). Более того, этот объект умеет накапливать промежуточные результаты.

Однако чтобы получить конечный результат, нам придется 10 раз вызвать функцию next. Можно скоратить себе работу и вызвать метод each с пустым телом. Он просто будет выполняться, пока выполняется внутренний цикл, поэтому в итоге мы получим ожидаемую сумму - 55.

ex_enum.each {}
    55

Enumerator на основе бесконечного цикла должен быть ленивым.

Попробуем накопить сумму квадратов натуральных чисел до произвольного числа с помощью ленивого Enumerator.

factorial = Enumerator.new do |yielder|
  power = 0
  
  (1..Float::INFINITY).each do |number|
    power += number**2
  end
  
  power
end

factorial.lazy.first 2

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

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

В Ruby нет способа вернуть значение из цикла, не прервав его выполнение, какой-либо стандартной языковой конструкцией. Для этого используется специальный класс - Enumerator::Yielder.

Экземпляр этого класса передается в блок кода при создании Enumerator всегда и неявно, то есть без участия программиста. Возврат значения выглядит следующим образом:

yield_ex = Enumerator.new do |yielder|
  (1..Float::INFINITY).each do |x|
    yielder.yield x
  end
end

yield_ex.lazy.first 10
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

То есть если добавить в пример, который выполнялся бесконечно, yield, все будет работать как ожидается.

factorial = Enumerator.new do |yielder|
  power = 0
  
  (1..Float::INFINITY).each do |number|
    yielder.yield power
    power += number**2
  end
end

factorial.lazy.first 5
    [0, 1, 5, 14, 30]

Заключение

Сегодня мы познакомились с концепцией ленивых вычислений и узнали, как они могут быть нам полезны. Из дополнительных материалов мы узнали о том, на что можно напороться, если попытаться передать функцию в функцию в Ruby. Эти знания могут помочь не только при выполнении лабораторных работ, но и в более глубоком освоении языка Ruby.