Недавно chiaroscuro написал провокационную статью с жёлтым заголовком «Почему циклы должны умереть». Её обсуждение заняло около 180 комментариев, но сама статья ушла в минус и не попала на главную, не смотря на то, что она содержала здравую мысль об использовании рекурсии вместо циклов.
В этой статье я дополню его пост и приведу примеры реализации на одном из лучших языков под .NET — Nemerle, а так же сделаю холиварное заявление о преимуществе .NET перед Java.
Во-первых, мне хочется отметить один плюс использования рекурсии вместо циклов, которое упустил chiaroscuro — декомпозицию. Рассматривая программу на популярном императивном языке (Java, C#, Pascal, C) мы имеем дело с потоком команд. Средством декомпозиции этого потока, скажем для повторного использования кода или тестирования, является разбиение на процедуры, которые раньше назывались подпрограммами. В названии «подпрограмма» заключена их суть — мы берем основной поток команд, вырезаем кусок, заворачиваем его в некий workaround и процедура готова, но она является тем же самым потоком, только поменьше. Мы пришли к тому, что в языке одни средства служат вычислению — императивные инструкции — те, из которых состоит поток вычислений, другие же обслуживают этот поток — процедуры. В случае ФЯ, рекурсия выполняет те же задачи, что и циклы в императивных языках, а так же служит средством декомпозиции, то есть программа, написанная на ФЯ сама разваливается на отдельные логические части. Сразу стоит заметить, что возникает проблема замусоривания глобального пространства имен; но во многих ФЯ она элегантно решается — функция внутри своего тела может объявить функцию, которая видна только ей.
Следующее на что стоит обратить внимание в статье — комментарии, во многих из них хабралюди твердили как один «рекурсия это красивое эллегантное но жрущее ресурсы зло». В общем случае это так, но существует класс рекурсивных алгоритмов, которые по потреблению ресурсов сравнимы с разворотом этой рекурсии в цикл — такая рекурсия называется хвостовой рекурсией. Распознать её очень просто: если функция получила значение функции, ничего с ним не сделала и вернула его как свое значение, то мы имеем дело с хвостовой рекурсией, в случае рекурсии конечно же. Легко понять почему так происходит — если с значением не происходит действий, то можно освободить стек от локальных переменных до того, как вызвать вторую функцию, кроме того в качестве адреса возврата можно подставить не себя, а свой адрес возврата.
Это были дополнения к той статье, а теперь основное замечание: полностью отказываться от циклов глупо и, в настоящее время, имеет смысл только, если это академическое программирование целью которого исследовать оптимизацию компиляторов; когда программирование хлеб насущный, то нужно использовать те средства, которые наиболее адекватны задаче в текущий момент. Впрок учить haskell до того момента, пока его не научать автоматически параллелить на множество процессоров, я не буду. Я выберу язык, который предоставляет мне выбор инструмента, с помощью которого я могу быстро решить свою задачу. То есть язык должен быть гибридным и поддерживать как функциональную, так и объектно-ориентированную парадигму. Таким языком является Nemerle.
Внимательный читатель может спросить причем здесь Java. Дело в том, что виртуальная машина Java, в отличии от .NET не поддерживает оптимизацию хвостовой рекурсии. В прочим, для многих может оказаться новостью, что она есть в .NET, так как самый популярный язык программирования для него — C# — её не поддерживает. После того, как я узнал, что оптимизация хвостовой рекурсии поддерживается в .NET у меня появилась идея протестировать её, что и стало причиной этого поста.
Подопытным кроликом станет алгоритм нахождения последних 5 цифр n-ого числа Фибоначчи, а тестироваться он будет на языках Nemerle, C# и Perfect C#, назовем так язык, который полностью совместим с C#, но обладает свойством оптимизации хвостовой рекурсии. Что бы получить сборку скомпилированную Perfect C#'ом я скомпилировал код на C#, декомпилировал его с помощью ildasm'а добавил il инструкцию tail перед вызовом функции и скомпилировал il код ilasm'ом. Ниже представлены коды программ на этих языках:
А теперь само интересное — результаты тестирования. Для разминки я решил посчитать последние 5 цифр 40000ого числа Фибоначчи: Nemerle справился за 0.58 миллисекунды, PerfectC# за 2.389 миллисекунды, а С# за 0.782 миллисекунды. После этого я решил испытать алгоритм на 100000ым числе Фибоначчи и получил следующие результаты: Nemerle — 1.421 миллисекунды, PerfectC# — 3.244 миллисекунды, С# пал с StackOverflowException.
Результаты таковы, что Nemerle занимает первое место, а второе делят PerfectC# и C#, так как второй валится на глубокой рекурсии, но нам где не валиться обгоняет PerfectC#.
UPD
Эталонная реализация последних 5 цифр 40000 чисела Фибаначчи — 0.565 миллисекунды и 100000 числа Фибаначчи — 1.407 миллисекунды.
В этой статье я дополню его пост и приведу примеры реализации на одном из лучших языков под .NET — Nemerle, а так же сделаю холиварное заявление о преимуществе .NET перед Java.
Во-первых, мне хочется отметить один плюс использования рекурсии вместо циклов, которое упустил chiaroscuro — декомпозицию. Рассматривая программу на популярном императивном языке (Java, C#, Pascal, C) мы имеем дело с потоком команд. Средством декомпозиции этого потока, скажем для повторного использования кода или тестирования, является разбиение на процедуры, которые раньше назывались подпрограммами. В названии «подпрограмма» заключена их суть — мы берем основной поток команд, вырезаем кусок, заворачиваем его в некий workaround и процедура готова, но она является тем же самым потоком, только поменьше. Мы пришли к тому, что в языке одни средства служат вычислению — императивные инструкции — те, из которых состоит поток вычислений, другие же обслуживают этот поток — процедуры. В случае ФЯ, рекурсия выполняет те же задачи, что и циклы в императивных языках, а так же служит средством декомпозиции, то есть программа, написанная на ФЯ сама разваливается на отдельные логические части. Сразу стоит заметить, что возникает проблема замусоривания глобального пространства имен; но во многих ФЯ она элегантно решается — функция внутри своего тела может объявить функцию, которая видна только ей.
Следующее на что стоит обратить внимание в статье — комментарии, во многих из них хабралюди твердили как один «рекурсия это красивое эллегантное но жрущее ресурсы зло». В общем случае это так, но существует класс рекурсивных алгоритмов, которые по потреблению ресурсов сравнимы с разворотом этой рекурсии в цикл — такая рекурсия называется хвостовой рекурсией. Распознать её очень просто: если функция получила значение функции, ничего с ним не сделала и вернула его как свое значение, то мы имеем дело с хвостовой рекурсией, в случае рекурсии конечно же. Легко понять почему так происходит — если с значением не происходит действий, то можно освободить стек от локальных переменных до того, как вызвать вторую функцию, кроме того в качестве адреса возврата можно подставить не себя, а свой адрес возврата.
Это были дополнения к той статье, а теперь основное замечание: полностью отказываться от циклов глупо и, в настоящее время, имеет смысл только, если это академическое программирование целью которого исследовать оптимизацию компиляторов; когда программирование хлеб насущный, то нужно использовать те средства, которые наиболее адекватны задаче в текущий момент. Впрок учить haskell до того момента, пока его не научать автоматически параллелить на множество процессоров, я не буду. Я выберу язык, который предоставляет мне выбор инструмента, с помощью которого я могу быстро решить свою задачу. То есть язык должен быть гибридным и поддерживать как функциональную, так и объектно-ориентированную парадигму. Таким языком является Nemerle.
Внимательный читатель может спросить причем здесь Java. Дело в том, что виртуальная машина Java, в отличии от .NET не поддерживает оптимизацию хвостовой рекурсии. В прочим, для многих может оказаться новостью, что она есть в .NET, так как самый популярный язык программирования для него — C# — её не поддерживает. После того, как я узнал, что оптимизация хвостовой рекурсии поддерживается в .NET у меня появилась идея протестировать её, что и стало причиной этого поста.
Подопытным кроликом станет алгоритм нахождения последних 5 цифр n-ого числа Фибоначчи, а тестироваться он будет на языках Nemerle, C# и Perfect C#, назовем так язык, который полностью совместим с C#, но обладает свойством оптимизации хвостовой рекурсии. Что бы получить сборку скомпилированную Perfect C#'ом я скомпилировал код на C#, декомпилировал его с помощью ildasm'а добавил il инструкцию tail перед вызовом функции и скомпилировал il код ilasm'ом. Ниже представлены коды программ на этих языках:
Код на Nemerle Код на PerfectC#
public module Fibonacci .class public auto ansi beforefieldinit
{ Fibonacci extends [mscorlib]System.Object
public Last5(number : int) : int {
{ .method private hidebysig static int32
def F2(counter,a,b) F2(int32 counter, int32 a, int32 b)
{ cil managed
if (counter==0) {
a .maxstack 8
else ldarg.0
F2(counter-1,b,(a+b)%100000) brtrue.s IL_0005
} ldarg.1
when(number<0) throw Exception(); ret
F2(number,1,1) ldarg.0
} ldc.i4.1
} sub
ldarg.2
ldarg.1
Код на C# ldarg.2
add
ldc.i4 0x186a0
public class Fibonacci rem
{ tail.
static private int F2(int counter, int a, int b) call int32 Fibonacci::F2(int32,int32,int32)
{ ret
if (counter == 0) return a; }
return
F2(counter - 1, b, (a + b)%100000); .method public hidebysig static int32
} Last5(int32 number) cil managed
{
static public int Last5(int number) .maxstack 8
{ ldarg.0
if (number < 0) throw new Exception(); ldc.i4.0
return F2(number, 1, 1); bge.s IL_000a
} newobj instance
} void [mscorlib]System.Exception::.ctor()
throw
ldarg.0
ldc.i4.1
ldc.i4.1
call int32 Fibonacci::F2(int32,int32,int32)
ret
}
.method public hidebysig specialname
rtspecialname instance void .ctor()
cil managed
{
.maxstack 8
ldarg.0
call instance
void [mscorlib]System.Object::.ctor()
ret
}
А теперь само интересное — результаты тестирования. Для разминки я решил посчитать последние 5 цифр 40000ого числа Фибоначчи: Nemerle справился за 0.58 миллисекунды, PerfectC# за 2.389 миллисекунды, а С# за 0.782 миллисекунды. После этого я решил испытать алгоритм на 100000ым числе Фибоначчи и получил следующие результаты: Nemerle — 1.421 миллисекунды, PerfectC# — 3.244 миллисекунды, С# пал с StackOverflowException.
Результаты таковы, что Nemerle занимает первое место, а второе делят PerfectC# и C#, так как второй валится на глубокой рекурсии, но нам где не валиться обгоняет PerfectC#.
UPD
Эталонная реализация последних 5 цифр 40000 чисела Фибаначчи — 0.565 миллисекунды и 100000 числа Фибаначчи — 1.407 миллисекунды.
