LINUX.ORG.RU

[FP] Не дающий покоя, навязчивый, сводящий с ума вопрос


0

0

Пусть надо вычислить сумму положительных значений sin(t), t = 0..99

Например так:

reduce(float.__add__, filter(lambda x: x > 0, map(sin, range(100))))

В результате создается 3 списка и вычисления происходят в 3 циклах (рекурсиях?).

Императивным подходом получаем 1 список + 1 цикл

Скажите, это как-нибудь оптимизируется хоть в каком-нибудь ФЯ? 3 списка заменяются одним? 3 рекурсии заменяются одним циклом? Или все остается так, как выглядит =( ? Этож какое неоправданное использование ресурсов!

★★★★★

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> Скажите, это как-нибудь оптимизируется хоть в каком-нибудь ФЯ?

Насчет ФЯ не знаю, но в Python 2.x это не оптимизируется, и будет тебе 3 списка (хотя рекурсии что-то я не вижу). В Python 3.0, AFAIK, map и filter возвращают итераторы, и получается как в императивном случае.

За настоящие ФЯ пусть ответят настоящие спецы :)

> Этож какое неоправданное использование ресурсов!

Память нынче дешева :D

tailgunner ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Python - не функциональный язык. И потом, зачем тут списки?

Делаешь функцию - генератор аккумуляторов(практически sicp-пример):

(defun filter-accumulate (acc p end-p nil-val term next) (labels ((accumulator (init end) (if (funcall end-p init end) nil-val (funcall acc (let ((val (funcall term init))) (if (funcall p val) val nil-val)) (accumulator (funcall next init) end))))) #'accumulator))

И вот твой, собственно, случай: (funcall (filter-accumulate #'+ #'plusp #'> 0 #'sin #'1+) 0 99)

(можно еще и в хвостовую рекурсию развернуть или сразу в loop, тогда и по производительности совсем замечательно все будет)

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Ох, е.
Вот код:
(defun filter-accumulate (acc p nil-val term next)
(labels ((accumulator
(init end)
(if (> init end) nil-val
(funcall acc
(let ((val (funcall term init)))
(if (funcall p val) val nil-val))
(accumulator (funcall next init) end)))))
#'accumulator))

(funcall (filter-accumulate #'+ #'plusp #'> 0 #'sin #'1+) 0 99)

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

(defun filter-accumulate (acc p end-p nil-val term next)
 (labels ((accumulator 
	    (init end) 
	    (if (funcall end-p init end) nil-val
	      (funcall acc
		       (let ((val (funcall term init)))
			 (if (funcall p val) val nil-val))
		       (accumulator (funcall next init) end)))))
   #'accumulator))


(funcall (filter-accumulate #'+ #'plusp #'> 0 #'sin #'1+) 0 99) 

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Функциональный язык С# всё в один цикл раскатает (см. yield).

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Ух спасибо, добрый анон. Теперь буду спать спокойно, зная, что существуют генераторы аккамуляторов (пока не узнаю что это такое)

makoven ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Что бы не создавать списков, можно так:

from itertools import imap, ifilter
reduce(float.__add__, ifilter(lambda x: x > 0, imap(sin, range(100))))

Но мне кажется, что так тоже будет несколько медленнее, чем простой цикл.

nozh ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

какой только херни не понапридумывают, лишь бы нормальные фвп не использовать
В питоне что, запретили фпв создавать?

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

В ghc (Glasgow Haskell Compiler) все будет заменено одним списком (по крайней мере, должно; если не заменяется, можно дописать свои правила преобразования). см. http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html

В разных компиляторах Common Lisp тоже вполне возможно (не смотрел точно). В Common Lisp — за счет compiler-macro.

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

dmitry_vk ★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> какой только херни не понапридумывают, лишь бы нормальные фвп не использовать

Ага, понапридумывали всякие циклы. :)

> В питоне что, запретили фпв создавать?


Нет, не запрещали.

nozh ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Этот питоновский вариант не будет создавать никаких массивов. В ленивых языках тоже не будет создано никаких массивов, всё будет делаться на лету, т.е. тоже сплошной цикл.

Joe_Bishop ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Haskell:

sum $ filter (>=0) $ map sin [0..99]

Цикл будет один - ибо произойдет list fusion.

imp ★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Похоже я упускаю что-то очевидное: почему нельзя заменить range на xrange? И вот уже одним списком меньше. Ну и про itertools уже сказали.

Davidov ★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

>>почему нельзя заменить range на xrange? И вот уже одним списком меньше. Ну и про itertools уже сказали.

Да, видимо это и есть наиболее рациональный подход (по крайней мере для больших списков).

В питоне понятно, что происходит - генератор xrange последовательно обмазывается функциями, в результате получаем итератор итератора, который, затем редуцируется в сумму.

А в ФЯ как технически происходит оптимизация?

makoven ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> reduce(float.__add__, filter(lambda x: x > 0, map(sin, range(100))))

> Этож какое неоправданное использование ресурсов!


ну itertools же:

from itertools import ifilter, imap

reduce(float.__add__, ifilter(lambda x: x > 0, imap(sin, xrange(100))))


также, в питон3 все это говнище будет генераторами по умолчанию

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

А можно вопрос (возможно глупый)? Вот хоть убейте не понимаю: зачем подобные вещи писать в чисто функциональном стиле, хотя если переписать обычным тупым циклом, то получится:

1) короче
2) проще для понимания
3) точно известно время работы

? Ну кроме красноглазия ессно...

Deleted ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Ну, reduce как раз по этой причине собирались убрать из питона (по крайней мере из builtins).

А что касается map, filter и lambda, они обычно сильно упрощают понимание и код короче делают.

Davidov ★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> если переписать обычным тупым циклом, то получится:

> 1) короче

Перепиши. Посмотрим, получится ли короче.

> 2) проще для понимания

Это да. Хотя - вопрос привычки :)

> 3) точно известно время работы

Оно в обоих случаях известно.

tailgunner ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> 1) короче

существенно короче только если писать на c++

на питоне длина кода примерно та же

хотя для совместимости с императивными программерами
рекомендуют по возможности функциональные конструкции
разворачивать в цикл.

2) проще для понимания

вопрос привычки.

по мне так сумма в виде sum(list_of_elements) понятнее чем сумма в виде цикла.

3) точно известно время работы

оно точно известно при любой форме записи

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

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

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

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

Так лучше?

sum [y|x<-[0..99], let y=sin x, y>0]

imp ★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

>это что, компрехеншн?

да

>Факториал вы тоже считаете генерируя список перемножая его элементы?

да

какие проблемы? Начто иначе нужен lazy evaluation? Чтобы и писать легко и работало в результате быстро.

imp ★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

>1) короче

