Программирование на языке Ruby

1. Основы языка Ruby

Ruby, названный так в честь драгоценного камня рубина, – один из самых молодых языков современного промышленного программирования. Первая версия интерпретатора была обнародована создателем языка, японским программистом Юкихиро Мацумото (Yukihiro Matsumoto) в 1995 году. Официальный сайт, посвящённый языку Ruby, размещён по адресу , а много дополнительной полезной и интересной информации можно найти в Википедии – свободной Интернет-энциклопедии ().

Ruby – это чрезвычайно мощный, динамический, чисто объектно-ориентированный язык, при разработке которого основное внимание было уделено удобству программирования на нём. Многие удачные идеи, использованные ранее в таких языках, как Perl, Python, Smalltalk, LISP и некоторых других, в Ruby удалось гармонично объединить. Благодаря этому язык легко изучать, на нём очень легко и приятно писать программы, а в уже написанные программы легко вносить необходимые изменения.

В МГИУ с 2003 года Ruby является первым из языков, которые изучают студенты-программисты. Его используют для написания простейших программ на занятиях по информатике старшеклассники подшефных школ нашего университета. Ruby применяется сотрудниками информационно-вычислительного центра университета для генерации индивидуальных заданий по математике и информатике для студентов и слушателей факультета довузовского образования. Он же позволяет с минимальными затратами сил и времени решать многие другие задачи организации эффективного учебного процесса. Наконец, именно на Ruby реализована основная часть информационной системы, позволившей автоматизировать работу университета в целом (см. [6]).

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

1.1 Установка Ruby. Если Ваша операционная система – Linux или Mac OS X, то, скорее всего, интерпретатор языка Ruby вместе со всеми необходимыми библиотеками уже установлен. Команда ruby -v в этом случае выведет информацию о версии интерпретатора, подобную следующей: ruby 1.8.4 (2005-12-24) [i686-linux].

Для Microsoft Windows существует так называемый One-Click Installer, который можно взять с сайта .

Подходящий RPM–пакет для операционной системы Linux легко найти на сайте , набрав в поле поиска слово ruby.

Так как Ruby – свободный программный продукт, то его исходные тексты доступны и могут быть получены с сайта . Установка из исходных текстов требует определённых знаний, но, как правило, сводится к выполнению лишь нескольких команд, подобных следующим: tar xvfz ruby-1.8.4.tar.gz; cd ruby-1.8.4;./cofigure; make install.

1.2 Первые программы. Программа на языке Ruby представляет собой последовательность выражений и инструкций (expressions and statements), которые размещаются обычно по одному (одной) на строке. Точка с запятой используется для отделения друг от друга инструкций на одной и той же строке, обратный слэш \ в конце строки позволяет продолжить запись выражения на следующей строчке, а комментарии начинаются с символа # и продолжаются до конца текущей строки.

Пример 1. Напишите программу, печатающую строку-приветствие.

puts "Здравствуй мир!"

Эта программа содержит единственную инструкцию – вызов метода puts, который печатает на стандартный вывод данный ему список объектов, состоящий в нашем случае из одной строки – объекта класса String. Если указанный в рамке текст разместить в файле hello.rb, то команда ruby hello.rb запустит программу и мы увидим приветствие на экране, который является стандартным выводом по умолчанию. Перенаправить вывод в файл с именем res.txt можно командой

ruby hello.rb > res.txt

Ruby является объектно-ориентированным языком, но допускает написание программ в директивном стиле. Можно считать, что наша программа содержит команду (директиву) «напечатать строку», хотя на самом деле всё устроено немного сложнее. Те сущности (называемые объектами), с которыми имеет дело программа на языке Ruby, в процессе выполнения программы взаимодействуют между собой, посылая друг другу сообщения (называемые также вызовами методов), содержащие иногда дополнительную информацию (объекты-параметры). Вызов метода m объекта obj с параметром arg записывают в виде obj.m(arg) или просто obj.m arg[1], а единственная инструкция нашей программы является сокращением от STDOUT.puts "Здравствуй, мир!". Теперь уже ясно, что сообщение «напечатать строку» посылается объекту STDOUT – стандартному выводу.

