LCME Понедельник, 25.09.2017, 05:24
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Форум » Билеты к экзаменам » Программирование » 09 Ленивые вычисления
09 Ленивые вычисления
freidomДата: Воскресенье, 27.12.2009, 23:08 | Сообщение # 1
Главный тут
Группа: Администраторы
Сообщений: 273
Репутация: 20
Статус: Offline
Нормальный порядок редукций. Ленивые и энергичные вычисления. Ленивые вычисления в языке OCaml. Реализация ленивого списка всех простых чисел.

Нормальным порядком редукций называется такой порядок, при котором первым редуцируется самый левый редекс. Таким образом, аргументы функции вычисляются не ранее, чем они реально становятся необходимы. Существует теорема, утверждающая, что если у лямбда-выражения существует нормальная форма, то она может быть получена таким порядком. Например, аппликативным порядком невозможно вычислить нормальную форму выражения (\x.a) (w w), в то время как нормальным её можно получить в один шаг. Однако, нормальный порядок редукций не всегда эффективен. Например, выражение w (I I) вычисляется гораздо быстрее аппликативным порядком, чем нормальным, хотя они дают одинаковые результаты.
Существует способ бороться с этой проблемой, и называется он "ленивые вычисления". Суть его заключается в том, что вместо подстановки аргумента можно подставлять ссылку на него и затем уже производить все операции со ссылкой, что позволяет не вычислять одно и то же выражение дважды. К сожалению, такой алгоритм сложнее реализовать.
В большинстве языков программирования (в том числе и в OCaml) по умолчанию принят энергичный (аппликативный) порядок вычислений, при котором сначала вычисляются аргументы функции (процедуры) перед вызовом самой функции. Однако, в OCaml есть встроенный способ задействовать ленивый порядок вычислений. Чтобы отложить вычисление некоторого выражения x типа 'a, нужно написать lazy x, и это выражение будет имеь тип 'a Lazy.t. Для вычисления значения типа 'a Lazy.t есть функция Lazy.force.
Ну и наконец, пример реализации ленивого списка всех простых чисел.
Сначала опишем тип данных для представления ленивого списка:

Code
type 'a lazy_list = Nil | Cons of 'a * 'a lazy_list Lazy.t;;

Затем, нам понадобится функция, проверяющая, является ли данное число простым и не использующая ленивые вычисления:
Code
let is_prime n =
      let rec ip i =
       if i = 1 then true else if n mod i = 0 then false else ip (i - 1) in
      ip (n / 2);;

Теперь основная функция:
Code
let rec all_primes n =
      if is_prime n then
       Cons (n, lazy (all_primes (n + 1)))
      else is_prime (n + 1);;

Ну и наконец, так как первое простое число - двойка, то вызов функции будет выглядеть следующим образом:
Code
let all_primes = all_primes 2;;
 
Jack_WarGunOffДата: Понедельник, 28.12.2009, 18:59 | Сообщение # 2
Сержант
Группа: Друзья
Сообщений: 34
Репутация: 6
Статус: Offline
В is_prime надо во 2-ом if ветки местами поменять, а то у тебя простые числа -только те, которые делятся на каждое предшествущее им (то есть 2) и у первом if поменять 0 на 1, иначе получается плохо. Также, т.к. 1 - не простое число (см. конспект по делимости из лагеря), начинать надо с 2

Aquila non captat muscas - Орлы не ловят мух

Сообщение отредактировал Jack_WarGunOff - Понедельник, 28.12.2009, 18:59
 
freidomДата: Понедельник, 28.12.2009, 19:22 | Сообщение # 3
Главный тут
Группа: Администраторы
Сообщений: 273
Репутация: 20
Статус: Offline
исправлено, спасибо
 
Форум » Билеты к экзаменам » Программирование » 09 Ленивые вычисления
Страница 1 из 11
Поиск:

Copyright Freidom © 2017 Хостинг от uCoz