1. Куча / Говнокод #25088

    0

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    6. 6
    7. 7
    При решении каких задач наиболее органично использовать конечные автоматы?
    
    Посоветуйте задачи, желательно прикладные и не из области разбора регулярных выражений
    или лексического анализа. Какой-нибудь пример, на котором можно продемонстрировать
    практическое применение конечных автоматов.
    
    Где вам пригождались автоматы или знания о них в реале?

    SEO: #fsm #AKKA

    Запостил: vistefan, 15 Ноября 2018

    Комментарии (123) RSS

    • SEO: #fsm #AKKA
      Ответить
    • Любая задача, которая формулируется как "если мы в таком-то состоянии, мы делаем это, если в другом — нечто другое". Пример из жизни: "если мы избраны лидером для шарда, и нас просят выполнить транзакцию, мы выполняем её локально, если нет — проксируем её".
      Ответить
    • Напиши свой протокол поверх UDP или UDP-Lite
      Ответить
    • Сетевые протоколы.
      Ответить
    • Тикет в багтрекере обычно подчиняется стейт-машине, которая похоронена где-то в реализации.

      Любая (компьютерная, карточная, настольная) игра — это конечный автомат, где действия игрока — это события, изменяющие (обычно многочисленные, но конечные) состояния игрового мира.
      Любая база данных, не обладающая бесконечной памятью — это конечный автомат, где пользовательские запросы являются событиями. Аналогично можно рассматривать и веб-сервер.

      Как это можно использовать? Для тестирования, к примеру, генерируя случайные наборы событий и проверяя, что поведение автомата удовлетворяет инвариантам.
      Тут много технических деталей, но идея, кмк, очень красивая
      http://qfpl.io/posts/intro-to-state-machine-testing-1/
      http://qfpl.io/posts/intro-to-state-machine-testing-2/
      > Где вам пригождались автоматы или знания о них в реале?

      В основном видел много сетевого кода, организованного в виде огромной таблицы функций, в которой одним индексом является текущее состояние, а в другом — тип полученного пакета.
      Ответить
      • Спасибо.

        Да, с играми можно придумать замечательные примеры.
        Ответить
    • Не так давно в энтерпрайзе у меня был объект "заявка" который мог переезжать в разные состояния, и это описывалось стейт машиной. Эта хуйня в интерпрайзе так часто встречается что для нее даже есть много тулзов.

      Руби
      https://github.com/aasm/aasm
      Пистон
      https://github.com/viewflow/django-fsm
      Жабаспринг
      https://projects.spring.io/spring-statemachine/
      Жабажбос
      https://docs.jboss.org/jbossas/javadoc/4.0.4/common/org/jboss/util/state/StateMachine.html

      Особо толстые энтрепрайзники даже имеют для это UI:
      Микрософт
      https://docs.microsoft.com/ru-ru/dotnet/framework/windows-workflow-foundation/state-machine-workflows

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


      Наконец автоматами всегда описывают протоколы (как верно сказал гость). Посмотри на диаграммы GBP, STP или даже того же TCP.
      Ответить
      • Упоминание стейт-машин в интерпрайзе будет неполным без http://www.bpmn.org/
        Ответить
      • > не понимаю почему ты не считаешь это практическим

        О, я вижу, что был превратно понят. Видимо, я неясно высказался. Я не имел ввиду, что разбор регулярных грамматик -- это не практический случай. Я только имел ввиду, что хочу узнать другие случаи практического применения, потому что с этими я уже знаком.
        Ответить
    • в новой команде на стендап-митинге бросил пару таких слов. вроде приняли за умного
      Ответить
      • Это правильно.

        Скажешь на стендапе "полиномиальный алгоритм" и все с уважением смотрят
        Ответить
    • В "PHP" нет никаких автоматов, и потому я за "PHP"
      Ответить
      • Есть. Состояние в БД. Событие в HTTP. Твой скрипт обрабатывает один переход конечного автомата...
        Ответить
        • Сейчас придет Сёма и скажет что обычному программисту автоматы не нужны
          Ответить
          • Но тут пока никто так и не смог сказать для чего они нужны среднестатистическому программисту.
            Ответить
            • А ещё тут пока никто так и не смог сказать, для чего нужно быть «среднестатистическим программистом», и зачем о нём думать. Вероятно, «среднестатистическому программисту» не нужен и свободный софт. А ещё, видимо, «среднестатистическому программисту» достаточно знать информацию примерно с первых 50-ти страниц учебника о языке, на котором он пишет, чтобы писать свой «среднестатистический код», причём на любом языке одинаковый. Если «среднестатистический программист» — это человек, которому не интересны знания в собственной профессии, который рутинно выполняет свою работу и не хочет без крайней необходимости (читай: деньги) делать что-либо сверх ожидаемого от него фирмой или начальством, то ни быть им, ни думать о том, что ему нужно или не нужно, нет никакого смысла.
              Ответить
              • Вот представь, что тебе надо пилить отчеты для какой-нибудь опердени. Программирования там минимум, гораздо важнее будет знание предметной области. Вряд ли у тебя там будет желание делать что-то сверх нормы и оставаться на работе после шести.

                Но ведь кто-то должен всё это пилить?
                Ответить
                • Отчеты должны генерироваться системой отчетов, управлять которой может бизнес-интеллидженс-аналист со знаниями SQL/MDX/какого-то скриптового ЯПа.

                  Если где-то день-деньской сидит программист и пишет SELECT * FROM PETUHI WHERE IQ<80, то нахуй и такого программиста и такую контору.
                  Ответить
                • > Но ведь кто-то должен всё это пилить?

                  Да, но с вероятностью 100% такие люди найдутся. Об этом не нужно специально заботиться, это место пусто не будет, туда невидимая рука рынка сама поставит какого-то человека, скорее всего посредственного специалиста, или уставшего, или нуждающегося, или не амбициозного. Ну, как сказали выше, «среднестатистического». Это ОК. Но вот зачем специально размышлять о таком человеке, или уж тем более умышленно им быть, я не понимаю.

                  Специально думать надо про свободные программы, потому что они нуждаются в этом, там законы рынка не действуют, там анархия.
                  Ответить
                  • Это - не программист вообще. Среднестатистические- это веб-программисты, как фронт-, так и бекенд-, десктоп. Кто ещё?
                    Ответить
                • Ну макрос-программисты - это недопрограммисты вообще. Вот поэтому: "Программирования там минимум, гораздо важнее будет знание предметной области.". Но и такие тоже есть, да.
                  Ответить
              • А языки программирования - не свободный софт (как и большинство иде)?

                Школьник, ты опять начал хуйню нести. Спроси у своих коллег, где и когда они по работе сталкивались с конечными автоматами. Зачем конечные автоматы веб-программисту, как фронт-, так и бекенд-? Десктоп-программисту? Нет, ты можешь конечно и цыкломяши мацать в свободное от работы время, просто ни копейки денег оно тебе не принесет. А потом читая посты таких как ты создается впечатление что нужно знать дохуя всего чтобы быть веб-макакой, развивается комплекс неполноценности и всё такое. А проблема-то не в тех, кто читает, проблема в долбоёбах вроде тебя, которые в интернет понтоваться ходят.
                Ответить
                • >> А языки программирования - не свободный софт
                  Языки могут быть спецификацией (она обычно или бесплатна или доступна за небольшую сумму) или реализацией (она может быть как платна, как и бесплатна)

                  Твой вопрос не имеет смысла

                  >>Спроси у своих коллег, где и когда они по работе сталкивались с конечными автоматами

                  Обезьяна, тут уже 10 человек отписалось и все рассказали зачем нужны конечные автоматы (при том что конечные автоматы это не теория очередей, про нее даже самоучки знают) а тебе всё мало
                  Ответить
                  • >Языки могут быть спецификацией (она обычно или бесплатна или доступна за небольшую сумму) или реализацией (она может быть как платна, как и бесплатна)
                    И то и то обычно швабодно. Вон даже мс начала швабодку любить.

                    Подсвинок пиздоголовый, с чем из этого большинство (если вам так ненавистен среднестатистический программист) столкнется в работе?
                    Ответить
                    • >>И то и то обычно швабодно.
                      Нет. Ты просто ничего кроме CPython в жизни не видел. Стандарт С++ не бесплатен. Реализиция языка Wolfram Language далеко не всегда бесплатна, про цену компиляторов каких нить Verilog тебе Броманд расскажет
                      Ответить
                      • Видел я дохуя и больше, именно видел, а не более-менее серьезно писал.

                        >Стандарт С++ не бесплатен
                        Я и написал "обычно". Конпеляторы цпп в массе швабодны.

                        >Verilog
                        Конпеляторы/иде для прикладного программирования. Теперь доволен?
                        Ответить
                        • Это IDE-то свободы? Intellij Idea Ultimate? RubyMine? WebStorm? Visual Studion Professional?

                          >>прикладного программирования
                          Wolfram точно не системный:)
                          Ответить
                          • вольфрам это хуита какая-то для математиков? Ни разу не слышал.

                            Идея разве не попенсорц? RubyMine и WebStorm - это главные/единственные иде для этих языков? Насчет студии я и написал "обычно", второй раз тебе напоминаю.
                            Ответить
                            • >>вольфрам это хуита какая-то для математиков?
                              ага

                              >>Идея разве не попенсорц?
                              коммунити -- да
                              ультимейт нет

                              >>RubyMine и WebStorm - это главные/единственные иде для этих языков?
                              Ну Ruby и, например, PyCharm почти что дефакто
                              Ответить
                              • > коммунити - да
                                И где исходники скачать?
                                Ответить
                                • Не поверишь
                                  https://github.com/JetBrains/intellij-community
                                  Ответить
                                  • О_о
                                    Ответить
                                    • Возможно вам так же будет интересно узнать что бесплатные версии с исходниками есть у pycharm community (лежит внутри той же репы) и кажется еще то-ли golang то-ли rust plugin.

                                      Исходников точно нету у webstorm, rubymine и pycharm professional
                                      Ответить
                                    • > О_о

                                      Лол, а ты не знал? )
                                      Ответить
                              • С каких пор математики - это программисты?

                                >Конпеляторы/иде для прикладного программирования. Теперь доволен?

                                pycharm да, но даже на работе вполне хватает комунети.
                                Ответить
                                • >>С каких пор математики - это программисты?
                                  Кнут называет себя математиком.
                                  Дейкстра называл себя математиком, и даже подчеркивал что называть то, чем он занимается "комптютер сайнс" это всё равно что называть хирургию "knife сайнс"
                                  Ответить
                                  • > сайнс

                                    Вот не лень было тебе переключать раскладку, чтобы после «knife» написать русскими буквами «сайнс»
                                    Ответить
                            • > идея
                              > попенсорц
                              /0
                              Ответить
                              • Нет Сёма прав, гоммунити правда попенсорц
                                Ответить
                • > А потом читая посты таких как ты создается впечатление
                  Проезжая мимо станции, у меня улетела шляпа

                  > что нужно знать дохуя всего чтобы быть веб-макакой
                  Нет, не нужно. Будь ей, без каких-либо знаний, я лично тебе разрешаю.
                  Ответить
                • > Спроси у своих коллег
                  Так я и спросил, здесь разве не программисты сидят? Повторяю, это НЕ форум для домохозяек, тут мои коллеги, программисты.

                  > в интернет понтоваться ходят

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

                  Вот например 1024-- мой вопрос показался интересным, и цели, с которой я его задал, я тоже достиг.Но я НЕ СТАВИЛ вопрос о том, нужны ли кому-то автоматы и обязательно ли их кому-нибудь знать. Это уже твой личный Freud.
                  Ответить
                  • Но это тебе сраку порвало http://govnokod.xyz/_25088/#comment-402737

                    Твои вопросы вполне имеют право на существование, просто знание конечных автоматов в работе среднестатистическому программисту (слово средне понимаешь? не пыхарю, которым ты почему-то его пытаешься выставить) ничего не даст от слова вообще.
                    Ответить
                    • Чувак, там дыли ссылки на реализацию автоматов для django и rails. Угадай, пользуются ли ими веб программисты>
                      Ответить
                      • И? Мало модулей для джанги? Всеми ими кто-то хоть когда-то да пользовался.
                        Ответить
                      • В "PHP" ничего из этого нет. Именно поэтому я за "PHP".
                        Ответить
                        • И тут барабанная дробь...

                          ...............
                          https://symfony.com/doc/current/workflow/state-machines.html

                          Сифони
                          Сраный симфони, практически вордпресс

                          Алсо
                          https://github.com/yohang/Finite
                          https://github.com/winzou/state-machine
                          Ответить
                          • ООП и фреймворки не нужны. Я просто пишу процедурный код в одном файле и теку.
                            Ответить
                            • > и теку
                              Пиши на си, заодно и память течь будет.
                              Ответить
                              • В умелых руках память может течь даже в языках с GC
                                Ответить
                                • Нефритовый стержень в руках самурая подобен ситару.
                                  Ответить
                              • Кстати, а бесконечный размер очереди считается утечкой памяти? Или только если на память никто не ссылается? Тогда утечки в языках с гц невозможны.
                                Ответить
                                • > бесконечный размер очереди
                                  Наверное. Как и кривое кеширование когда кеш не отпускает старые объекты.
                                  Ответить
                                  • Для этого есть всякие софтрефересны
                                    Ответить
                                • Именно о нем я и говорил
                                  Ответить
                    • Я, конечно, понимаю, с кем разговариваю, поэтому никаких пояснений о том, откуда у тебя взялось представление о среднестатистическом программисте, просить не стану.

                      Если под средним-по-больнице программистом понимается более-менее что попало, тогда средний программист в среднем может знать какую угодно теорию и помочь ему на практике и что-то дать в работе тоже может приблизительно что угодно.
                      Ответить
                  • О, так я уже не неосилятор? :)
                    Ответить
    • Состояния питания в ACPI: http://images.books24x7.com/bookimages/id_6137/0401.jpg
      Тоже стейт машина
      Ответить
      • >стейт машина
        ЯДЕРНЫЙ RAGE! НЕТУ ТАКОГО ТЕРМИНА, СКОТИНА! КОНЕЧНЫЙ АВТОМАТ, СУКА! А НЕ СТЕЙКМАШИНА!
        Ответить
        • У нас “steak machine” обычно называют электрогрилем.
          Ответить
    • Выбор дешевых авиабилетов в процессе их оценивания (уточнения цены) внутри очереди приоритетов.

      P.S.
      > Где вам пригождались автоматы или знания о них в реале?
      Чесно говоря, знания о автоматах на мозг не давят. Можно сформировать в одном предложении:
      "храним состояние и переходим в другое по выволнению некоего условия"
      Ответить
      • > Выбор дешевых авиабилетов в процессе их оценивания (уточнения цены) внутри очереди приоритетов.

        Поподробнее?
        Ответить
        • > Поподробнее?
          Ответить
          • Priority Queue, каждое решение хранится в некотором состоянии. На верхушке всегда находится самое дешевое. Однако, чтоб вычислить конечную цену надо много чего сделать (для каждого). Так вот, берем самое верхне решение, переводим его состояние (обрабатываем) и отправляем обратно в очередь (на место, соответсвующее его цене). Финал: верхнее решение обчислено до конца, и осталось на верхушке.

            Самих состояний может быть много. Писать их не буду, слишком специфично. Однако, если с точки зрения аггрератора цен, то там навеное не так уж и много состояний
            Ответить
            • Выглядит как обычный Дейкстра, ну или A*.
              Ответить
              • Кстати, летаешь бизнес-классом или в пассажирском?
                Ответить
                • Завидуешь ему?
                  Ответить
                  • Завидовать можно только размеру пениса, а у него против моего балтийского убивца шансов нет.
                    Ответить
                    • >балтийского

                      Латыш, шоль?
                      Ответить
                      • осетин
                        Ответить
                        • P.S. Предчувствую следующий вопрос, поэтому дам ссылку на ответ:
                          http://holywars.ru/comments/17552
                          Ответить
                          • После этого вопросов стало ещё больше
                            Ответить
                        • ИНКАНУС -- ОСЕТИН???
                          Ответить
                          • Тот, который с нижним подчеркиванием - да.
                            Ответить
                • Билеты Цюрих -- Нижний Новгород оказываеццо не такие дорогие, как я думал.
                  Ответить
              • Задание повышенной сложности: найти в поисковиках A*.
                Ответить
                • https://ru.wikipedia.org/wiki/A*
                  Ответить
                  • А кроме Википедии?

                    У Гугла я так и не нашёл хвалёный режим verbatim. Кавычки не помогают.

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

                    Бинг, база которого уступает и Гуглу, и Яндексу, спокойно находит все статьи, в которых встречается A*.
                    Ответить
                    • А как я по твоему нашел эту статью?

                      https://www.google.ru/search?q=a*+algorithm
                      Ответить
                      • <А как я по твоему нашел эту статью?

                        В архиве брата Шуберта?
                        Ответить
                      • Да, со словом "algorithm" находит. Правда, с середины второй страницы начинает выводить статьи со словом "algorithm", но без A*. Хорошо, хоть полторы страницы результатов можно получить.
                        Ответить
                        • <хоть полторы страницы результатов можно получить.

                          "Неоконченная симфония", таки? Какая прелесть!
                          Ответить
                    • По этому я за Jump point search
                      Ответить
      • >>мозг не давят.
        Есть некоторые особенности, например конечные автоматы бывают детермеринованые и недетерминированые, и вот во втором случае надо быть аккуратным чтобы не получить экспоненциальную питушню.

        Создтатели движков регулярок не всегда это умеют, см. "Runaway Regular Expressions: Catastrophic Backtracking"
        Ответить
      • Кстати, о билетах: иногда нужно применить максимально возможную скидку, и иногда это np, и есть забавные решения типа https://www.optaplanner.org/

        Это кстати родтвенник упомянутого уже тут https://en.wikipedia.org/wiki/JBPM
        Ответить
    • Любая железка реализована как куча взаимодействующих аппаратных конечных автоматов. На верилоге без них никуда :3
      Ответить
    • Любой транслятор реализован как куча взаимодействующих программных конечных автоматов. На регулярках без них никуда :3
      Ответить
    • И вообще, насколько я знаю, даже в программировании на Си под ПЛК без ОС без этого тоже не обойтись.
      Ответить
      • Железки часто представлены как конечные автоматы, да.

        Записал в регистр что-то и железка перешла в состояние A, грубо говоря
        Ответить
    • >Где вам пригождались автоматы?

      Обокан, АКМ, АКМ-У, Скорострельный АКМ в "Тени чернобыля", "Зове припяти", "Чистом нёбе"

      > или знания о них в реале

      В пизде
      Ответить
    • Кстати да, хороший вопрос. Хорошо бы, если на ГК было больше таких обсуждений. Да и в жизни тоже.

      Вот в веб-питушне что-то такое наблюдается. Есть форма, есть валидация, есть отсылка запросов. Кто-то давит на кнопку, и обработчик должен учитывать, что питушня находится в одном из состояний:
      * есть изменения и ничего не сохраняли
      * нажимали на кнопку, запрос на валидацию идёт
      * запрос на валидацию прошёл, валидно
      * нажимали на кнопку, запрос на сохранение идёт
      * нет изменений или всё сохранили

      И тут и клиент эту пишутню с учётом этих стадий обрабатывает, и сервер. Дальше ещё можно добавить "авторизован/не авторизован для сервера" и "отправлена первая часть формы", "... вторая...", ...
      Ответить
      • Въебал первый минус.
        "Платон мне друк, да истина дороже."
        Ответить
      • В системах документооборота поведение документа или проекта внутри системы часто похоже на стейт-машину. Например, есть цикл между состояниями, когда эксперт таким-то набором средств вносит замечания и отправляет на доработку заказчику услуги несколько раз, потом проект переходит в другое состояние, и с ним можно сделать то-то и то-то.

        Но напоминает только концептуально. Такого, чтобы кто-то на уровне кода применял стейт-машины для подобных задач, я не видел. Возможно это оттого, что часто в начале работы над проектом реализуется какое-то очень небольшое подмножество бизнес-логики, а потом никто уже не рефакторит усложнившуюся систему, а просто добавляют кучу трудно отлаживаемых и противоречивых условий, при которых у кнопки «Редактировать» будет `display: block;`

        А ещё поведение задачи на гибкой доске (also known as agile board для тех, кто ненавидит свой родной русский язык и использует буржуйские термины) очень похоже на конечный автомат:
        planning
        todo
        in progress
        code review
        in progress
        code review
        ...
        testing (todo)
        testing (in progress)
        reopened
        code review
        ...
        testing (todo)
        testing (in progress)
        reopened
        code review
        ...
        done
        closed
        Ответить
        • >>документооборота
          >> Такого, чтобы кто-то на уровне кода применял стейт-машины для подобных задач, я не видел
          орлы?

          https://help.sap.com/doc/d9c75eebcfa840c8a4aa4b0e6a8136de/3.0.14/en-US/7c0bb3cd70061014aa44b2d6f9e344e9.html

          https://infostart.ru/public/841130/

          https://community.dynamics.com/crm/b/gonzaloruiz/archive/2016/09/27/state-machines-in-crm-for-status-transitions
          Ответить
          • Вот оно что… Спасибо, что показал.
            Ответить
            • Ахахаха
              http://1c.ruboard.ru/public/675140/

              Даже 1С ники знают про конечный автомат
              Сёма, лопни!
              Ответить
        • Ненависть тут не причем, на инглише на порядок больше информации. У нас все термины в конспектах сопровождались английским переводом.

          >стейт-машины
          Поди-ка найди мне книжку, в которой дается определение этому термину. Тоже ведь буржуйский термин.
          Ответить
          • > Поди-ка найди мне книжку
            Не найду, это сленг, причём это не то же самое, что конечный автомат. Стейт-машина не обязательно конечна. Конечна финит-стейт-машина.
            Ответить
            • Так у этого "термина" определение-то есть?
              Ответить
      • > Кстати да, хороший вопрос

        Спасибо.
        Ответить
    • Вы пидоры, почточно без меня базарити. Конченый автоматвэ в J из коробки есть глолгол для создания:
      sc=: 2 2 2$ 0 0  1 1  1 0  1 2  NB. state table
         <"1 sc
      ┌───┬───┐
      │0 0│1 1│
      ├───┼───┤
      │1 0│1 2│
      └───┴───┘
         y=: ' fourscore and seven years ago, our fathers'
         (0;sc;' '=a.) ;: y
      ┌──────────┬────┬──────┬──────┬─────┬────┬────────┐
      │ fourscore│ and│ seven│ years│ ago,│ our│ fathers│
      └──────────┴────┴──────┴──────┴─────┴────┴────────┘
         (0;sc;' '=a.) ;: '[email protected] zero  two'
      ┌─────┬─┬────┐
      │ zero│ │ two│
      └─────┴─┴────┘
      Ответить
    • Что за хуйню вы здесь обсуждаете?
      Ответить

    Добавить комментарий