время, потраченное программистом на то, что бы понять алгоритм — ничто по сравнению с суммарным временем, которое потратят пользователи на ожидание результатов от программы.
Утверждение верно только в случае если у вас уже есть шаблон решения. При отсутствии шаблона, в т.ч. полученого при учёбе, доминирующим становится скорее быстрое понимание алгоритма. Давайте уж говорить о стерильных предпосылках.
в данном случае оно окупится еще на этапе разработки, так как на реализацию Пинг-Понга уйдет намного больше времени, чем на ОПН ( ИМХО ).
В свете уже вышесказанного, предполагаю что всё будет с точностью до наоборот. Причём по всему циклу разработки, включая отладку и тестирование. Понимание здесь играет ключевую роль.
Я не позиционирую себя как гуру HPC, но я хотя бы привел аргументы, почему ОПН оптимальнее чем Пинг-Понг.
Согласен что это было не очень корректно. Попробую исправиться.
Поскольку инструментальные замеры отсутствуют попробуем разобрать с точки зрения логики.
Мне тут в коментах предлагали осмыслить формулу длиной 1 млн. символов и 100 тыс. парных скобок. Давайте на этот пример и обопрёмся. Но сделаем это чуть позже, после ответов на конкретные имеющиеся вопросы.
один посимвольный разбор в ОПН против множества тестов по регулярному выражению в Пинг-Понге, каждый из которых включает в себя посимвольный проход.
В Пинг-Понге нет посимвольных проходов от слова «совсем». Используются цельносмысловые единицы. как то «группа» — фрагмент обрамлённый скобками; операция выделяется во фрагмент на смысловом уровне и включает в себя два операнда на предопределённой операции; операнд — фрагмент, который отнесён к данной операции. То есть чем длиннее операнды тем более эффективно работает алгоритм. Нигде нет посимвольного прохода с логикой определения ветвления по условию.
Не совсем понял, что имелось в виду.
Имелось ввиду что замена фрагмента длиной 10 символов по индексам пройдёт быстрее анализа каждого из тех же 10 символов с множественной логикой для каждого.
Если я правильно понимаю таблицу с описанием алгоритма, после каждого теста по regex'пу выполняется замена обрабатываемого фрагмента строки на результат, что ведет к копированию всего хвоста строки. Если конечно длина результата не совпала с длиной фрагмента, что маловероятно.
Всё правильно. Замена фрагмента результатом происходит каждый раз по окончанию расчёта. Не готов по внутреннему устройству StringBuilder, но предполагаю, что там это происходит на уровне ссылок. То есть в указанное место вставляется новая ссылка с отбрасыванием ссылок заменяемого фрагмента и переиндексация хвоста. Насколько операция тяжёлая сказать затрудняюсь, но явно сильно оптимизированная где-то на уровне положить в стек — забрать из стека. Не будем забывать что стек это тоже массив. И когда вы складываете в стек или забираете из него — это тоже время.
Серьезным подходом считается написать реализации обоих подходов и сравнить. И при разработке новых алгоритмов всегда стоит сравнивать их с существующими аналогами.
Кто бы спорил с такой очевидной вещью если бы не такое понятие как трудозатраты.
Ладно на вопросы ответил, возвращаемся к логическому сравнению алгоритмов.
Начнём с того что отбрасываем как присутствующее в обоих алгоритмах — это элементарные операции + — * /, несмотря на то, что операция / тяжелее операции + как минимум в 40 раз. Они присутствуют одинаково в исходной формуле.
Что нам надо сделать для КАЖДОГО символа в ОПН:
Сортировка и расчёты
1. достать символ из строки по адресу (чтение из памяти, запись в регистр АЛУ, подготовка следующего адреса I++)
2. сравнить с образцами (цифры, знаки операций, скобки -16 образцов). Пусть образцы лежать в некой оптимизированной хэш таблице, но каждый нужно выдернуть и сравнить с поступившим символом, т.е. занести в регистр и произвести операцию сравнения. По совпадению перейти на команду соответствующей ветки. И тут 50 на 50 угадал ли процессор со следующей командой, уровень неопределённости достаточно высок. то бишь с конвейером могут быть проблемы и нехилый шанс заработать штраф в виде пропущенных тактов.
3. Для любой из веток проверить предусловие.
3.1 для цифры (работаем с вещественными числами с длиной >1) поместить в буфер для сборки числа. Мы не знаем следующего символа и не в курсе сформировано у нас число или нет.
3.2 для скобки открывающей. Увеличить счётчик скобок на 1; поместить в стек операций.
3.3 для скобки закрывающей. Взвести флаг «расчёт фрагмента»; проверить буфер сборки числа и если он не пуст, хотя он в данном случае всегда не пуст — проверку можно пропустить, перенести число в стек операндов; перейти на ветку расчёта фрагмента, реверс до открывающей скобки (расчёт фрагмента будет ниже); уменьшить счётчик скобок на 1, хотя это можно сделать по достижению скобки открывающей.
3.4 для операции. вытащить из стека предыдущую операцию и передать в регистр АЛУ для сравнения приоритетов.
3.4.1 если приоритет предыдущей операции ниже или это "(" или стек пуст, записать данную операцию в стек.
3.4.2 если приоритет предыдущей операции такой же, то записать текущую в промежуточное хранилище; вытащить предыдущую операцию из стека операций; вытащить 2-й операнд из стека; вытащить 1-й операнд из стека; результат положить в стек; вытащить текущую операцию из промежуточного хранилища и положить в стек операций.
3.4.3 если следующий оператор "(". передать текущую операцию в АЛУ; вытащить 2-й операнд из стека; вытащить 1-й операнд из стека; результат положить в стек; удалить "(" из стека; уменьшить счётчик скобок на 1( вверху был вариант когда счётчик уменьшался по ")" — это не особо важно); перейти на адрес последнего проверенного символа (его перед этим тоже сохранить где-то надо, а теперь считать) и ветку последовательного перебора.
Уфф! не уверен, что ничего не потерял, но вроде всё. Учтём что это для КАЖДОГО символа. Ну и обещаное.
Расчёт фрагмента от ")" выглядит теперь совсем простенько
1. Получили ")". Переходим в режим реверса. Записали адрес для последующего возврата на последовательный прямой перебор.
2. вытаскиваем предыдущую операцию. определяем что это за операция; вытаскиваем операнды (по одному), результат в стек операндов. И так в цикле до "("
3. получили "(". Закрываем расчёт фрагмента: удаляем "(" из стека; уменьшаем счётчик скобок; вытаскиваем адрес отработанной ")"; переходим на ветку прямого перебора с адреса + 1.
переходим на Пинг-Понг
1. достать символ из строки по адресу (чтение из памяти, запись в регистр АЛУ, подготовка следующего адреса I++)
2. сравнить с ")". Если «да», то записать индекс конца фрагмента. Иначе перейти на следующий символ.
3. Зафиксирован индекс конца фрагмента в переменной. Переход на реверс; смена шаблона поиска на "(".
4. сравнить символ по направлению движения с "(". Если «да», то записать в переменную индекс начала фрагмента.
5. записать фрагмент по индексам в строку «фрагмент»; перейти на ветку расчёта умножения.
6. расчёт слоя умножения в строке «фрагмент»
6.1 поиск "*" от начала фрагмента. Если найден, то выделить операнд слева (регулярное выражение); занести в переменную начало подфрагмента; перевести в dubl; выделить операнд справа (регулярное выражение); занести в переменную конец подфрагмента; перевести в dubl; результат заменяет подфрагмент в строке «фрагмент»; продолжить поиск с начала обработанного подфрагмента. Иначе переход на блок деления.
7. блок деления — аналогично блоку умножения
8. блок сложения вычитания — аналогично предыдущим.
9. результат расчёта фрагмента записать в рабочую строку вместо фрагмента по индексам.
10 перейти к поиску следующего фрагмента
Обратите внимание, что поиск по маске очень быстрая операция. Выделение операндов вряд ли сильно кратно больше чем предыдущая. поскольку тоже почти маска. Ну и здесь не алгоритм по каждому символу.
Здесь сложнее определить элементарные операции, поскольку неизвестны внутрянка и SnringBuilder регулярных выражений, но предположительно, по моему мнению здесь активно используется механизм поиска по маске или такой же как в ОПН по хэш таблице. Поскольку практически отсутствуют операторы ветвления конвейер должен работать эффективней.
В ОПН эффективнее должна работать замена подфрагмента результатом (результат кладётся на вершину стека), но и всё.
Так что нет очевидных причин для более быстрой работы ОПН на достаточно больших формулах. На коротких возможно и да.
Ну и некоторый упрёк, так сказать алаверды: всё что здесь написано, может не так подробно, Вы могли подчерпнуть в самой статье.
Если взять вместо мотаний взад-вперёд по строке последовательное движение с рекурсией, которая всё равно неизбежна в случае выражений типа ((a+b)*(c-d))*e
Нет в алгоритме рекурсии. Есть только прямое и реверсное (обратное) движение.
ваш алгоритм будет вынужден считать скобки, чтобы определить пару первой скобке...
Это не так. Первая же открывающая скобка от первой закрывающей однозначно идентифицирует фрагмент сколько бы вложений не содержала формула.
получится самый типовой нисходящий ручной парсер типа того, что в книге Страуструпа по C++.
За наводку на книгу — спасибо. Обязательно посмотрю.
А если добавить разбор по приоритетам операций — получится парсер Пратта.
Здесь нет разбора по приоритетам операций от слова «совсем». Приоритетность реализуется последовательностью блоков расчёта. То есть расчёты проводятся послойно, что повышает эффективность работы конвейера.
И, заметьте, никаких мотаний.
Не хотелось бы говорить до просмотра обозначенных вами алгоритмов, но без локальных реверсов я пока решений не встречал, да и просто логически это невозможно. В ОПН тоже есть реверсы если не по строке, то как вы назовёте сначала складывание в стек, а затем выборку из него. Это тот же самый реверс, только на вторичном хранилище.
ИМХО единственное достоинство Пинг-Понга — это его простота ( при чем только в понимании, в реализации не все так просто )
Вряд ли мы оба сейчас готовы квалифицированно ответить на такое однозначно. Надо проводить профилирование кода, запускать исполнение на тысячные циклы, делать зависимости от длины формул и прочее. Предлагаю оставить вопрос эффективности в покое. Мне достаточно что алгоритм прост и понятен.
Редкие случаи посимвольного разбора в ОПН в Пинг-Понге заменяются на тест регулярными выражениями по любому поводу. Количество проходов по исходной строке может быть очень большим — и это против одного прохода в ОПН.
Удивили. Алгоритм на ОПН — это ВСЕГДА посимвольный разбор. Да и
Пункт 'Замена фрагмента "(...)"' тянет за собой столько же копирований памяти.
Ох, не надо бы такое утверждать, лучше стоит восстановить информацию по замене фрагментов в строке. Операция, конечно, не однотактная, но… лучше посмотрите в источниках, которым доверяете.
Никто ничего не заучивает — все просто пользуются самым эффективным решением.
Когда говорят «самое эффективное» всегда хочется поинтересоваться: «С чем и как сравнивали?». И это я не про обсуждаемые алгоритмы.
Надеюсь вы не будете оспаривать, что нагляднсть плотно записанной строки сильно проигрывает нормальной математике
Нет не буду. Вы правы в том, что язык математики не зря был изобретён. Возражу в том, что перевод нормального математического языка в скобочную (инфиксную) запись, что в запись ОПН одинаков по сложности. Всё же ОПН много сложнее.
Вот ваша задача по постановке- это именно что (научиться) менять эти костыли/протезы/ходули/сапоги на ходу, вместо того, что бы одевать их в удобном месте глядя на изначальный, ничем не пожатый вид формул.
Возможно. Однако, на настоящий момент это ограничивается средствами ввода и передачи данных. Ведь глядя на математическую формулу вы сразу видите только структуру (образ формулы, катринку), причём многострочную, потом выделяете наиболее значимые фрагменты и лишь затем начинаете переходить к конкретным расчётам по приоритетам. То есть, насколько я понял, Вы предлагаете решить задачу прямой и обратной трансформации образов математических формул «на лету». И ввести это в стандарт.
Первая задача даже менее сложна чем вторая. Так что если по первой уже существуют конкретные решения, то вторя, по моему мнению, будет решена не скоро.
В целом, по высказанным вами соображениям согласен. Негоже терять наработанные цивилизационные, не побоюсь этого слова, решения, к которым относится и язык математики.
Насколько я понял, алгоритм, предложенный в статье является формализацией подхода, который используется человеком.
Да.
Зачем же рассказывать студентам то, что они умеют и практикуют со школьных времен?
Чтобы понимали наличие альтернатив и разных подходов. Плохо когда все дуют в одну дуду. ограничивает возможности развития.
Не лучше ли рассказать про ОПН, которая выигрывает у Пинг-Понга в производительности и используется в реальных проектах?
Во-первых, что выигрывает это ещё вопрос. Посимвольный разбор с разветвлённой логикой достаточно затратен сам по себе. Так что пока ещё бабушка надвое сказала.
Во-вторых, задачи разные и преимущество в одних может оказаться недостатком в других. Поэтому наличие разных инструментов повышает уровень свободы разработчика.
В-третьих, пока не было ОПН — не было и проектов с использованием данной нотации. Но всё течёт, всё изменяется.
Что по Вашему полезнее/интереснее?
Что интереснее это индивидуально. А вот полезнее знать где и что применить, причём независимо от текущей моды или коронки «так принято».
говорю Вам как студент))
Эх, хорошее время… Кстати, и время поиска нового, а не только заучивания устоявшихся норм и правил.
Прежде всего, есть два совершенно разных алгоритма:
Не знаю как у вас, а у нас учили, что если есть одинаковый вход и одинаковый выход, то разбираться надо со всем чёрным ящиком, а не с его частями.
почему вы называете всё это критикой ОПН?
Потому что в основе лежит именно запись (представление), в которую переформатируют инфиксную (привычную) запись, чтобы уже потом получить конечный результат. И тогда встаёт вопрос: «А надо ли корёжить исходное?» И при этом тратить учебное время на слом мозгов молодёжи. Для себя я ответил:«Не надо ни первое, ни второе.» Если ОПН была сделана во времена ограниченности инструментов управления кодом и железом, то при наличие на сегодня адекватных инструментов можно пожалеть молодёжь и не вбивать им в мозги старые дрожжи. Здесь рассматривались два ПОДХОДА к решению одной задачи.
Надеюсь я объяснил почему именно критика ОПН, а не конкретных алгоритмов и аппаратных ускорителей (акселераторов).
Понимаю ваше возмущение.
Пинг-Понг реализован на java. Перед этим я честно нарисовал алгоритм посимвольного разбора подобного разбору для ОПН и это мне сильно не понравилось прям на уровне алгоритма.
С вашего позволения, реализовывать ОПН не буду, задача не впечатляет.
Оставим это молодым. Подозреваю что кто-то это сделает без меня и, возможно, выложит результаты.
По большому счёту вы правы. Есть одинаковые вход и выход. Вопрос во внутренних подходах к обработке.
Лично для меня ОПН показался слишком перегруженным с точки зрения понимания и стало жалко молодёжь.
Да конечно. Можно просто сказать что есть одна входная корзинка и две на выходе. А как корзинки называются — дело третье.
И ещё, я критикую не саму ОПН, а её безальтернативность в процессе обучения.
В Пинг-Понге я ориентируюсь по знаку операции и отбираю по шаблону (регулярные выражения) левый и правый операнд. меня ни символы не интересуют, ни точки.
Ну да… Я тоже про это подумал. Как-то более-менее объективно оценить насколько эта операция будет забирать на себя ресурсы у меня получилось только чисто логически. Однако, сокращение интеллектуальных операций при работе с каждым символом может скомпенсировать эти затраты. Специализировано этим вопросом не занимался, поэтому ничего внятного сказать не могу.
Да я, чес слово, не против ОПН как таковой. Просто когда шерстил и Хабр и и-нет постоянно только ОПН в глаза лезет. А тут меня ещё один гуру от java слегка вздёрнул. А когда, на Хабре кстати, почитал обсуждения по разбору формул… Ну не вижу я тут безальтернативности, что и высказал. Ну и как-то это было скорее против засилия ОПН в учебном процессе.
Утверждение верно только в случае если у вас уже есть шаблон решения. При отсутствии шаблона, в т.ч. полученого при учёбе, доминирующим становится скорее быстрое понимание алгоритма. Давайте уж говорить о стерильных предпосылках.
В свете уже вышесказанного, предполагаю что всё будет с точностью до наоборот. Причём по всему циклу разработки, включая отладку и тестирование. Понимание здесь играет ключевую роль.
Согласен что это было не очень корректно. Попробую исправиться.
Поскольку инструментальные замеры отсутствуют попробуем разобрать с точки зрения логики.
Мне тут в коментах предлагали осмыслить формулу длиной 1 млн. символов и 100 тыс. парных скобок. Давайте на этот пример и обопрёмся. Но сделаем это чуть позже, после ответов на конкретные имеющиеся вопросы.
В Пинг-Понге нет посимвольных проходов от слова «совсем». Используются цельносмысловые единицы. как то «группа» — фрагмент обрамлённый скобками; операция выделяется во фрагмент на смысловом уровне и включает в себя два операнда на предопределённой операции; операнд — фрагмент, который отнесён к данной операции. То есть чем длиннее операнды тем более эффективно работает алгоритм. Нигде нет посимвольного прохода с логикой определения ветвления по условию.
Имелось ввиду что замена фрагмента длиной 10 символов по индексам пройдёт быстрее анализа каждого из тех же 10 символов с множественной логикой для каждого.
Всё правильно. Замена фрагмента результатом происходит каждый раз по окончанию расчёта. Не готов по внутреннему устройству StringBuilder, но предполагаю, что там это происходит на уровне ссылок. То есть в указанное место вставляется новая ссылка с отбрасыванием ссылок заменяемого фрагмента и переиндексация хвоста. Насколько операция тяжёлая сказать затрудняюсь, но явно сильно оптимизированная где-то на уровне положить в стек — забрать из стека. Не будем забывать что стек это тоже массив. И когда вы складываете в стек или забираете из него — это тоже время.
Кто бы спорил с такой очевидной вещью если бы не такое понятие как трудозатраты.
Ладно на вопросы ответил, возвращаемся к логическому сравнению алгоритмов.
Начнём с того что отбрасываем как присутствующее в обоих алгоритмах — это элементарные операции + — * /, несмотря на то, что операция / тяжелее операции + как минимум в 40 раз. Они присутствуют одинаково в исходной формуле.
Что нам надо сделать для КАЖДОГО символа в ОПН:
Сортировка и расчёты
1. достать символ из строки по адресу (чтение из памяти, запись в регистр АЛУ, подготовка следующего адреса I++)
2. сравнить с образцами (цифры, знаки операций, скобки -16 образцов). Пусть образцы лежать в некой оптимизированной хэш таблице, но каждый нужно выдернуть и сравнить с поступившим символом, т.е. занести в регистр и произвести операцию сравнения. По совпадению перейти на команду соответствующей ветки. И тут 50 на 50 угадал ли процессор со следующей командой, уровень неопределённости достаточно высок. то бишь с конвейером могут быть проблемы и нехилый шанс заработать штраф в виде пропущенных тактов.
3. Для любой из веток проверить предусловие.
3.1 для цифры (работаем с вещественными числами с длиной >1) поместить в буфер для сборки числа. Мы не знаем следующего символа и не в курсе сформировано у нас число или нет.
3.2 для скобки открывающей. Увеличить счётчик скобок на 1; поместить в стек операций.
3.3 для скобки закрывающей. Взвести флаг «расчёт фрагмента»; проверить буфер сборки числа и если он не пуст, хотя он в данном случае всегда не пуст — проверку можно пропустить, перенести число в стек операндов; перейти на ветку расчёта фрагмента, реверс до открывающей скобки (расчёт фрагмента будет ниже); уменьшить счётчик скобок на 1, хотя это можно сделать по достижению скобки открывающей.
3.4 для операции. вытащить из стека предыдущую операцию и передать в регистр АЛУ для сравнения приоритетов.
3.4.1 если приоритет предыдущей операции ниже или это "(" или стек пуст, записать данную операцию в стек.
3.4.2 если приоритет предыдущей операции такой же, то записать текущую в промежуточное хранилище; вытащить предыдущую операцию из стека операций; вытащить 2-й операнд из стека; вытащить 1-й операнд из стека; результат положить в стек; вытащить текущую операцию из промежуточного хранилища и положить в стек операций.
3.4.3 если следующий оператор "(". передать текущую операцию в АЛУ; вытащить 2-й операнд из стека; вытащить 1-й операнд из стека; результат положить в стек; удалить "(" из стека; уменьшить счётчик скобок на 1( вверху был вариант когда счётчик уменьшался по ")" — это не особо важно); перейти на адрес последнего проверенного символа (его перед этим тоже сохранить где-то надо, а теперь считать) и ветку последовательного перебора.
Уфф! не уверен, что ничего не потерял, но вроде всё. Учтём что это для КАЖДОГО символа. Ну и обещаное.
Расчёт фрагмента от ")" выглядит теперь совсем простенько
1. Получили ")". Переходим в режим реверса. Записали адрес для последующего возврата на последовательный прямой перебор.
2. вытаскиваем предыдущую операцию. определяем что это за операция; вытаскиваем операнды (по одному), результат в стек операндов. И так в цикле до "("
3. получили "(". Закрываем расчёт фрагмента: удаляем "(" из стека; уменьшаем счётчик скобок; вытаскиваем адрес отработанной ")"; переходим на ветку прямого перебора с адреса + 1.
переходим на Пинг-Понг
1. достать символ из строки по адресу (чтение из памяти, запись в регистр АЛУ, подготовка следующего адреса I++)
2. сравнить с ")". Если «да», то записать индекс конца фрагмента. Иначе перейти на следующий символ.
3. Зафиксирован индекс конца фрагмента в переменной. Переход на реверс; смена шаблона поиска на "(".
4. сравнить символ по направлению движения с "(". Если «да», то записать в переменную индекс начала фрагмента.
5. записать фрагмент по индексам в строку «фрагмент»; перейти на ветку расчёта умножения.
6. расчёт слоя умножения в строке «фрагмент»
6.1 поиск "*" от начала фрагмента. Если найден, то выделить операнд слева (регулярное выражение); занести в переменную начало подфрагмента; перевести в dubl; выделить операнд справа (регулярное выражение); занести в переменную конец подфрагмента; перевести в dubl; результат заменяет подфрагмент в строке «фрагмент»; продолжить поиск с начала обработанного подфрагмента. Иначе переход на блок деления.
7. блок деления — аналогично блоку умножения
8. блок сложения вычитания — аналогично предыдущим.
9. результат расчёта фрагмента записать в рабочую строку вместо фрагмента по индексам.
10 перейти к поиску следующего фрагмента
Обратите внимание, что поиск по маске очень быстрая операция. Выделение операндов вряд ли сильно кратно больше чем предыдущая. поскольку тоже почти маска. Ну и здесь не алгоритм по каждому символу.
Здесь сложнее определить элементарные операции, поскольку неизвестны внутрянка и SnringBuilder регулярных выражений, но предположительно, по моему мнению здесь активно используется механизм поиска по маске или такой же как в ОПН по хэш таблице. Поскольку практически отсутствуют операторы ветвления конвейер должен работать эффективней.
В ОПН эффективнее должна работать замена подфрагмента результатом (результат кладётся на вершину стека), но и всё.
Так что нет очевидных причин для более быстрой работы ОПН на достаточно больших формулах. На коротких возможно и да.
Ну и некоторый упрёк, так сказать алаверды: всё что здесь написано, может не так подробно, Вы могли подчерпнуть в самой статье.
Нет в алгоритме рекурсии. Есть только прямое и реверсное (обратное) движение.
Это не так. Первая же открывающая скобка от первой закрывающей однозначно идентифицирует фрагмент сколько бы вложений не содержала формула.
За наводку на книгу — спасибо. Обязательно посмотрю.
Здесь нет разбора по приоритетам операций от слова «совсем». Приоритетность реализуется последовательностью блоков расчёта. То есть расчёты проводятся послойно, что повышает эффективность работы конвейера.
Не хотелось бы говорить до просмотра обозначенных вами алгоритмов, но без локальных реверсов я пока решений не встречал, да и просто логически это невозможно. В ОПН тоже есть реверсы если не по строке, то как вы назовёте сначала складывание в стек, а затем выборку из него. Это тот же самый реверс, только на вторичном хранилище.
Вряд ли мы оба сейчас готовы квалифицированно ответить на такое однозначно. Надо проводить профилирование кода, запускать исполнение на тысячные циклы, делать зависимости от длины формул и прочее. Предлагаю оставить вопрос эффективности в покое. Мне достаточно что алгоритм прост и понятен.
Удивили. Алгоритм на ОПН — это ВСЕГДА посимвольный разбор. Да и
Ох, не надо бы такое утверждать, лучше стоит восстановить информацию по замене фрагментов в строке. Операция, конечно, не однотактная, но… лучше посмотрите в источниках, которым доверяете.
Когда говорят «самое эффективное» всегда хочется поинтересоваться: «С чем и как сравнивали?». И это я не про обсуждаемые алгоритмы.
Нет не буду. Вы правы в том, что язык математики не зря был изобретён. Возражу в том, что перевод нормального математического языка в скобочную (инфиксную) запись, что в запись ОПН одинаков по сложности. Всё же ОПН много сложнее.
Возможно. Однако, на настоящий момент это ограничивается средствами ввода и передачи данных. Ведь глядя на математическую формулу вы сразу видите только структуру (образ формулы, катринку), причём многострочную, потом выделяете наиболее значимые фрагменты и лишь затем начинаете переходить к конкретным расчётам по приоритетам. То есть, насколько я понял, Вы предлагаете решить задачу прямой и обратной трансформации образов математических формул «на лету». И ввести это в стандарт.
Первая задача даже менее сложна чем вторая. Так что если по первой уже существуют конкретные решения, то вторя, по моему мнению, будет решена не скоро.
В целом, по высказанным вами соображениям согласен. Негоже терять наработанные цивилизационные, не побоюсь этого слова, решения, к которым относится и язык математики.
Да.
Чтобы понимали наличие альтернатив и разных подходов. Плохо когда все дуют в одну дуду. ограничивает возможности развития.
Во-первых, что выигрывает это ещё вопрос. Посимвольный разбор с разветвлённой логикой достаточно затратен сам по себе. Так что пока ещё бабушка надвое сказала.
Во-вторых, задачи разные и преимущество в одних может оказаться недостатком в других. Поэтому наличие разных инструментов повышает уровень свободы разработчика.
В-третьих, пока не было ОПН — не было и проектов с использованием данной нотации. Но всё течёт, всё изменяется.
Что интереснее это индивидуально. А вот полезнее знать где и что применить, причём независимо от текущей моды или коронки «так принято».
Эх, хорошее время… Кстати, и время поиска нового, а не только заучивания устоявшихся норм и правил.
Не знаю как у вас, а у нас учили, что если есть одинаковый вход и одинаковый выход, то разбираться надо со всем чёрным ящиком, а не с его частями.
Потому что в основе лежит именно запись (представление), в которую переформатируют инфиксную (привычную) запись, чтобы уже потом получить конечный результат. И тогда встаёт вопрос: «А надо ли корёжить исходное?» И при этом тратить учебное время на слом мозгов молодёжи. Для себя я ответил:«Не надо ни первое, ни второе.» Если ОПН была сделана во времена ограниченности инструментов управления кодом и железом, то при наличие на сегодня адекватных инструментов можно пожалеть молодёжь и не вбивать им в мозги старые дрожжи. Здесь рассматривались два ПОДХОДА к решению одной задачи.
Надеюсь я объяснил почему именно критика ОПН, а не конкретных алгоритмов и аппаратных ускорителей (акселераторов).
Пинг-Понг реализован на java. Перед этим я честно нарисовал алгоритм посимвольного разбора подобного разбору для ОПН и это мне сильно не понравилось прям на уровне алгоритма.
С вашего позволения, реализовывать ОПН не буду, задача не впечатляет.
Оставим это молодым. Подозреваю что кто-то это сделает без меня и, возможно, выложит результаты.
Лично для меня ОПН показался слишком перегруженным с точки зрения понимания и стало жалко молодёжь.
И ещё, я критикую не саму ОПН, а её безальтернативность в процессе обучения.
habrahabr.ru/post/351782/?reply_to=10720704#comment_10720704