LINUX.ORG.RU

Худший случай для ФП?

 , , ,


0

1

Очень часто можно встретить такое мнение:

Для чего-нибудь алгоритмического или математического я использую ФП. Но для любого рода симуляции ООП решение гораздо проще.

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

В сравнении ООП версия проста и очевидна: просто меняй объекты как требуется (вызовом их методов, конечно). Объекты содержат ссылки друг на друга, все обновления происходят с потерей информации о прошлом. Но так ли всё просто?

Допустим симуляция происходит с фиксированным шагом и в течение одного из этих шагов танк стреляет. Надо просто добавить снаряд в коллекцию объектов симуляции. Но тут есть загвоздка. Танки, обработанные ранее в симуляции не будут знать о снаряде, а обработанные позже будут.

Чтобы такого не происходило, надо отложить создание всех новых объектов до конца кадра.

Теперь, предположим, каждый танк принимает решение что делать основываясь на состоянии остальных объектов поблизости. Танк1 сканирует ближайшие объекты, двигается вперёд. Танк2 делает тоже самое и видит, что Танк1 слишком близко к нему, хотя на самом деле это не так, Танк2 имеет неправильные представления о положении Танк1, полученные как бы из будущего.

Для этой проблемы есть пара решений: разделить кадр на фазу принятия решений и на фазу перемещения. Второе — сохранить список всех изменений и потом атомарно применять его на финальном этапе.

Если бы симуляция сразу писалась в функциональном стиле, костылей, придуманных выше, вводить бы не пришлось. Это более естественный способ работы, когда у тебя нет мутабельных структур данных. Было бы ФП решение проще ООП? Может быть и нет. Хоть все обновления и отложены, остаётся вопрос как управляться с передаваемой вокруг информацией об изменениях.

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

★★★★★

Последнее исправление: PolarFox (всего исправлений: 1)
Ответ на: комментарий от emulek

Танк1 перемещается в контексте, в котором Танк2 неподвижен. А Танк2 перемещается при неподвижном Танк1

«принимает решение на передвижение». Вообще чисто для игрушки можно ввести понятие инициативы а-ля DnD - т.е. кто там первый встал, еще определить надо отдельным броском.

arkhnchul ★★★
()

Чтобы такого не происходило, надо отложить создание всех новых объектов до конца кадра.

Чтобы такого не происходило, изменения нужно вносить либо методом «stop the world» («всем лежать полчаса, изучать потолок»), как это делается в кин-дза-дзаJava, либо работать со всеми акторами параллельно и совершенно независимо, сообщая о результате ровно тогда, когда все объекты доложат супервизору о своей готовности, как это делается в Эрланге.

blexey ★★★★★
()
Ответ на: комментарий от PolarFox

то в кваках.

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

arkhnchul ★★★
()
Ответ на: комментарий от emulek

В SICP ЕМНИП есть простой пример, с банковскими аккаунтами.

Этот пример, про который ты говоришь, это не ФП-подход. Там мы имеем либо одно разделяемое муттабельное состояние, либо 2 независимых муттабельных. Чистый ФЯП такое сделать не позволит.

anonimous
()

Чистое ФП это говно. Рулят комбинированные подходы. Да, ессно, тащить весь мир в параметре функции это неправильно, криво, и неудобно.

lovesan ★★★
()
Ответ на: комментарий от anonymous

Эрланг такой же «чисто функциональный» как C++ «объектно-ориентированный», евпочя.

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

lovesan ★★★
()
Ответ на: комментарий от monk

Для ФП очень неудобным является случай,

Тут я вижу обычный цикл с ручной обрезкой токена. Да, рекурсию я тоже вижу, но это по-прежнему паскаль со скобками. ФП не вижу.

В то время как не-ФП

Тут я вижу замыкание. Чистое ФП.

Хочу понять, что я упустил? В срач не хочу. Спасибо.

anonymous
()
Ответ на: комментарий от Manhunt

Для этой проблемы есть пара решений: разделить кадр на фазу принятия решений и на фазу перемещения. Второе — сохранить список всех изменений и потом атомарно применять его на финальном этапе.