Первые программы

Пример 2. Напишите программу, печатающую сумму первых n членов начинающейся с единицы геометрической прогрессии со знаменателем q.

Рассмотрим сначала решение, основанное на использовании известной формулы для суммы геометрической прогрессии

S = (qn – 1)/(q – 1)

Запуск этой программы даёт результат 7, а заменив 3 на 64 и запустив программу ещё раз, мы получим знаменитое «шахматное» [2] число 18446744073709551615.

q=2; n=3

puts(q**n-1)/(q-1)

В Ruby (в отличие от многих других языков) легко работать с большими числами.

Программа содержит три инструкции, первые две из которых присваивают переменным q и n значения 2 и 3 соответственно. Отметим, что сами переменные объектами не являются, а лишь указывают (ссылаются) на различные объекты (в данном случае на числа – объекты класса Fixnum). Далее вычисляется выражение (q**n-1)/(q-1), которое неявно преобразуется в строку и печатается методом puts на стандартный вывод. Вот развёрнутая форма второй инструкции программы: STDOUT.puts ((q**n-1)/(q-1)).to_s, где метод to_s, применяемый к числу, возвращает представление этого числа в виде строки.

Кроме чисел и уже встречавшихся нам строк в языке Ruby существует ещё ряд базовых типов (см. стр. 42), для работы с которыми можно использовать много различных операторов (см. стр. 48), включая стандартные арифметические операторы и оператор присваивания. Имена локальных (другие нам встретятся чуть позже) переменных должны начинаться с маленькой латинской буквы и могут содержать также большие буквы, цифры и символ подчёркивания. Имена констант (например, STDOUT) должны начинаться с большой буквы. Более полная информация об использовании имён приведена на стр. 45.

Другое решение этой задачи, использующее цикл while, требует чуть больших комментариев. Переменные s и i используются в этой программе как аккумулятор для накопления суммы прогрессии и счётчик цикла соответственно. Вначале они обнуляются, а на каждой итерации цикла, выполнение которого продолжается, пока величина i остаётся меньше n, значение s увеличивается на очередной член прогрессии, а значение i – на единицу. После завершения цикла остаётся только напечатать результат. Заметим, что выражение i += а эквивалентно i = i + a.

q=2; n=3

i=s=0

while i

   s += q**i

   i += 1

end

puts s

Обратите внимание, насколько первый вариант программы проще второго. Ещё важнее, что в последнем случае используется низкоуровневый стиль программирования, который чреват ошибками и которого стараются избегать знатоки Ruby. Кроме того, вторая программа чрезвычайно неэффективна по сравнению с первой (попробуйте найти сумму миллиарда членов прогрессии со знаменателем 0.5 с помощью обеих программ).

Даже хорошее знание лучших языков программирования не заменяет знания математики.

1.3 Использование базовых типов. Часто программы получают данные из файлов, запрашивают их с клавиатуры или берут непосредственно из командной строки. Проиллюстрируем последнюю из этих возможностей на примере решения следующей несложной задачи.

Пример 3. Напишите программу, печатающую сумму цифр десятичного представления натурального числа, задаваемого в командной строке.

После запуска программы test.rb командой ruby test.rb 123 Маша в массиве ARGV окажутся все аргументы командной строки, указанные при её запуске, то есть строки 123 и Маша. Выражение ARGV[0] даёт первый элемент массива (строку 123). Для решения задачи этого достаточно, а более подробно с массивами (Arrays) можно познакомиться, заглянув на стр. 43. Таблица A.10 на стр. 47 содержит перечень наиболее часто используемых предопределённых объектов Ruby–программы (ARGV – один из них).

