Блин! Опять быстрая сортировка! Вы рискуете распугать тех, кто действительно заинтересован декларативным подходом и призвать троллей. Это, увы, не самый лучший пример. Дело в том, что хоаровский вариант реально быстр и сортирует на месте. Рекурсивный же только записывается красиво, но хоаровским, увы, не является. Это разные алгоритмы с разными свойствами. Об этом уже много раз писали на разных языках, статьи легко гуглятся. Главный аргумент троллей: евангелисты-декларативщики опять и опять приводят два-три примера неработающих алгоритмов! В хаскеллевском Data.List используется mergesort, поскольку сам по себе quicksort непрактичен и в функциональной реализации жаден до памяти. Декларативный подход серьезно играет в большем: в построении реактивных систем, в алгебраическом описании сложных архитектур, в принципиальной доказуемости декларативных утверждений. Я понимаю и полностью разделяю восхищение, испытываемое при первом знакомстве с ленивым "решетом Эратосфена" на Хаскеле (которое тоже вовсе не оно), или тем же рекурсивным quicksort, но прошу: не останавливайтесь на этом! Мы не должны выглядеть евангелистами с одними и теми же простыми притчами, у функционального и логического программирования есть гораздо больше классных результатов. Правда, они сложнее . А главное: не противопоставляйте парадигмы. Это мешает искусству владения ими всеми.
Моноид в категории Клейсли — это круто!!!
Посвятил часок вечером пятницы написанию варианта интерпретатора с внешней памятью (он в находится в репозитории). Разница в коде только в том, что команды PUT, GET, PUTI и GETI поселились в монаде IO, в которой есть возможность доступа к Vector.Mutable. После чего можно было приступить к тесту решетом Эратосфена.
При тех же условиях, что в статье про поросят (заполнение решетом памяти в 65536 ячейки, сто запусков):
чистый вариант (один прогон) — 43 сек! 100 прогонов — больше часа! Хаскель отстой, ФП — сферический конь в вакууме и т.д…
вариант с мутабельным вектором (тоже чистый, но запускаемый в монаде IO) — 9 сек на все сто прогонов!
С решением на Питоне для этого же компьютера я не сравнивал, но для меня было главное не победить кого-то. Основная задача — убедиться в том, что не изменяя принципам чистого функционального программирования, можно выбирать максимально подходящий вычислительный процесс, а так же что моноидальное решение легко расширяется и способно использовать эффективную внешнюю память.
Наивная реализация решета эратосфена требует для массива 65000 ячеек 16 миллионов шагов и каждый в десятка два инструкций, так что, скорее всего, моя реализация здорово уступит решению на С: там прямая работа с памятью, а у меня — программная реализация вектора. Мы в разных категориях, и задачи у нас разные.
Хвала ленивым вычислениям — этот монстр не создавался в памяти ни разу!
При запуске получилось 3 миллиона шагов выполнения программы.
Простое вычисление — 1.26 секунд
Простое вычисление, компиляция с флагом -O2 — 0.47 секунд
Простое вычисление (в монаде IO, -O2) — 0.35 секунд
Вычисление с логированием числа шагов (-O2) — 1.28 секунд
Вычисление с логированием числа шагов и кода (-O2) — 2.62 секунд. Замедление связано с ленивостью кортежа.
Вычисление с логированием используемой длины стека (-O2) — 65.24 секунд. Замедление связано с вычислением длины списка.
Вполне неплохо, в монаде IO компилятор оптимизирует вычисления максимально.
Тут, мне кажется, всё просто: непонятно на лекции — спрашивайте преподавателя, непонятно после лекции — идите в библиотеку, непонятно в книжке — меняйте книжку, ищите статьи и первоисточники. Читайте зарубежные учебники (не потому что они лучше, а потому что они все разные). Сами устраивайте семинары среди студентов. Ставьте собственные задачи. И очень скоро вы поймёте: это вам вообще надо? У вас не будет потребительского отношения к математике, если она часть вашей жизни. Люди творили математику в войну, в голод, в юности и в старости, даже в психушке. И вовсе не из-за пользы, а потому что это была их жизнь, их понимание прекрасного. Таких всегда немного. Эйлеры, Гильберты, Фихтенгольцы, Фейнманы и Савватеевы всегда дефицит. И наконец, математика никому ничего не должна. Она не должна быть полезной. Не должна быть понятной. Только непротиворечивой. Её результатами можно пользоваться, и опыт показывает, что практически всё от абстрактных алгебр до теории кос, паркетов или категорий находит своё применение. Причём, не по отдельности, а в совокупности. Забавно наблюдать, как народ, ожидая год от года появления новых технологий, усиления мощности смартфонов, развития интеллектуальных сервисов, капризно возмущается: "Зачем нам все эти сложности с функциональным программированием — оно не практично, с коллайдерами — они дорогие и бесполезные, с теорией категорий и гомологической теорией типов — очередная фигня, которую понимает полторы сотни человек… эллиптические кривые, abc-гипотеза, вы что серьёзно считаете, что на них можно потратить жизнь?" Так что, по-моему, нет какой-то "проблемы современных математических текстов", которую можно было бы решить., как нет, скажем, "проблемы современного театра (потому что я в нём ничерта не смыслю)".
На первый вопрос, боюсь, никто вам не ответит. А если ответит, то к нему будет сотня новых вопросов: от чисто методических, до обвинении в ангажированности.
А на второй вопрос я не берусь ответить, поскольку вводится три новых безразмерных параметра, и численный эксперимент выдаст такое множество разных решений, что одного ответа точно не получится. Поиск аналитического решения мне представляется чересчур громоздким для того, чтобы быть полезным. А вы чего имено ожидаете от этого распределения? Каких свойств?
О, я ждал такого комментария! Видите ли, эта серия статей про универсальные свойства распределений случайных величин, про принципы матстатистики и некоторые любопытные закономерности, имеющие математическое объяснение. Она не про экономику, также как законы Мерфи — никакие не законы. А так, вы совершенно правы, реальный мир учитывает всё, что вы перечислили и выдает какие-то распределения, меняющиеся со временем и плохо измеряемые. И народ их аппроксимирует гаммой, Вейбуллом или лог-нормальными распределениями не от безысходности или незнания, а в силу важных аналитических свойств этих распределений, позволяющих дальнейший анализ (устойчивость, бесконечная делимость, максимизация энтропии и т.д.) Вот об этих неочевидных свойствах мне и хочется рассказать.
Я специально указал использованные алгоритмы, хоть они и предельно просты. Можно усложнять модель, можно вводить новые параметры и играть с этим. Это несложно, увлекательно, но, на мой взгляд, не очень полезно для практического применения. Люди склонны сопротивляться красивым теоретическим решениям или отыскивать в них лазейки.
Всё-таки, идемпотентность, не очень удачный термин в данном контексте. Речь идет о чистоте функции или прозрачности по ссылкам, но слово "идемпотентность" кроме труднопроизносимости имеет совсем другой смысл. Это когда f(f(x))=f(x).
Не уверен, что верно понял вопрос. Замечу что "осознанная произвольность" — это то, что отличает живые системы от неживых, но она не нарушает законов физики. В открытых диссипативных системах возможна самоорганизация, локально понижающая энтропию, но для всей системы, в контексте окружающей среды, деятельность таких необычных флуктуаций энтропию все равно повышают. Экономика управляется осознанно на микроуровне, ансамбль миркоэкономик требует нового управления в виде макроэкономической политики целой страны, ансамбль экономик целых стран тоже хорошо бы регулировать, но тут начнётся борьба с масонами и гегемонией и, полагаю, всё опять вернётся к стохастике. Не любят люди чужого управления, пусть даже и разумного.
Есть варианты с налогами и сборами, которые неплохо работают, до тех пор, пока люди подчиняются алгоритму. Но люди выше этого и начинают мухлевать. Так что да, все возвращается на круги своя :)
Блин! Опять быстрая сортировка! Вы рискуете распугать тех, кто действительно заинтересован декларативным подходом и призвать троллей. Это, увы, не самый лучший пример. Дело в том, что хоаровский вариант реально быстр и сортирует на месте. Рекурсивный же только записывается красиво, но хоаровским, увы, не является. Это разные алгоритмы с разными свойствами. Об этом уже много раз писали на разных языках, статьи легко гуглятся. Главный аргумент троллей: евангелисты-декларативщики опять и опять приводят два-три примера неработающих алгоритмов! В хаскеллевском Data.List используется mergesort, поскольку сам по себе quicksort непрактичен и в функциональной реализации жаден до памяти. Декларативный подход серьезно играет в большем: в построении реактивных систем, в алгебраическом описании сложных архитектур, в принципиальной доказуемости декларативных утверждений. Я понимаю и полностью разделяю восхищение, испытываемое при первом знакомстве с ленивым "решетом Эратосфена" на Хаскеле (которое тоже вовсе не оно), или тем же рекурсивным quicksort, но прошу: не останавливайтесь на этом! Мы не должны выглядеть евангелистами с одними и теми же простыми притчами, у функционального и логического программирования есть гораздо больше классных результатов. Правда, они сложнее . А главное: не противопоставляйте парадигмы. Это мешает искусству владения ими всеми.
Моноид в категории Клейсли — это круто!!!
Посвятил часок вечером пятницы написанию варианта интерпретатора с внешней памятью (он в находится в репозитории). Разница в коде только в том, что команды
PUT,GET,PUTIиGETIпоселились в монаде IO, в которой есть возможность доступа к Vector.Mutable. После чего можно было приступить к тесту решетом Эратосфена.При тех же условиях, что в статье про поросят (заполнение решетом памяти в 65536 ячейки, сто запусков):
чистый вариант (один прогон) — 43 сек! 100 прогонов — больше часа! Хаскель отстой, ФП — сферический конь в вакууме и т.д…
вариант с мутабельным вектором (тоже чистый, но запускаемый в монаде IO) — 9 сек на все сто прогонов!
С решением на Питоне для этого же компьютера я не сравнивал, но для меня было главное не победить кого-то. Основная задача — убедиться в том, что не изменяя принципам чистого функционального программирования, можно выбирать максимально подходящий вычислительный процесс, а так же что моноидальное решение легко расширяется и способно использовать эффективную внешнюю память.
Наивная реализация решета эратосфена требует для массива 65000 ячеек 16 миллионов шагов и каждый в десятка два инструкций, так что, скорее всего, моя реализация здорово уступит решению на С: там прямая работа с памятью, а у меня — программная реализация вектора. Мы в разных категориях, и задачи у нас разные.
Добавил в статью ссылку на репозиторий.
Сравнения с программой на С я не проводил, хотя и правда это интересно.
Я собрал тестовую задачу в которой склеил все программы-примеры и умножил моноидально ещё 10000 раз.
Хвала ленивым вычислениям — этот монстр не создавался в памяти ни разу!
При запуске получилось 3 миллиона шагов выполнения программы.
Простое вычисление — 1.26 секунд
Простое вычисление, компиляция с флагом
-O2— 0.47 секундПростое вычисление (в монаде IO,
-O2) — 0.35 секундВычисление с логированием числа шагов (
-O2) — 1.28 секундВычисление с логированием числа шагов и кода (
-O2) — 2.62 секунд. Замедление связано с ленивостью кортежа.Вычисление с логированием используемой длины стека (
-O2) — 65.24 секунд. Замедление связано с вычислением длины списка.Вполне неплохо, в монаде IO компилятор оптимизирует вычисления максимально.
Перечисленные вами проблемы, действительно реальны, важны и интересны, но обсуждаемая статья, к сожалению, не про них.
Тут, мне кажется, всё просто: непонятно на лекции — спрашивайте преподавателя, непонятно после лекции — идите в библиотеку, непонятно в книжке — меняйте книжку, ищите статьи и первоисточники. Читайте зарубежные учебники (не потому что они лучше, а потому что они все разные). Сами устраивайте семинары среди студентов. Ставьте собственные задачи. И очень скоро вы поймёте: это вам вообще надо? У вас не будет потребительского отношения к математике, если она часть вашей жизни. Люди творили математику в войну, в голод, в юности и в старости, даже в психушке. И вовсе не из-за пользы, а потому что это была их жизнь, их понимание прекрасного. Таких всегда немного. Эйлеры, Гильберты, Фихтенгольцы, Фейнманы и Савватеевы всегда дефицит. И наконец, математика никому ничего не должна. Она не должна быть полезной. Не должна быть понятной. Только непротиворечивой. Её результатами можно пользоваться, и опыт показывает, что практически всё от абстрактных алгебр до теории кос, паркетов или категорий находит своё применение. Причём, не по отдельности, а в совокупности. Забавно наблюдать, как народ, ожидая год от года появления новых технологий, усиления мощности смартфонов, развития интеллектуальных сервисов, капризно возмущается: "Зачем нам все эти сложности с функциональным программированием — оно не практично, с коллайдерами — они дорогие и бесполезные, с теорией категорий и гомологической теорией типов — очередная фигня, которую понимает полторы сотни человек… эллиптические кривые, abc-гипотеза, вы что серьёзно считаете, что на них можно потратить жизнь?" Так что, по-моему, нет какой-то "проблемы современных математических текстов", которую можно было бы решить., как нет, скажем, "проблемы современного театра (потому что я в нём ничерта не смыслю)".
На пяти рандомных клетках.
Спасибо! Вы очень точно выразили то, что я думаю на этот счет.
Совершенно верно! Об этом была вторая из опубликованных глав о "нормальности ненормальности".
Ни то ни другое, с моей стороны это развёрнутое и честное "не знаю". А ваши слова о движении, по-моему, и есть ответ.
Гигиеническую роль чистоты в ООП играет принцип инкапсуляции, так что он и там есть и используется.
Не размышляйте о том, что творится в голове авторов, в этом знании нет никакой пользы.
На первый вопрос, боюсь, никто вам не ответит. А если ответит, то к нему будет сотня новых вопросов: от чисто методических, до обвинении в ангажированности.
А на второй вопрос я не берусь ответить, поскольку вводится три новых безразмерных параметра, и численный эксперимент выдаст такое множество разных решений, что одного ответа точно не получится. Поиск аналитического решения мне представляется чересчур громоздким для того, чтобы быть полезным. А вы чего имено ожидаете от этого распределения? Каких свойств?
О, я ждал такого комментария! Видите ли, эта серия статей про универсальные свойства распределений случайных величин, про принципы матстатистики и некоторые любопытные закономерности, имеющие математическое объяснение. Она не про экономику, также как законы Мерфи — никакие не законы. А так, вы совершенно правы, реальный мир учитывает всё, что вы перечислили и выдает какие-то распределения, меняющиеся со временем и плохо измеряемые. И народ их аппроксимирует гаммой, Вейбуллом или лог-нормальными распределениями не от безысходности или незнания, а в силу важных аналитических свойств этих распределений, позволяющих дальнейший анализ (устойчивость, бесконечная делимость, максимизация энтропии и т.д.) Вот об этих неочевидных свойствах мне и хочется рассказать.
Я специально указал использованные алгоритмы, хоть они и предельно просты. Можно усложнять модель, можно вводить новые параметры и играть с этим. Это несложно, увлекательно, но, на мой взгляд, не очень полезно для практического применения. Люди склонны сопротивляться красивым теоретическим решениям или отыскивать в них лазейки.
Спасибо за перевод! Про безопасное приведение очень полезная информация.
Всё-таки, идемпотентность, не очень удачный термин в данном контексте. Речь идет о чистоте функции или прозрачности по ссылкам, но слово "идемпотентность" кроме труднопроизносимости имеет совсем другой смысл. Это когда f(f(x))=f(x).
Не уверен, что верно понял вопрос. Замечу что "осознанная произвольность" — это то, что отличает живые системы от неживых, но она не нарушает законов физики. В открытых диссипативных системах возможна самоорганизация, локально понижающая энтропию, но для всей системы, в контексте окружающей среды, деятельность таких необычных флуктуаций энтропию все равно повышают. Экономика управляется осознанно на микроуровне, ансамбль миркоэкономик требует нового управления в виде макроэкономической политики целой страны, ансамбль экономик целых стран тоже хорошо бы регулировать, но тут начнётся борьба с масонами и гегемонией и, полагаю, всё опять вернётся к стохастике. Не любят люди чужого управления, пусть даже и разумного.
Есть варианты с налогами и сборами, которые неплохо работают, до тех пор, пока люди подчиняются алгоритму. Но люди выше этого и начинают мухлевать. Так что да, все возвращается на круги своя :)