Это типовые решения, ничего костыльного в них нет.

для игрушек — да, может быть. А вообще для моделирования сложных систем этот подход обычно не годен.

emulek
()
Ответ на: комментарий от arkhnchul

«принимает решение на передвижение»

они оба двигаются, кагбэ одновременно. Это получается реалистично. Создаются два форка реальности, для каждого танка свой, а потом эти форки мержатся.

emulek
()
Ответ на: комментарий от lovesan

Да, ессно, тащить весь мир в параметре функции это неправильно, криво, и неудобно.

можно не весь, а только ближайшее окружение.

emulek
()
Ответ на: комментарий от anonymous

Ну давай, умник, расскажи нам, как ты одновременно меряешь импульс и координаты частиц?

anonymous
()
Ответ на: комментарий от emulek

Другой анонимус выше писал уже. Есть матрица состояний и есть поток событий, меняющий состояния для следующего шага в соответствии с определенным алгоритмом.

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

Также, не смотря на твой оптимизм, вычисления тебе придется производить определенными поциями — любая модель так или иначе сведется к этому, единственное что ты можешь, это в некоторой степени управлять величиной шага.

anonymous
()
Ответ на: комментарий от anonymous

когда ты будешь их мержить, тебе придется как-то разруливать коллизии

придётся. Но это в любом случае придётся. Ибо ничего непрерывного IRL не бывает.

уж не говоря о том, что это совершенно бестолковая трата ресурсов

а как влияет Танк1 на движение Танка2, если между ними Over9000 метров? Правильно, никак. А стало быть достаточно взять лишь небольшую окрестность, а не всё сразу. IRL так тоже есть, гугли про скорость света.

Также, не смотря на твой оптимизм, вычисления тебе придется производить определенными поциями — любая модель так или иначе сведется к этому, единственное что ты можешь, это в некоторой степени управлять величиной шага.

«оптимизм» у тебя. А скорее — блеяние олигофрена. Потому что я не представляю, как ты собрался проводить все расчёты СРАЗУ. Поделись, будь так любезен...

emulek
()
Ответ на: комментарий от emulek

придётся. Но это в любом случае придётся. Ибо ничего непрерывного IRL не бывает.

Да, придется, например танк въехал в стену/яму/другой танк. Но это _в_процессе_вычислений_ придется делать в любом случае. Ты же предлагаешь уже после этого смержить множество копий матрицы состояний. Понимаешь разницу?

Также, возможно, будет полезно определить преоритеты событий.

А стало быть достаточно взять лишь небольшую окрестность, а не всё сразу

Квинтэссенция бреда. Нет у тебя никаких окрестностей, только состояния. Hint: карта точно такой же обект, как и танк с т.з. алгоритма.

вычисления тебе придется производить определенными поциями


как ты собрался проводить все расчёты СРАЗУ

Наркоман? Какая буква тебе непонятна в слове _порциями_?

Поделись, будь так любезен...

Есть несколько вариантов. Оптимальный, имхо — обход по событиям. Как я писал выше, это позволяет ограничиться обсчетом только измененных состояний. При необходимости можно этот список предварительно оптимизировать, удалив взаимоисключающие действия.

anonymous
()
Ответ на: комментарий от anonymous

Хочу понять, что я упустил?

В контексте топика под ФП понимаются чистые алгоритмы и структуры данных. Как Haskell. В замыкании применяется set! на уже определённую переменную.

monk ★★★★★
()
Ответ на: комментарий от anonymous

Да, придется, например танк въехал в стену/яму/другой танк. Но это _в_процессе_вычислений_ придется делать в любом случае. Ты же предлагаешь уже после этого смержить множество копий матрицы состояний. Понимаешь разницу?

понимаю. Но ВСЮ матрицу не нужно мержить повторно, если один танк въехал в яму. Необходимо и достаточно пересчитать координаты этого танка. Если два танка столкнулись, то достаточно пересчитать конфликт только для двух этих танков. Я не вижу во всём этом проблемы.

Также, возможно, будет полезно определить преоритеты событий.

это можно и при мерже делать.

А стало быть достаточно взять лишь небольшую окрестность, а не всё сразу

