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

Котоны, я тут почитал про Хаскель и у меня встал вопрос. Я правильно понимаю, что когда вы пишете на Хаскеле, вы не думаете об асимптотической сложности кода вообще?

В понятиях хаскеля ты и не должен думать, твоя задача объявить формализм, а задача интерпретатора найти решение. Слишком высок уровень над машиной

В понятиях хаскеля ты и не должен думать, твоя задача объявить формализм, а задача интерпретатора найти решение. Слишком высок уровень над машиной

Ну тогда я правильно понял.

Непрактично :)

Знаю паренька, любителя хаскеля и лиспа, который контесты пилит на функциональных языках

так что, вероятно, асимптотика играет свою роль

Интересно, на каких

хаскель в основном, еще скала (хотя это больше смесь java с крестами)

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

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

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

Ну здрасте. Берёшь почти любой эффективный алгоритм - он использует изменяемые данные (массивы, хэш-таблицы). Можно ли его столь же эффективно переписать на неизменяемых - вопрос

Вы говорите про эффективность или алгоритмическую сложность? Если вы вместо модификации структуры будете ее копировать - то выростет коэфициент, но как выростет сложность?

в терминах асимптотики RAM-машины разнцы нет, соль в операциях Input/Output в память, которые в данной модели не учитываются

Всем привет! #работа #Vacancy #Moscow #Office #Senior #developer #Go #ML #Ruby #Python #Java #C++ ЗП: 150к - 250к RUB на руки. Контакт @mandarinka25 (Марина) Вакансия представлена рекрутинговым агентством. Ищем: Senior Go Developer -а. Продукт: Платформа, позволяющая автоматически создавать решения для бизнеса на базе машинного обучения. Задачи: Создание инфраструктурных решений, выстраивание архитектуры приложений, разработка и поддержка микросервисов. Ожидаем от вас: Опыт работы от 2 лет, уверенное знание одного из языков (Go, Ruby, Python/Java/C++). Желание переходить на Go. Подробнее http://amp.gs/kPVu Условия: Опцион, гибкий график, возможность несколько дней в неделю работать удалённо. Спасибо!

Вы говорите про эффективность или алгоритмическую сложность? Если вы вместо модификации структуры будете ее копировать - то выростет коэфициент, но как выростет сложность?

Ещё как вырастет. Копировать массив длины N стоит O(N), а модифицировать - O(1)

В хаскеле ко всему прочему развито использование алгебраических типов и паттернг-матчинг, как это интерпретировать в сложность? В сложность какой машины, конкретной, на которой выполняется сейчас? А если это выполнить на машине, которая будет уметь в алгебраические типы, тогда как?

Если говорим о external memory моделях, то да, но там все вычисления по определению эффективные и за О(1)

Ну меня-то интересует та машина, на которой я буду запускать.

Ну меня-то интересует та машина, на которой я буду запускать.

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

Ещё как вырастет. Копировать массив длины N стоит O(N), а модифицировать - O(1)

Как минимум, проблема в том, что O(N^2) + O(N) = O(N^2), разве нет?

Што

при чём тут это

Если алгоритм делает O(N^2) модификаций над структурой данных со средним размером O(N), то с копированиями это будет уже O(N^3)

Што?

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

Не совсем понимаю, почему не оба сразу.

Сначала оптимизация алгоритмической сложности, потом бенчмарки.

Потому что алгоритмическая сложность в целом ниочем, так как никто не помнит про константу. Например, для умножения матриц есть Алгоритм Копперсмита — Винограда у которого O^{2.3727}, но его мало кто использует из-за большой константы.

Это всё так, но между алгоритмом за линию и за квадрат тем не менее обычно выбирают линию.

А там разве под капотом не используются изменяемые структуры данных?

собссно неизменяемые там нужны, чтобы компилятору было проще придумывать, как решать задачи

а под капотом он может творить любую ересь

А потом окажется, что у этого вашего алгоримта за линию константа 50, а у квадрата 2, и максимальное N=4. Бенчи тут совсем не нужны, давайте проверять сложность.

Котоны, я тут почитал про Хаскель и у меня встал вопрос. Я правильно понимаю, что когда вы пишете на Хаскеле, вы не думаете об асимптотической сложности кода вообще?

Зачем он тебе? Возьми нормальный язык. Скалу или окамл, например

А потом окажется, что у этого вашего алгоримта за линию константа 50, а у квадрата 2, и максимальное N=4. Бенчи тут совсем не нужны, давайте проверять сложность.

Доведение до абсурда, круто

Я тоже так могу

Интересно, часто ли применяют алгоритмы для максимального N=4

А потом окажется, то максимальное N=1000000 и квадрат вообще не может его когда-либо посчитать

Доведение до абсурда, круто

давайте обсудим на примере какой-то более конкретной задачи)

Сортировка

Интересно, часто ли применяют алгоритмы для максимального N=4

Никогда не сортировали массив из 4 элементов или не искали там максимальное?)

Сортировка скучно, там как раз на списках норм