в большинстве случаев будет намного длиннее. особенно в примерах сложней факториала

>2) проще для понимания

это троллинг

>3) точно известно время работы

что мешает посчитать асимптотическую сложность для обоих случаев? в чём принципиальная разница?

jtootf ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

>> в большинстве случаев будет намного длиннее. особенно в примерах сложней факториала

Возможно. Но не всегда. Вот в тех случаях когда нефункциональный подход будет короче - зачем всёравно писать функционально?

>> это троллинг

Это ИМХО =). Хотя согласен - это скорее дело привычки.

>> что мешает посчитать асимптотическую сложность для обоих случаев? в чём принципиальная разница?

Разница в том, что в случае если я напишу на C тупой цикл, который тупо суммирует N синусов, то я буду точно уверен, что время выполнения - O(N). Назвисимо от используемого компилятора. А в случае магии со списками и "труЪ функциональщиной" придётся надеяться на компилятор - то ли ему хватит ума дооптимизировать до O(N), то ли он родит нечто вроде O(N^2)...

P.S. Я не троллю, мне действительно интересно зачем всё это нужно.

Deleted ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

>Возможно. Но не всегда. Вот в тех случаях когда нефункциональный подход будет короче - зачем всёравно писать функционально?

это уже дзен и LISP-way

>Разница в том, что в случае если я напишу на C тупой цикл, который тупо суммирует N синусов, то я буду точно уверен, что время выполнения - O(N). Назвисимо от используемого компилятора. А в случае магии со списками и "труЪ функциональщиной" придётся надеяться на компилятор - то ли ему хватит ума дооптимизировать до O(N), то ли он родит нечто вроде O(N^2)...