Квинтэссенция бреда. Нет у тебя никаких окрестностей, только состояния. Hint: карта точно такой же обект, как и танк с т.з. алгоритма.

Hint: алгоритм придумываешь ты, и можешь его делать любым, каким хочешь. Если в твоём алгоритме нет окрестностей, а в моём есть, то ты — неосилятор.

как ты собрался проводить все расчёты СРАЗУ

Наркоман? Какая буква тебе непонятна в слове _порциями_?

понятна. А какая буква тебе непонятна в слове «окрестность»?

Оптимальный, имхо — обход по событиям.

на самом деле, это оптимизация. И годна она лишь тогда, когда этих событий немного. Если это не 100 танчиков, а скажем поверхность со 100 точками, на которой ты хочешь смоделировать непрерывный процесс, то такой вариант ничего не даст — «события» происходят во всех точках в каждый квант времени.

emulek
()
Ответ на: комментарий от emulek

Но ВСЮ матрицу не нужно мержить повторно, если один танк въехал в яму. Необходимо и достаточно пересчитать координаты этого танка.

Блин. Не надо ничего мержить и пересчитывать по 20 раз. Вообще. Ты просто меняешь значение в матрице состояний. В процессе вычисления этого значения проверяешь коллизии. Один раз на одно состояние. Все, обрабатываем следующее событие, т.е. вычисляем новое значение для соответствующего этому событию состояния.Опять один раз. И так пока не кончатся события для текущего шага. Затем переходим к следующему шагу, ad infinitum.

на самом деле, это оптимизация

Да, но это очевидная оптимизация, альтернатива, например — обход матрицы состояний, размер которой гарантированно больше очереди событий. Естественно, могут быть другие факторы, и тогда надо смотреть.

anonymous
()
Ответ на: комментарий от emulek

А какая буква тебе непонятна в слове «окрестность»?

Проблема не в буквах, а в «окрестности». Ее нет, просто нет, совсем нет.

anonymous
()
Ответ на: комментарий от yoghurt

изобразить - да, гарантировать - нет

Aswed ★★★★★
()
Ответ на: комментарий от lovesan

Эрланг такой же «чисто функциональный» как C++ «объектно-ориентированный», евпочя.

ага, там наследование и традиционные объекты с виртуальными методами и прочей атрибутикой сплошь и рядом...

swwwfactory ★★
()
Ответ на: комментарий от anonymous

Что за симуляция без случайностей? Это обычное вычисление, которое можно аналитически расписать

тут недавно что-то про уравнения Навье-Стокса было. реши-ка их аналитически

MyTrooName ★★★★★
()
Ответ на: комментарий от lovesan

тащить весь мир в параметре функции это неправильно

монады рулят

MyTrooName ★★★★★
()
Ответ на: комментарий от anonymous

Ты просто меняешь значение в матрице состояний. В процессе вычисления этого значения проверяешь коллизии. Один раз на одно состояние.

не взлетит. Коллизии ещё надо найти. Вот пример:

1. снаряд перед танком

2. снаряд за танком

Вот и спрашивается, была тут коллизия, или нет? В обоих состояниях снаряд не в танке.

Т.ч. эти твои события надо сначала рассчитать, а потом уже их обходить. А то не очень понятно, как снаряд влияет на танк, если ни в одном состоянии модели снаряд не встречается с этим танком?

emulek
()
Ответ на: комментарий от anonymous

Проблема не в буквах, а в «окрестности». Ее нет, просто нет, совсем нет.

это твоя проблема и проблема твоего алгоритма.

emulek
()
Ответ на: комментарий от emulek

Вот и спрашивается, была тут коллизия, или нет?

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

Да, и поскольку для всех состояний у нас единое хранилище, то: 1.исходные данные для разрешения коллизий легкодоступны; 2.Нам не требуется ничего знать о конкретных объектах.

эти твои события надо сначала рассчитать, а потом уже их обходить

