Ленивые вычисления
May. 23rd, 2010 12:33 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonЧитаю статью про F# в очередном номере ПФП, а там стандартный набор бреда про сабж:
В противоположность жадному подходу существует стратегия ленивых вычислений, которая позволяет вычислять значение выражения только тогда, когда оно становится необходимо. Преимуществами такого подхода являются:
• производительность, поскольку неиспользуемые значения просто не вычисляются;
• возможность работать с бесконечными или очень большими последовательностями, так как они никогда не загружаются в память полностью;
• декларативность кода. Использование ленивых вычислений избавляет программиста от необходимости следить за порядком вычислений, что делает код проще.
По пунктам:
1.
а) Что-то я не припомню, чтобы программисты на неленивых языках стали бы вычислять какие-то значения, которые потом не используют. Обычно все-таки люди достаточно разумны, чтобы их программы вычисляли ровно столько, сколько нужно.
б) Ленивость создает накладные расходы, причем существенные. Если две программы делают одно и то же, ленивый вариант никак не будет производительнее энергичного. Почему-то большинство проблем с производительностью программ на Хаскеле решают именно расстановкой всяких ! и $!, убирающих ленивость. И оптимизатор тем же занимается.
2.
С бесконечными структурами ни ленивые, ни энергичные программы работать не могут, они всегда работают с конечной их частью. Насчет больших последовательностей - в неленивых языках они доступны в виде итераторов, энуменаторов и т.п., но это несколько другая вещь, т.к. значения обрабатываются по очереди и не хранятся в памяти, в отличие от ленивых списков и структур. Если же что-то в памяти хранить, то из-за накладных расходов на ленивость ленивые языки принципиально могут хранить меньше данных в тех же объемах памяти, чем неленивые.
3.
От необходимости следить за порядком вычислений избавляет исключительно чистота, а не ленивость. Если код не весь чист (содержит побочные эффекты), то ровно наоборот - ленивость заставляет думать о порядке вычислений гораздо больше обычного, т.к. программа ведет себя не так, как обычно подсказывает интуиция. В строгих же языках порядок вычислений настолько прост и понятен, что задумываться не заставляет.
В противоположность жадному подходу существует стратегия ленивых вычислений, которая позволяет вычислять значение выражения только тогда, когда оно становится необходимо. Преимуществами такого подхода являются:
• производительность, поскольку неиспользуемые значения просто не вычисляются;
• возможность работать с бесконечными или очень большими последовательностями, так как они никогда не загружаются в память полностью;
• декларативность кода. Использование ленивых вычислений избавляет программиста от необходимости следить за порядком вычислений, что делает код проще.
По пунктам:
1.
а) Что-то я не припомню, чтобы программисты на неленивых языках стали бы вычислять какие-то значения, которые потом не используют. Обычно все-таки люди достаточно разумны, чтобы их программы вычисляли ровно столько, сколько нужно.
б) Ленивость создает накладные расходы, причем существенные. Если две программы делают одно и то же, ленивый вариант никак не будет производительнее энергичного. Почему-то большинство проблем с производительностью программ на Хаскеле решают именно расстановкой всяких ! и $!, убирающих ленивость. И оптимизатор тем же занимается.
2.
С бесконечными структурами ни ленивые, ни энергичные программы работать не могут, они всегда работают с конечной их частью. Насчет больших последовательностей - в неленивых языках они доступны в виде итераторов, энуменаторов и т.п., но это несколько другая вещь, т.к. значения обрабатываются по очереди и не хранятся в памяти, в отличие от ленивых списков и структур. Если же что-то в памяти хранить, то из-за накладных расходов на ленивость ленивые языки принципиально могут хранить меньше данных в тех же объемах памяти, чем неленивые.
3.
От необходимости следить за порядком вычислений избавляет исключительно чистота, а не ленивость. Если код не весь чист (содержит побочные эффекты), то ровно наоборот - ленивость заставляет думать о порядке вычислений гораздо больше обычного, т.к. программа ведет себя не так, как обычно подсказывает интуиция. В строгих же языках порядок вычислений настолько прост и понятен, что задумываться не заставляет.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2010-05-31 05:49 am (UTC)Насколько я помню про STG, по мере потребления списка каждый его элемент будет появляться сперва в виде thunk'a, потом в санке вызов вычисления будет заменяться возвратом значения, но сам вычисленный thunk никуда не исчезнет, пока его сборщик мусора не уберет. А если у нас кто-то еще ссылается на начало списка (xs), то весь список и будет в памяти.
no subject
Date: 2010-05-31 08:48 am (UTC)Ленивый список не присутствует в памяти полностью именно потому, что его ненужный префикс убирает сборщик мусора. Вы намекаете, что в статье этого не написали?
no subject
Date: 2010-05-31 08:56 am (UTC)в отличие от ленивого языка, где надо специально следить, как бы что-нибудь где-нибудь не зацепилось случайно.
no subject
Date: 2010-05-31 09:30 am (UTC)no subject
Date: 2010-05-31 09:15 am (UTC)Интересно, что мешает сборщику мусора здесь:
http://thedeemon.livejournal.com/16444.html?thread=173628#t173628
(в режиме без -О2)