а компиляторы C ничего не оптимизируют, да? или в труЪ-функциональщине нет профайлеров и вывода промежуточного кода?

>Я не троллю, мне действительно интересно зачем всё это нужно

что именно? ФП? для решения задач, которые хорошо ложатся на ФП ;) в случае небольших выпадающих из общей картины участков есть FFI, для haskell бонусом - квазиквотация и штуковины вроде harpy

если же вся работа сводится к борьбе с ФП, то стоит задуматься - а нужен ли он здесь вообще

jtootf ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

>> а компиляторы C ничего не оптимизируют, да? или в труЪ-функциональщине нет профайлеров и вывода промежуточного кода?

А теперь прочитай пост топикстартера:

>> В результате создается 3 списка и вычисления происходят в 3 циклах (рекурсиях?).

>> Императивным подходом получаем 1 список + 1 цикл

>> Скажите, это как-нибудь оптимизируется хоть в каком-нибудь ФЯ? 3 списка заменяются одним? 3 рекурсии заменяются одним циклом? Или все остается так, как выглядит =( ? Этож какое неоправданное использование ресурсов!

Т.е. императивным подходом мы гарантированно получаем O(N), без всяких если. А функциональным - 50/50, как решит компилятор. Допустим я для разработки и отладки использую хороший компилятор X и пишу только в функциональном стиле. У меня всё работает хорошо и быстро. Но мои исходники скачал Вася Пупкин и собрал их не таким хорошим компилятором Y, который кое-где не додумался соптимизировать до уровня компилятора X. В результате у васи моя программа работает в N раз медленней. Причём это *та*же* программа с теми же алгоритмами. Лично мне вот такая неопределённость и не нравится.

Компиляторы C и C++ в принципе не умеют оптимизировать алгоритмы (кроме простейших случаев), да от них это и не требуется. Никто в здравом уме не станет писать высокоуровневый код типа "сумма(синус(*) от 1.0 до 99.0 с шагом 1.0)" на C++. С одной стороны это далеко не всегда удобно, но с другой стороны всегда можно гарантировать как и за какое время будет работать алгоритм. На любом компиляторе, которым эта программа соберётся.

Deleted ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> Т.е. императивным подходом мы гарантированно получаем O(N), без всяких если. А функциональным - 50/50, как решит компилятор.

Такое впечатление, что ты вообще не читал ответов. Или ты просто троллишь.

> Компиляторы C и C++ в принципе не умеют оптимизировать алгоритмы

Тем не менее, результаты работы разных компиляторов могут различаться в разы, и что - выкинем Си/Си++?

tailgunner ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

>Но мои исходники скачал Вася Пупкин и собрал их не таким хорошим компилятором Y

для haskell есть ghc. чем будет собирать Вася? yhc? jhc? они несколько нестабильные, вообще говоря

>всегда можно гарантировать как и за какое время будет работать алгоритм. На любом компиляторе, которым эта программа соберётся

это не так. особенно для C++

а по сабжу - судя по всему, тебя больше волнует переносимость ФП-исходников между компиляторами, чем оптимизация. тогда о чём вообще речь? что же касается самой оптимизации, то все связанные со сложностью вопросы оцениваются ничуть не хуже чем для императивных языков

jtootf ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> Никто в здравом уме не станет писать высокоуровневый код типа "сумма(синус(*) от 1.0 до 99.0 с шагом 1.0)" на C++

Не? :D

s = sum_fn<double>(1.0, 99.0, sin, 1.0)

(тело sum_fn остается в качестве упражнения читателю :))

tailgunner ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

>> для haskell есть ghc. чем будет собирать Вася? yhc? jhc? они несколько нестабильные, вообще говоря

Для common lisp'а существует дофига компиляторов и интерпретаторов.

>> это не так. особенно для C++

Я пытаюсь сказать, что при написании программ на языках типа C++ никто не будет надеятся на то, что компилятор сможет хорошо оптимизировать сложный высокоуровневый код. Хотя некоторые компиляторы это и умеют.