Никогда не сортировали массив из 4 элементов или не искали там максимальное?)

Сортировал, но не считал ассимптотику

Ну здрасте. Берёшь почти любой эффективный алгоритм - он использует изменяемые данные (массивы, хэш-таблицы). Можно ли его столь же эффективно переписать на неизменяемых - вопрос

Любая изменяемая структура данных моделируется неизменяемыми с добавлением логарифма в асимптотику. Привет, персистентный массив

Никогда не сортировали массив из 4 элементов или не искали там максимальное?)

искать - иммутабельная операция и максимум за линию

Любая изменяемая структура данных моделируется неизменяемыми с добавлением логарифма в асимптотику. Привет, персистентный массив

Кидай пруфы

Кидай пруфы

https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2

Спасибо)

Дерево отрезков над структурой

Это, правда, еще и памяти лишний логарифм кушает

Ещё как вырастет. Копировать массив длины N стоит O(N), а модифицировать - O(1)

Кстати, а вот интересный вопрос, откуда вы взяли такую оценку? Мне это кажется не очень очевидным.

Зачем он тебе? Возьми нормальный язык. Скалу или окамл, например

А почему скала или окамл? В чём преимущества?

Но для многих структур есть честная персистентность без потерь в асимптотике

Кстати, а вот интересный вопрос, откуда вы взяли такую оценку? Мне это кажется не очень очевидным.

Ну, memcpy быстрее линии не может работать)

в асимптотике

А почему скала или окамл? В чём преимущества?

На них можно не обмазываться монадами, а писать работающий код

Я просто хотел немного заняться ФП, поэтому интересуюсь

Ну, memcpy быстрее линии не может работать)

С правильной структурой может

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

Ну, memcpy быстрее линии не может работать)

а вот и нет!

Ну, memcpy быстрее линии не может работать)

Не очень понятно, почему.

в некоторых особых случаях он может отработать за константу

Делаешь персистентное RBST и эмулируешь memcpy за логарифм

На них можно не обмазываться монадами, а писать работающий код

То есть, по сути, получается лаконичнее?

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

Ну понятно, что на специальных структурах данных быстрое копирование. Но у любой ли структуры есть такой неизменяемый с быстрым копированием эквивалент?

То есть, по сути, получается лаконичнее?

Получается практичнее

в некоторых особых случаях он может отработать за константу

Например?

просто ремап памяти 8)

в некоторых особых случаях он может отработать за константу

mmap?

Ну понятно, что на специальных структурах данных быстрое копирование. Но у любой ли структуры есть такой неизменяемый с быстрым копированием эквивалент?

Ну ты можешь сделать массив с быстрым копированием за логарифм. На нем строишь свою любимую структуру

Ну, с учётом ограничения на размер адресного пространства всё работает за константу, конечно

просто ремап памяти 8)

ага

mmap?

Хитро!

Ну ты можешь сделать массив с быстрым копированием за логарифм. На нем строишь свою любимую структуру

Собственно, это отвечает на мой вопрос, да.

Зачем тут возник срач "асимптотики vs бенчмарки", я так и не понял.

Правда, памяти жрет много и работает медленно. Но хаскеллистов это никогда не волновало

Собственно, это отвечает на мой вопрос, да.

еще в хаскеле есть мутабельные массивы если очень хочется

data.array.st

это возмутительно!

в терминах асимптотики RAM-машины разнцы нет, соль в операциях Input/Output в память, которые в данной модели не учитываются

Но вот итоговый результат будет весьма разным

просто ремап памяти 8)

Кстати, ремап же по страницам идёт. Значит, всё равно O(N)!

Получается практичнее

Понятно, а не посоветуешь какой-нибудь хороший туториал или книгу? Можно на английском. Так опыт в программировании есть (алгоритмы, промышленное), а в функциональном нет

Понятно, а не посоветуешь какой-нибудь хороший туториал или книгу? Можно на английском. Так опыт в программировании есть (алгоритмы, промышленное), а в функциональном нет

Начни с любого функционального языка, чтобы суть понять

Хоть с хаскеля

Начни с любого функционального языка, чтобы суть понять

голосую за racket

даёшь стековые языки во все поля

factor ftw! *осёл из шрека.жпг*

Что там с изменяемыми структурами в стековых языках?

factor ftw! *осёл из шрека.жпг*

жс

Что там с изменяемыми структурами в стековых языках?

Без понятия.

Но получается всратый и нечитаемый непосвящёнными код, оч круто.

Начни с любого функционального языка, чтобы суть понять

Да начать, изучить базовые вещи я могу, а меня интересует что-то более структуризированное и нацеленное на практику, типа такого, но про ФП

структуризируй в своей голове

Да начать, изучить базовые вещи я могу, а меня интересует что-то более структуризированное и нацеленное на практику, типа такого, но про ФП

Ну например, Real world ocaml

Зачем тут возник срач "асимптотики vs бенчмарки", я так и не понял.

А ещё при прочих равных алгоритмы с одинаковой асимптотикой и константами могут сильно различаться