Так как последняя цифра числа n равна остатку от деления на 10 (n%10), а целочисленное деление на 10 (n/10) равносильно удалению последней цифры, то построить цикл while, вычисляющий требуемую сумму, не слишком сложно. Обратите внимание на метод to_i, преобразующий строку в целое число. Его необходимо делать явно в отличие от вызываемого автоматически при работе puts метода to_s, выполняющего обратное преобразование числа в строку. Запустить эту программу, содержащуюся в файле sum1.rb, можно так: ruby suml.rb 12345.

n=ARGV[0].to_i

s = 0

while n > 0

   s += n%10

   n /= 10

end

puts s

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

Новая версия программы содержит последовательный вызов всего трёх методов и состоит из одной строки.

Метод scan[3] с параметром /./ преобразует строковое представление числа АRGV[0]в массив цифр, который обрабатывается методом inject – одним из так называемых итераторов, последовательно выполняющим действия, указанные в блоке (код в фигурных скобках), над каждым из элементов массива. При этом переменная s сначала инициализируется нулём, а на каждой итерации увеличивается на величину x.to_i, равную числовому значению очередной цифры х. Полученный результат затем печатается методом puts.

Отметим, что inject является методом модуля Enumerable, который включается (mix in) в различные классы, расширяя их возможности. Кроме массивов таким классом являются диапазоны (Ranges), чаще всего используемые в качестве последовательностей элементов: натуральные числа от 3 до 9 (3...9 или 3…10), латинские буквы от D до H (’D’..’H’) и т.п. При решении следующей задачи использование итератора each для диапазона чисел является вполне естественной идей.

Пример 4. Является ли простым число 15485863?

Напомним, что натуральное число является простым, если оно имеет ровно два различных делителя. Интерес к простым числам связан прежде всего с их использованием в криптографии. Подробнее об этом можно узнать на сайте http://en.wikipedia.org/wiki/Prime_numbers.

n=15_485_863

 (2...n).each do|i|

  if n % i == 0

    puts false; exit

  end

end

puts true

Наивный алгоритм проверки простоты числа n очевиден: будем последовательно находить остатки от деления n на числа 2, 3, 4 и так далее, вплоть до n-1. Если хотя бы один из остатков окажется нулевым, то число простым не является. Итератор each для каждого элемента диапазона выполняет блок (начинающийся do и заканчивающийся end[4]), проверяющий это условие и прекращающий выполнение программы (метод exit) в случае его выполнения. В Ruby операторы if, while и некоторые другие являются просто модификаторами выражений, что не так во многих других языках (обязательно ознакомьтесь с примерами на стр. 49).

Программа станет намного изящнее и понятнее, если воспользоваться методом any? (в Ruby имя метода может оканчиваться вопросительным знаком [5]) модуля Enumerable. Этот метод проверяет для элементов i диапазона (2...n) заданное в блоке условие n%i==0 и возвращает «истину» (true), как только встретит элемент, ему удовлетворяющий. Если же таких элементов не найдётся, то метод возвратит «ложь» (false). Отрицание (!) полученного результата является ответом на вопрос о простоте числа n.

n=15_485_863;put s !(2...n).any?{|i|n%i==0}

Аналогичный методу any? метод all? модуля Enumerable позволяет проверить истинность заданного в блоке условия для всех элементов коллекции. Этот модуль определяет ещё целый ряд методов, полный перечень можно получить с помощью команды ri Enumerable.

Пример 5. Найдите минимальное четырёхзначное число, уменьшающееся на 27 после перестановки его последней цифры на первую позицию.

puts(1000...10000).find{|x|x/10+1000*(x%10) == x-27}

Последняя цифра числа x – это x%10, а число, получающееся после её перестановки на первую позицию, равно значению выражения x/10+1000*(x%10). Таким образом, нам нужно найти (find) первое число из диапазона 1000…10000, для которого выполняется условие x/10+1000*(x%10) == x-27. Это делает метод find (или detect).