События это просто набор данных: «танк_1 изменил_курс +1.5», «снаряд танк_2 начал_движение_по_курсу», «танк_3 остановился», «гора_123 стоит_на_месте»... Вот этот список обходишь, данные (+1.5) подставляешь в соотв обработчик состояния (изменил_курс) для соответствующего объекта (танк_1). Обработчик проверяет коллизии и изменяет соответствующее состояние (курс для танк_1).

это твоя проблема и проблема твоего алгоритма

Нет, это проблема твоя и твоего алгоритма, куда ты впихнул непонятную и ненужную сущность. У меня этого нет — нет и проблемы.

anonymous
()
Ответ на: комментарий от emulek

не взлетит

Вообще-то уже взлетело. Речь, разумеется, не о танчиках. Такие задачи встречаются довольно часто.

anonymous
()
Ответ на: комментарий от anonymous

Вообще-то уже взлетело. Речь, разумеется, не о танчиках. Такие задачи встречаются довольно часто.

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

emulek
()
Ответ на: комментарий от anonymous

События это просто набор данных: «танк_1 изменил_курс +1.5», «снаряд танк_2 начал_движение_по_курсу», «танк_3 остановился», «гора_123 стоит_на_месте»... Вот этот список обходишь, данные (+1.5) подставляешь в соотв обработчик состояния (изменил_курс) для соответствующего объекта (танк_1). Обработчик проверяет коллизии и изменяет соответствующее состояние (курс для танк_1).

я в курсе. Повторяю: это одно из решений.

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

у тебя нет потому, что у тебя объекты влияют друг на друга тогда, и только тогда, когда есть коллизия. Если танк проехал мимо ямы, ямы НЕ СУЩЕСТВУЕТ.

IRL это не так, солнышко светит для всех. Т.е. такое упрощение мало где применимо.

emulek
()
Ответ на: комментарий от emulek

у тебя объекты влияют друг на друга тогда, и только тогда, когда есть коллизия.

Наоборот, коллизия возникает когда объекты влияют друг на друга. Это у всех так. Процитирую тебя же: «а как влияет Танк1 на движение Танка2, если между ними Over9000 метров? Правильно, никак.»

Если танк проехал мимо ямы, ямы НЕ СУЩЕСТВУЕТ.

Если танк не проехал мимо ямы, то коллизия будет обнаружена и обработана. Разумеется, для этого яма должна «существовать», т.е. иметь соответствующее состояние. Для танка же отсутствие влияния ямы неотличимо от отсутствия самой ямы.

IRL это не так, солнышко светит для всех. Т.е. такое упрощение мало где применимо.

Вот и не делай подобных «упрощений». Ты пытаешься притянуть некие обобщения, которые по факту лишь генерят дополнительные сущности без необходимости.

Повторяю: это одно из решений.

Все альтернативы — это либо криво реализованное то же самое (в лучшем случае), либо захардкоженый по самые гланды хардкор, либо недоделанный глючно-падучный Пульт Управления Вселенной. Ну и множество промежуточных мутантов.

anonymous
()
Ответ на: комментарий от anonymous

Наоборот, коллизия возникает когда объекты влияют друг на друга. Это у всех так. Процитирую тебя же: «а как влияет Танк1 на движение Танка2, если между ними Over9000 метров? Правильно, никак.»

у меня так потому только, что танки в разных окрестностях. А у тебя окрестностей нет. Потому твой код проверяет коллизию танков №1 и №2, а мой код — не проверяет.

Если танк не проехал мимо ямы, то коллизия будет обнаружена и обработана. Разумеется, для этого яма должна «существовать», т.е. иметь соответствующее состояние.

вот видишь — у тебя яма влияет(потенциально) на ВСЕ танки. А у меня — только на те, которые в окрестности ямы. Ещё раз — окрестность ямы это круг вокруг этой ямы, с радиусом который равен расстоянию, которое проедит самый быстрый танк от ямы за квант времени (со «скоростью света»). Очевидно, что любой танк не доедет до ямы, если он не в этом круге.

emulek
()
Ответ на: комментарий от emulek

Я прекрасно понимаю, какое решение ты предлагаешь, мы все через это проходили. Почему так делать не надо я уже говорил, где твоя абстракция течет — показал. Но ты можешь продолжать.

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