>> а по сабжу - судя по всему, тебя больше волнует переносимость ФП-исходников между компиляторами, чем оптимизация. тогда о чём вообще речь?

Можно и так сказать.

>> что же касается самой оптимизации, то все связанные со сложностью вопросы оцениваются ничуть не хуже чем для императивных языков

В том и проблема, что из-за "подразумевающихся" оптимизаций для *языков* это никак не оценить. Только для конкретных компиляторов. У компиляторов C такой проблемы просто нет, так как они не умеют оптимизировать на таком уровне (я уже задолбался говорить одно и то же) =).

И хочу напомнить: я знаю, что в том же common lisp'е можно писать и императивно. Но почему многие не рекомендуют так делать? Мне вот это не понятно. Я пока не вижу ни каких плюсов в переписывании императивного кода в чисто функциональный, там где нет явного выигрыша вроде сильного упрощения кода и выигрыша в производительности. Только минусы.

Deleted ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

>Я пока не вижу ни каких плюсов в переписывании императивного кода в чисто функциональный, там где нет явного выигрыша вроде сильного упрощения кода и выигрыша в производительности. Только минусы

не видишь? не переписывай!

>Для common lisp'а существует дофига компиляторов и интерпретаторов

а CL и не функциональный язык: там как хочешь, так и пишешь

>Я пытаюсь сказать, что при написании программ на языках типа C++ никто не будет надеятся на то, что компилятор сможет хорошо оптимизировать сложный высокоуровневый код. Хотя некоторые компиляторы это и умеют

ты знаешь, на это нигде и никто не надеется. работает медленно - берём профайлер и оптимизируем. хоть в C++, хоть в Haskell, хоть в Scheme

>У компиляторов C такой проблемы просто нет, так как они не умеют оптимизировать на таком уровне

однако разница между результатом работы всё же есть, так? и как достигается переносимость? вот здесь - то же самое, только на "другом уровне"

jtootf ★★★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> В том и проблема, что из-за "подразумевающихся" оптимизаций для *языков* это никак не оценить. Только для конкретных компиляторов. У компиляторов C такой проблемы просто нет, так как они не умеют оптимизировать на таком уровне (я уже задолбался говорить одно и то же) =).


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

такие штуки как разворот рекурсии в цикл приводят к
_пропорциональному_ изменению времени выполнения
(плюс, возможно, уменьшение потребления памяти)

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> А можно вопрос (возможно глупый)? Вот хоть убейте не понимаю: зачем подобные вещи писать в чисто функциональном стиле, хотя если переписать обычным тупым циклом, то получится:

> 1) короче > 2) проще для понимания > 3) точно известно время работы

Как насчет параллелизации? MapReduce было популяризованно гуглом как среда которая параллельно вычисляет на произвольном числе машин, возможно на тысячах. Размер задачи будет соответствующий, на практике там будет не i=1..99 а i=1..999999999.

gods-little-toy ★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Нет, я все же не понял, почему функциональным стилем называется работа со списками(пусть и ленивыми)?
Серьезно, единственный функциональный пример тут >>3356901 - фвп и линейная рекурсия.

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

При чем тут MR? Это лишь удобная модель, которую понятно как распараллелить и под нее можно подвести многие задачи. И свой оверхед у нее есть.

anonymous ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Ладно ладно, вы опять меня убедили =).

Deleted ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

lists:foldl(fun(X, Y) -> X + sin(Y), 0, lists:seq(0, 99)).

что может быть проще?

Cy6erBr4in ★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

эх, сначало не заметил уточнения насчет "положительных" значений,
а потом не успел написать правильный вариант... напишу щас тогда :)

lists:foldl(fun(X, Y) -> 
                        case math:sin(Y) of
                            Z when Z >=0 ->
                                X + Z;
                            _ ->
                                X
                        end
                end,
                0, lists:seq(0, 99)).

Cy6erBr4in ★★★ ()

Re: [FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

Тебя что конкретно смущает? форматирование или синтаксис? Если первое, то тут да, что-то немного съехало, если второе, то дело привычки.

Cy6erBr4in ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.