Заметим, что методы find_all и select, будучи применёнными к коллекции, возвращают массив всех тех её элементов, которые удовлетворяют заданному в блоке условию, а метод reject возвращает элементы, для которых условие оказывается ложным.

Пример 6. Напечатайте квадраты всех натуральных чисел, не больших тысячи, десятичная запись которых заканчивается на 396.

p(1..1000).map{|t|t*t}.select{|x|x%1000==396}

Для решения задачи достаточно применить метод map (или collect), возвращающий массив, содержащий результаты применения заданного блока к элементам коллекции, а затем выбрать из него нужные числа. Метод p печатает массив (как и иные объекты) в более удобном виде, чем puts.

Пример 7. Выясните, является ли заданная в командной строке последовательность символов палиндромом. Напомним, что палиндром – это последовательность, которая не изменяется после её инвертирования (переворачивания). Ограничимся в этой задаче только малыми русскими буквами и пробелами, которые должны игнорироваться. Вот примеры палиндромов: «поп», «шалаш», «аргентина манит негра», «а роза упала на лапу азора». Если программа, решающая эту задачу, содержится в файле palindrome.rb, то команда ruby palindrome.rb аргентина манит негра должна напечатать true.

defprime?(n)

   not(2...n).any?{|i|n%i==0}

end

(15_485_800..15_485_863).eachdo|x|

   puts x if prime?(x)

end

Как мы уже знаем, объект ARGV содержит массив аргументов командной строки. Метод join класса Array «склеивает» в одну строку все его элементы, а метод reverse класса String инвертирует строку.

p ARGV.join==ARGV.join.reverse

Время, потраченное на знакомство с библиотеками Ruby, многократно окупится в дальнейшем.

Пока мы использовали только методы, определённые для классов и модулей стандартной библиотеки, но часто при написании программ полезно создавать свои методы. Например, при решении задачи о простоте числа естественно определить метод prime? с одним параметром (числом), возвращающий true или false. Затем его можно использовать для того, чтобы найти и напечатать все простые числа из диапазона 15_485_800..15_485_863. Подробнее про определение методов рассказано далее.

Пример 8. Реализованный выше метод prime? работает достаточно медленно. Говорят, что его сложность линейна[6], ибо для простых чисел выполняется почти n итераций. Реализуйте метод prime?, работающий быстрее.

Заметим, что если n = pq, то одно из чисел p и q заведомо не превосходит √n. До этой величины и достаточно выполнять проверку[7]. Для вычисления квадратного корня используем метод sqrt модуля Math.

def prime?(n) not (2.. Math.sqrt(n)).any?{|i| n%i == 0} end (15_485_800.. 15_485_863).each{ |x| puts x if prime?(x) }

Без знания математики хорошей программы не напишешь.

Пример 9. Многочлен можно задать массивом его коэффициентов. Например, многочлену x³+2x – 3 соответствует массив [1,0,2, – 3], а массив [1,2] задаёт многочлен x + 2. Реализуйте метод, позволяющий перемножать два многочлена, заданные их коэффициентами.

На самом деле для написания программы эта формула совершенно не нужна. Достаточно заметить, что степень итогового многочлена на единицу меньше суммы степеней исходных, перемножать необходимо каждый из коэффициентов первого многочлена a_i на каждый из коэффициентов второго b j, а получающееся произведение aibj следует добавлять к коэффициенту итогового многочлена при степени i + j. Реализовать данную идею проще всего с помощью метода each_with_index модуля Enumerable, который последовательно выполняет заданный блок для всех элементов коллекции, передавая в него сам элемент и его индекс. Метод size класса Array используется для определения количества элементов в нём, а метод new с двумя параметрами этого же класса создаёт новый массив указанного размера, заполненный нулями. Массивы в Ruby применяют очень часто, так как их можно использовать в качестве стеков, очередей, деков, списков и других структур данных.

