Вы имеете в виду врехнюю границу промежуточного результата? А зачем? Отсекать количество вариантов тут не надо, вариантов не так много, чтобы не перебрать все. Можно ли доказать, что среди экстремально больших промежуточных результатов не может быть искомого? Мне кажется, что можно, не так много действий могут приводить к чему-то большому.
Полный перебор (забив на все переполнения и неточности, поэтому и не полностью корректный как доказательство) в даблах на домашнем компе у меня занял 40 секунд. Длинная арифметика сразу увеличивает время в разы (что ерунда для глобальной задачи), но от точности и непредставимости результатов деления не спасает. 1/3 и в длинной арифметике непредставима, а sqrt(2) и в виде рациональных дробей. Я вижу проблему только с резким ростом вычислительной погрешности в операциях вроде 100500 ^ sqrt(3). Но для одного конкретного числа 10958 таких ситуаций мало, их можно и по одной (или классами) руками рассмотреть.
По крайней мере у меня получалось рассмотреть все лесенки из степеней, чтобы показать, что там 10958 точно нет. Чего я не рассмотрел, так это проблемы вычислительной погрешности, которые описал выше.
И да, я считаю (и это было в оригинале) что задача поставлена в действительных числах, не выходя в комплексную плоскость.
Забавно, а я давал задачку на поиск разложения 10958 студентам в качестве практики по программированию. Понятно, что не фундаментальное исследование, а просто перебор всех возможных вариантов, забив на сверхбольшие числа и всевозможные неточности double. А тут из этой задачи современную проблему математики создают.
Мне казалось, что отсутствие разложения уже доказано, ведь несложно показать, что среди лесенок из степеней этого числа нет, а всё остальное перебирается в лоб.
Хотел было возразить, что нет, C++ нормальный первый язык. Я с него начал и продолжаю работать на нём. Но потом понял, что на брейнфаке я тоже писал немало и даже никнейм на хабре к нему отсылает. А я считал себя нормальным человеком :(((
Пулинг, то есть объединение проб нескольких человек в один тест вполне себе используется. Ссылок под рукой нет, но должно гуглиться. Если хоть один человек в группе болен, то тест будет положительный и всех надо отправлять не подтверждение индивидуальным тестом.
Более сложные схемы, типа той, что в статье слишком ненадёжны. Сам по себе тест не 100% точный + ошибки лаборантов и неверный тест уже не у одного человека, а у всей группы, причём как ложноположительный (что терпимо), так и ложноотрицательный, что опасно.
Я сам думал про такую схему ещё в начале эпидемии, думаю, что не только я. Но в реальности малоприменимо.
Я видел, но это не совсем то же самое. Без поддержки языка статический анализ так и останется рекомендательным инструментом. В том же D понадобился live, а ещё были scope и return scope(hello DIP1000). Пока что это выглядит так себе, но я верю, что можно найти такое решение, которое будет понятнее и проще, и которое можно внедрить в C++.
Несмотря на то, как плохо выглядит вклинивание системы владения указателей в D, мне это очень нравится. Да, в расте всё выглядит органичнее и консистентнее, зато практика внедрения владения в язык, где это изначально не задумано, очень полезна для остальных. Rust всё же инопланетныйспецифичный язык, а тут есть шанс принести все его плюсы в более привычное окружение. И я сейчас даже не про D — всё это потенциально переносимо в другие языки, в первую очередь в C++.
С посылом статьи в целом согласен. Я учился программировать на BASIC на спектруме во времена выхода пентиумов 3 и 4, то есть это было не актуально совсем. Ни разу на практике не пригодились те знания, но навык программирования от языка зависит мало, и он спокойно был перенесён сначала на Паскаль, C, а потом и C++.
К списку полезного в вузе я бы добавил теоретическую информатику: алгоритмы, конечные автоматы, машина Тьюринга, методы оптимизации и всякие P = NP. Не то чтобы оно было нужно постоянно, детали все давно забыты, но знание о принципиальной возможности или невозможности решения задачи весьма полезны. Помогает не биться линий раз в стену невозможного и не сдаваться перед преодолимыми сложностями.
Каким образом теряется RAII или раскрутка стека? Если раскрутка как-то и страдает из-за использования map и then, то деструкторы не перестают вызываться. Гарантии те же и даже больше, потому что больше никто не может вклиниться в неудобные места вроде вычисления аргументов функций. Писать expected safe код проще, чем exception safe.
Что же вы все так набросились на статью! Да, не идеал, ради рекламы Expected много написано, но озвучить эту сторону тоже надо было.
Не надо забывать, что исключения совсем не zero cost даже, когда не бросаются, иначе бы noexcept в стандарт не тащили. Кроме затрат непосредственно на секцию try, которая в реализации SJLJ может быть очень недешёвой, есть ещё и косвенные на сломанные оптимизации. Сейчас с ходу не найду доклад, но точно был про внутренности llvm, где демонстрировалось, какие именно оптимизации ломаются.
Кроме того есть ещё разбухание бинаря (привет dwarf), -fno-exceptions и прочие интересные случаи.
Возможно, я чего-то о нём не знаю, но как без возможности воспроизвести проблему тестом, воспользоватся valgrind'ом? Когда есть, что запустить, чтобы воспроизвести утечку, valgrind гораздо лучше, но что делать, когда она никак не воспроизводится? Что он может сделать с одним лишь дампом?
Понятно, что посыл не в том, но всё же никто бы не стал в первый же год добавлять новый день. В реальности остались бы на старом календаре, а потом бы уже постепенно перешли, когда подготовили и софт и людей. Церковь вон живёт с юлианским календарём и никаких проблем не имеет.
Да, невнимательно посмотрел на флаги. Дописал в P.S.
Протестировал у себя, получил похожие цифры, а потом уже удвоился за счёт проверок границ. Даже не задумывался, что можно бенчмаркать DMD, на автомате взял ldc. Результаты у меня:
C gcc 8.3: Finished in 0.696s
D ldc2 1.10.0: Finished in 0.638s
Есть разброс, но в целом D версия чуть быстрее.
Уже прокомментировали про C++, добавлю то же самое про D. Достаточно добавить флажок boundscheck=off и получить удвоение скорости. Размен безопасности на скорость, которую вы сделали в хаскеле.
P.S. Забыл про главное, компилятор ldc2, а не референсный DMD.
Простите за скептицизм, но уверены, что речь не о планетах (Венера, Юпитер)? Они в разы ярче любой звезды, но найти на дневном небе даже их почти нереально, хотя потом уже хорошо видно. У меня получалось найти биноклем и только потом глазами по очень точному направлению. Может быть в горах с этим получше, яркость неба, теоретически, чуть меньше, контрастность выше, но всё равно с трудом верится.
Наверное уже сто раз писали, но почему каждый год конкурс в настолько неудобное время? То в разгар новогодних праздников, то как сейчас финал под ёлочкой. Что для студентов, что для работающих, конец года — самое напряжное время — зачёты, дедлайны и тд. Почему не весной? Чтобы и середина семестра, и не отпускной сезон, и не праздники.
Уже который год очень хочу нормально поучаствовать, но катастрофически не хватает времени и сил.
И всё равно спасибо организаторам. Хоть как-нибудь но постараюсь поучаствовать.
Спасибо за статью. Тоже использую Ragel, очень неожиданно и приятно видеть, что ещё кто-то его тоже использует.
У вас не самая простая для рагелевской грамматики задача — парные кавычки. Обычно всё проще и не требует ручных fcall и fret — больше описаний грамматики, меньше внутренностей.
Про понятнее или нет — спорный вопрос. Безусловно, порог входа в него высокий. Понять написанное в общих чертах можно и без доки, но чтобы менять придётся освоить весь pdf документации. Зато потом начинаешь понимать, что это самый нормальный способ парсинга любого текстового формата. Поддерживаемость и возможность добавления фич по сравнению с ручным разбором кодом даже с регекспами и рядом не стояла. Есть опыт поддержки парсера, написанного полностью руками и другого на рагеле, написанных другими людьми — небо и земля. В первом поправить логику ничего не сломав практически невозможно, со вторым делай, что хочешь.
И ещё хотел бы отметить безумную производительность. Есть разные режимы генерации, но тот, что через goto, создаёт нечто, что обогнать в бенчмарках руками написанным кодом не получается. Так что, если нужно распарсить текстовый протокол, Ragel — одновременно удобное и очень высокопроизводительное решение.
Полный перебор (забив на все переполнения и неточности, поэтому и не полностью корректный как доказательство) в даблах на домашнем компе у меня занял 40 секунд. Длинная арифметика сразу увеличивает время в разы (что ерунда для глобальной задачи), но от точности и непредставимости результатов деления не спасает. 1/3 и в длинной арифметике непредставима, а sqrt(2) и в виде рациональных дробей. Я вижу проблему только с резким ростом вычислительной погрешности в операциях вроде 100500 ^ sqrt(3). Но для одного конкретного числа 10958 таких ситуаций мало, их можно и по одной (или классами) руками рассмотреть.
По крайней мере у меня получалось рассмотреть все лесенки из степеней, чтобы показать, что там 10958 точно нет. Чего я не рассмотрел, так это проблемы вычислительной погрешности, которые описал выше.
И да, я считаю (и это было в оригинале) что задача поставлена в действительных числах, не выходя в комплексную плоскость.
Мне казалось, что отсутствие разложения уже доказано, ведь несложно показать, что среди лесенок из степеней этого числа нет, а всё остальное перебирается в лоб.
Более сложные схемы, типа той, что в статье слишком ненадёжны. Сам по себе тест не 100% точный + ошибки лаборантов и неверный тест уже не у одного человека, а у всей группы, причём как ложноположительный (что терпимо), так и ложноотрицательный, что опасно.
Я сам думал про такую схему ещё в начале эпидемии, думаю, что не только я. Но в реальности малоприменимо.
инопланетныйспецифичный язык, а тут есть шанс принести все его плюсы в более привычное окружение. И я сейчас даже не про D — всё это потенциально переносимо в другие языки, в первую очередь в C++.К списку полезного в вузе я бы добавил теоретическую информатику: алгоритмы, конечные автоматы, машина Тьюринга, методы оптимизации и всякие P = NP. Не то чтобы оно было нужно постоянно, детали все давно забыты, но знание о принципиальной возможности или невозможности решения задачи весьма полезны. Помогает не биться линий раз в стену невозможного и не сдаваться перед преодолимыми сложностями.
Не надо забывать, что исключения совсем не zero cost даже, когда не бросаются, иначе бы noexcept в стандарт не тащили. Кроме затрат непосредственно на секцию try, которая в реализации SJLJ может быть очень недешёвой, есть ещё и косвенные на сломанные оптимизации. Сейчас с ходу не найду доклад, но точно был про внутренности llvm, где демонстрировалось, какие именно оптимизации ломаются.
Кроме того есть ещё разбухание бинаря (привет dwarf), -fno-exceptions и прочие интересные случаи.
Протестировал у себя, получил похожие цифры, а потом уже удвоился за счёт проверок границ. Даже не задумывался, что можно бенчмаркать DMD, на автомате взял ldc. Результаты у меня:
C gcc 8.3: Finished in 0.696s
D ldc2 1.10.0: Finished in 0.638s
Есть разброс, но в целом D версия чуть быстрее.
P.S. Забыл про главное, компилятор ldc2, а не референсный DMD.
Это должно быть здесь. Доклад Андрея Александреску про алгоритмическую сложность и реальность на CppCon 2019.
Уже который год очень хочу нормально поучаствовать, но катастрофически не хватает времени и сил.
И всё равно спасибо организаторам. Хоть как-нибудь но постараюсь поучаствовать.
У вас не самая простая для рагелевской грамматики задача — парные кавычки. Обычно всё проще и не требует ручных fcall и fret — больше описаний грамматики, меньше внутренностей.
Про понятнее или нет — спорный вопрос. Безусловно, порог входа в него высокий. Понять написанное в общих чертах можно и без доки, но чтобы менять придётся освоить весь pdf документации. Зато потом начинаешь понимать, что это самый нормальный способ парсинга любого текстового формата. Поддерживаемость и возможность добавления фич по сравнению с ручным разбором кодом даже с регекспами и рядом не стояла. Есть опыт поддержки парсера, написанного полностью руками и другого на рагеле, написанных другими людьми — небо и земля. В первом поправить логику ничего не сломав практически невозможно, со вторым делай, что хочешь.
И ещё хотел бы отметить безумную производительность. Есть разные режимы генерации, но тот, что через goto, создаёт нечто, что обогнать в бенчмарках руками написанным кодом не получается. Так что, если нужно распарсить текстовый протокол, Ragel — одновременно удобное и очень высокопроизводительное решение.