Хотелось бы поинтересоваться, на основе чего был сделан вывод, что то, что вы называете «научным подходом», вообще кому либо нужно в программировании? Языки проектируются с двумя приоритетами: уметь решать поставленные перед ними задачи и быть удобными для их пользователей. А вот Ваши «доказательства» и «объяснения» — они то и не нужны никому от слова «совсем».
В идеале должно быть всего 2 низкоуровневых языка и 3-4 высокоуровневых, построенных на их основе.
Интересно, откуда такие цифры?
Факты:
Относятся к реальному миру, а не к программированию.
несколько принципов:
Похожи на смесь Coding Style Guide и какого-то очередного шаблона проектирования, которые вы так ненавидите.
Гипотеза:
Основана на том, что в программировании самым лучшим кодом является самый короткий, а это не так.
P. S. Почему в качестве ЯП для «доказательства гипотезы» выбрана Java? Она ведь полностью объектно-ориентирована, а судя по Вашей статье, хуже ООП может быть только ФП)
про «немедленно включить в программу» — это Вы уже сами придумали
«Так почему же студентов до сих пор мучают всякой хренью, придуманой в незапамятные времена?» — это не призыв? Или Вы, как любой уважающий себя диванный эксперт, только недовольство выражаете, а прямых предложений сделать не способны?
Обсуждение говорит об обратном.
Обсуждение говорит о том, что ее сложно вдавить лично Вам.
Я нигде не предлагал перечеркнуть, нигде не предлагал «вместо».
Читали предпоследнее предложение своей статьи? На всякий случай продублирую: «Так почему же студентов до сих пор мучают всякой хренью, придуманой в незапамятные времена?» И это после того, как вы предложили алгоритм, эффективность которого можете аргументировать только в «сфере обучения», и то лишь своим субъективным мнением.
Напрягло не просто так, а потому, что перед этим я поразбирался с ОПН.
И, как видно из комментариев, до сих пор с ней не разобрались. То есть всем ВУЗам мира нужно немедленно включить в свою программу алгоритм, придуманный человеком, который ниасилил ОПН?
Надо ли его вдавливать в молодые мозги?
Никто никуда ОПН не вдавливает, она сама течет куда хочет, ибо проблемы с ее пониманием возникают лишь у Вас.
И на нём десятки статей С ОПН и ни одной реальной альтернативы (рекурсию и деревья не считаем).
У любого понятия нет альтернатив, если не считать его альтернатив.
Это Вы правильно подметили. А еще не учтена реальная архитектура компьютерных систем.
Раз уж Вы так подробно сравнили количество логических обращений к символу строки, почему бы заодно не сравнить О-сложность алгоритмов? А еще можно наконец то сравнить время выполнения.
Циолковский был первым в своем деле, а Вы пришли в подробно изученную область и предложили перечеркнуть работу признанных ученых и вместо нее использовать самый примитивный подход, который можно представить. Так что Ваши высказывания сравнимы не с работами Циолковского, а с предложением Илону Маску забросить этот его SpaceX и вместо этого начать писать статьи в стиле Цилковского.
Рекурсивный спуск замечательно подходит в этом случае, и в понимании очень прост ( хотя это конечно субъективно ). И, между прочим, именно спуск, а не ОПН, был первым подходом, примененным мной для решения данной задачи.
Отговорок достаточно, но это не делает Вашу статью законченной. Любая статья, которая выдвигает новый алгоритм для решения некоторой задачи, обязательно должна содержать реализацию алгоритма и сравнение его с существующими аналогами, при чем не только по такой субъективной характеристике, как порог вхождения, а и по скорости, потребляемой памяти, портируемости, и т. д.
Если Вас не связывает NDA или что-то в этом роде, то выложить имеющуюся реализацию алгоритма в Интернет может помешать либо отсутствие Интернета, либо отсутствие реализации.
каждый операнд участвует в процессе три раза:1. инициализация переменной 2. помещение в стек 3. извлечение из стека для операции. То есть, если отбросить сами операции, то получаем три прохода по одному операнду
Эти действия совершаются не на этапе парсинга выражения, а на этапе вычисления, так что машина работает уже не со строками или регулярными выражениями, а с числами, которые представлены в удобном ей виде. Так что это три элементарных присваивания, которые выполнятся быстрее чем Ваш «очень быстрый» поиск по маске.
Основное применение — интерпретаторы и компиляторы.
Это снимает многие вопросы к дискуссии по этой статье. Спасибо.
Хотелось бы поинтересоваться, в какой практической ситуации имеет смысл применять Пинг-Понг.
безальтернативность решения ОПН в информационной сфере
прочитал с десяток, отбросив рекурсию и деревья. Только ОПН
А чем Вам рекурсия и деревья не альтернатива ОПН? Ваша вера в теории заговора про ОПН базируется лишь на том, что Вы отбросили все остальные найденные Вами решения.
Предлагаю оставить вопрос эффективности в покое. Мне достаточно что алгоритм прост и понятен.
Дело в том, что когда доходит до реальных проектов, приоритеты ставятся противоположные, потому что лишнее время, потраченное программистом на то, что бы понять алгоритм — ничто по сравнению с суммарным временем, которое потратят пользователи на ожидание результатов от программы. Кстати, в данном случае оно окупится еще на этапе разработки, так как на реализацию Пинг-Понга уйдет намного больше времени, чем на ОПН ( ИМХО ).
Вряд ли мы оба сейчас готовы квалифицированно ответить на такое однозначно.
Я не позиционирую себя как гуру HPC, но я хотя бы привел аргументы, почему ОПН оптимальнее чем Пинг-Понг.
Удивили. Алгоритм на ОПН — это ВСЕГДА посимвольный разбор.
Согласен, выразил немного не то что хотел. Но опять же, один посимвольный разбор в ОПН против множества тестов по регулярному выражению в Пинг-Понге, каждый из которых включает в себя посимвольный проход.
лучше стоит восстановить информацию по замене фрагментов в строке.
Не совсем понял, что имелось в виду. Если я правильно понимаю таблицу с описанием алгоритма, после каждого теста по regex'пу выполняется замена обрабатываемого фрагмента строки на результат, что ведет к копированию всего хвоста строки. Если конечно длина результата не совпала с длиной фрагмента, что маловероятно.
Когда говорят «самое эффективное» всегда хочется поинтересоваться: «С чем и как сравнивали?».
Серьезным подходом считается написать реализации обоих подходов и сравнить. И при разработке новых алгоритмов всегда стоит сравнивать их с существующими аналогами.
задачи разные и преимущество в одних может оказаться недостатком в других
ИМХО единственное достоинство Пинг-Понга — это его простота ( при чем только в понимании, в реализации не все так просто ). И я не считаю, что простота должна быть главным аргументом для выбора алгоритма.
Во-первых, что выигрывает это ещё вопрос. Посимвольный разбор с разветвлённой логикой достаточно затратен сам по себе.
Редкие случаи посимвольного разбора в ОПН в Пинг-Понге заменяются на тест регулярными выражениями по любому поводу. Количество проходов по исходной строке может быть очень большим — и это против одного прохода в ОПН. Пункт 'Замена фрагмента "(...)"' тянет за собой столько же копирований памяти. У меня нет реальных цифр, но я думаю, что Пинг-Понг немало проиграет ОПН в производительности.
Кстати, и время поиска нового, а не только заучивания устоявшихся норм и правил.
причём независимо от текущей моды или коронки «так принято».
Никто ничего не заучивает — все просто пользуются самым эффективным решением.
Ну и как-то это было скорее против засилия ОПН в учебном процессе.
Насколько я понял, алгоритм, предложенный в статье является формализацией подхода, который используется человеком. Зачем же рассказывать студентам то, что они умеют и практикуют со школьных времен? Не лучше ли рассказать про ОПН, которая выигрывает у Пинг-Понга в производительности и используется в реальных проектах?
Вот представьте, что лектору нужно рассказать, как найти подстроку в строке. Можно предложить алгоритм перебором за O(N^2), до которого любой студент и сам додумается, а можно рассказать о чем то вроде алгоритма Кнута-Морриса-Пратта, который не стыдно использовать в продакшене. Что по Вашему полезнее/интереснее? Лично мне второе, говорю Вам как студент))
Интересно, откуда такие цифры?
Относятся к реальному миру, а не к программированию.
Похожи на смесь Coding Style Guide и какого-то очередного шаблона проектирования, которые вы так ненавидите.
Основана на том, что в программировании самым лучшим кодом является самый короткий, а это не так.
P. S. Почему в качестве ЯП для «доказательства гипотезы» выбрана Java? Она ведь полностью объектно-ориентирована, а судя по Вашей статье, хуже ООП может быть только ФП)
«Так почему же студентов до сих пор мучают всякой хренью, придуманой в незапамятные времена?» — это не призыв? Или Вы, как любой уважающий себя диванный эксперт, только недовольство выражаете, а прямых предложений сделать не способны?
Обсуждение говорит о том, что ее сложно вдавить лично Вам.
Читали предпоследнее предложение своей статьи? На всякий случай продублирую: «Так почему же студентов до сих пор мучают всякой хренью, придуманой в незапамятные времена?» И это после того, как вы предложили алгоритм, эффективность которого можете аргументировать только в «сфере обучения», и то лишь своим субъективным мнением.
И, как видно из комментариев, до сих пор с ней не разобрались. То есть всем ВУЗам мира нужно немедленно включить в свою программу алгоритм, придуманный человеком, который ниасилил ОПН?
Никто никуда ОПН не вдавливает, она сама течет куда хочет, ибо проблемы с ее пониманием возникают лишь у Вас.
У любого понятия нет альтернатив, если не считать его альтернатив.
Это Вы правильно подметили. А еще не учтена реальная архитектура компьютерных систем.
Раз уж Вы так подробно сравнили количество логических обращений к символу строки, почему бы заодно не сравнить О-сложность алгоритмов? А еще можно наконец то сравнить время выполнения.
Несложно реализовать и в ОПН, и в деревьях.
Не очень понимаю, о чем вы, но звучит как задача, которая решается деревьями.
Но если в будущем он неприменим, зачем тратить время школьника?
Это неправильная стратегия разработки алгоритмов. Алгоритмы нужно придумывать не для того, что бы они были, а для решения реальных задач.
Эти действия совершаются не на этапе парсинга выражения, а на этапе вычисления, так что машина работает уже не со строками или регулярными выражениями, а с числами, которые представлены в удобном ей виде. Так что это три элементарных присваивания, которые выполнятся быстрее чем Ваш «очень быстрый» поиск по маске.
Хотелось бы поинтересоваться, в какой практической ситуации имеет смысл применять Пинг-Понг.
А чем Вам рекурсия и деревья не альтернатива ОПН? Ваша вера в теории заговора про ОПН базируется лишь на том, что Вы отбросили все остальные найденные Вами решения.
Дело в том, что когда доходит до реальных проектов, приоритеты ставятся противоположные, потому что лишнее время, потраченное программистом на то, что бы понять алгоритм — ничто по сравнению с суммарным временем, которое потратят пользователи на ожидание результатов от программы. Кстати, в данном случае оно окупится еще на этапе разработки, так как на реализацию Пинг-Понга уйдет намного больше времени, чем на ОПН ( ИМХО ).
Я не позиционирую себя как гуру HPC, но я хотя бы привел аргументы, почему ОПН оптимальнее чем Пинг-Понг.
Согласен, выразил немного не то что хотел. Но опять же, один посимвольный разбор в ОПН против множества тестов по регулярному выражению в Пинг-Понге, каждый из которых включает в себя посимвольный проход.
Не совсем понял, что имелось в виду. Если я правильно понимаю таблицу с описанием алгоритма, после каждого теста по regex'пу выполняется замена обрабатываемого фрагмента строки на результат, что ведет к копированию всего хвоста строки. Если конечно длина результата не совпала с длиной фрагмента, что маловероятно.
Серьезным подходом считается написать реализации обоих подходов и сравнить. И при разработке новых алгоритмов всегда стоит сравнивать их с существующими аналогами.
ИМХО единственное достоинство Пинг-Понга — это его простота ( при чем только в понимании, в реализации не все так просто ). И я не считаю, что простота должна быть главным аргументом для выбора алгоритма.
Редкие случаи посимвольного разбора в ОПН в Пинг-Понге заменяются на тест регулярными выражениями по любому поводу. Количество проходов по исходной строке может быть очень большим — и это против одного прохода в ОПН. Пункт 'Замена фрагмента "(...)"' тянет за собой столько же копирований памяти. У меня нет реальных цифр, но я думаю, что Пинг-Понг немало проиграет ОПН в производительности.
Никто ничего не заучивает — все просто пользуются самым эффективным решением.
Насколько я понял, алгоритм, предложенный в статье является формализацией подхода, который используется человеком. Зачем же рассказывать студентам то, что они умеют и практикуют со школьных времен? Не лучше ли рассказать про ОПН, которая выигрывает у Пинг-Понга в производительности и используется в реальных проектах?
Вот представьте, что лектору нужно рассказать, как найти подстроку в строке. Можно предложить алгоритм перебором за O(N^2), до которого любой студент и сам додумается, а можно рассказать о чем то вроде алгоритма Кнута-Морриса-Пратта, который не стыдно использовать в продакшене. Что по Вашему полезнее/интереснее? Лично мне второе, говорю Вам как студент))