def mul(p,q)

   r=Array.new(p.size+q.size-1,0)

   p.each_with_indexdo|u,i|

    q.each_with_indexdo|v,j|

       r[i+j] += u*v

    end

   end

   r

   end

p mul([1,0,2,-3],[1,2])

Пример 10. Реализованный в примере 8 метод prime? является слишком медленным для получения списка всех простых чисел от 2 до миллиона.

Напишите программу, решающую эту задачу за «разумное время».

n=Integer(ARGV[0])

sieve=[]

for i in 2..n

   sieve[i] = i

end

for i in2..Math.sqrt(n)

   next unlesssieve[i]

   (i*i).step(n,i){|j|sieve[j]=nil}

end

psieve.compact

Более двух тысяч лет назад греческий математик Эратосфен придумал алгоритм, называемый сейчас «решетом Эратосфена» [8]. В простейшем варианте он выглядит так. Выпишем сначала все числа от 2 до n. Затем отметим первое простое число 2 и вычеркнем все числа, кратные ему. Далее отметим первое из ещё не отмеченных и не вычеркнутых чисел (это будет число 3), и вычеркнем все числа, кратные ему (включая и те, которые уже вычеркнуты). Будем продолжать данный процесс, пока это возможно. В итоге останутся только простые числа. Слегка модифицированный алгоритм приводит к программе, которая через несколько секунд после её запуска командой ruby sieve.rb 1000000 печатает список всех простых чисел, меньших миллиона. Первая инструкция программы содержит вызов метода Integer модуля Kernel, который делает почти то же самое[9], что используемый нами ранее метод to_i класса String, – преобразует строку в число. В созданный далее пустой массив sieve заносятся числа от 2 до n с помощью цикла for. Массив при этом растёт: после первого присваивания он содержит три элемента ([nil,nil,2]), после второго – уже четыре и т.д. Цикл for является лишь удобным сокращением для известного нам итератора each: запись for i in 2.. m неявно преобразуется в (2.. m).each do |i|.

В следующем цикле число не обрабатывается, если оно равно nil, то есть уже вычеркнуто (см. таблицу A.12 на стр. 49). Вычёркивание всех ему кратных осуществляет итератор min.step(limit,step){|i| block} класса Numeric, который выполняет block, начиная со значения i=min, увеличивая его после каждой итерации на step до тех пор, пока оно не станет больше, чем limit. Воспользуйтесь командой ri compact для выяснения того, что делает метод compact.

Учитесь находить нужную Вам информацию в книгах, справочных системах и сети Интернет.

Пример 11. Числами Фибоначчи называют последовательность, задаваемую следующими формулами: f₀ = 0, f₁ = 1, f_n = f_n-1 + f_n-2 для n > 1. Напишите рекурсивный метод вычисления величины f_n.

Числа Фибоначчи встречаются и в науке, и в природе чрезвычайно часто[10], а последовательность этих чисел занимает весьма почётное место в Интернет-энциклопедии целочисленных последовательностей[11], которая является очень интересной сама по себе.

def fib(n)

   n < 2?n:fib(n-2)+fib(n-1)

end

p fib(40)

Рекурсивным называют метод, который вызывает сам себя, и написать его в данном случае очень легко, ибо он дословно повторяет определение последовательности чисел Фибоначчи. Отметим только, что тернарный оператор a ? b : с эквивалентен условному оператору if a then b; else с end (см. таблицу A.12).

Пример 12. С помощью написанного рекурсивного метода практически невозможно находить числа Фибоначчи f_n для больших значений n, так как даже на вычисление сорокового числа на компьютере с тактовой частотой процессора 2.4 Ghz требуется почти 6 минут. Реализуйте метод, позволяющий найти миллионное число Фибоначчи за «разумное время».

def fib(n)

   return n if n < 2

   a,b = 0,1

for i in 2..n

       a,b = b,a+b

   end

   b

end

pfib(1_000_000)

Требуемое решение можно получить, рассматривая преобразование F, определённое на парах чисел формулой F (a, b) = = (b, a + b). Если начать с пары чисел (0,1), то многократное применение F порождает последовательность чисел Фибоначчи. Такая программа (обратите внимание на множественное (параллельное) присваивание, см. стр. 49) имеет линейную сложность, ибо количество необходимых для нахождения f_n итераций цикла не превосходит n. Миллионное число Фибоначчи на компьютере с заданными в постановке задачи характеристиками эта программа находит примерно за две минуты, а ведь в его десятичной записи содержится 86784 цифры!

Интересно, что если вместо пар чисел рассматривать четвёрки, записанные в виде таблицы 2 х х 2 – квадратной матрицы, то можно получить ещё более быструю программу. Заметим, что матрица возведённая в квадрат, равна , в куб – , в четвертую степень – .

require 'matrix'

deffib(n)

   return n if n < 2

   (Matrix[[1,1],[1,0]]**n)[0,1]

end

p fib(1_000_000)

Первая строка этих матриц содержит числа Фибоначчи, а так как возведение в степень (в том числе и матриц) выполняется быстро, то вычисление чисел Фибоначчи таким способом оказывается весьма эффективным.

Для работы с матрицами, которые не входят в число базовых типов языка Ruby, необходимо с помощью директивы require подключить библиотеку, в которой определен класс Matrix и методы для манипулирования с объектами этого класса. Миллионное число Фибоначчи последняя программа находит почти в два с половиной раза быстрее, чем предыдущая, и разница в скорости их работы увеличивается с ростом номера n числа f_n.

1.4 Упражнения

Задача 1. Оператор ** в Ruby реализован весьма эффективно по сравнению с наивным способом умножения основания на себя нужное число раз. Напишите программу с применением цикла while, которая будет возводить число a в натуральную степень n за время, сопоставимое со временем работы оператора a**n даже для больших значений показателя.

Задача 2. Измените написанную при рассмотрении примера 7 программу так, чтобы она работала и в ситуации, когда исследуемая строка заключается в апострофы или кавычки. Например, команда ruby palindrome.rb ’аргентина манит негра’ должна печатать true.

Задача 3. Какие изменения следует внести в программу умножения многочленов (пример 9), если коэффициенты многочленов задавать в обратном порядке – от младших степеней к старшим?

Задача 4. Напишите программу, находящую для всех чисел от 1 до задаваемого в командной строке натурального n, массив списков (массивов) всех делителей этих чисел. Для n = 6, например, программа должна напечатать следующую строку: [[1], [1, 2], [1, 3], [1, 2, 4], [1, 5], [1, 2, 3, 6]].

Задача 5. Назовём билет с натуральным номером, десятичная запись которого состоит из чётного количества (2n) цифр, счастливым, если сумма первых его n цифр равна сумме n последних. Напишите программу, вычисляющую количество счастливых билетов для заданного натурального n.

Задача 6*. Напишите программу, способную вычислить количество счастливых билетов (см. задачу 5) для n = 1000 за «разумное время» (например, около 30 секунд на компьютере с тактовой частотой процессора 2.4 Ghz).

Задача 7*. Напишите такую программу, решающую задачу 4, чтобы время её работы для п = 10⁶ удовлетворяло требованиям, сформулированным в задаче 6 (это ограничение касается собственно нахождения массива; вывод такого огромного количества данных требует заметного дополнительного времени).

Задача 8*. Программа умножения многочленов, приведённая на стр. 12, имеет квадратичную сложность (количество операций при перемножении двух многочленов степени п пропорционально n²). Так называемое быстрое преобразование Фурье (см. книгу [5]) позволяет сделать это быстрее. Реализуйте алгоритм быстрого умножения многочленов таким образом.