Ну да, так и есть. На C++ там тривиальная ручная реализация BigInt без оптимизаций, которая очевидно уступает вылизанной реализации длинной арифметики в питоне (которая, кстати, написана на С). Так что там не сравнение питона с С++, а сравнение Сишной реализации длинной арифметики в библиотеке питона с кустарной ручной реализацией (ну с примесью самого языка для обвязки, но вообще непонятно, какая там пропорция).
Короче, бенчмарк очень спорный, и никаких выводов по нему делать нельзя.
Как-то странно. При расчете по формуле в 10М операций C++ в 177 раз быстрее CPython. А при подсчете до заданной точности - сравним. В чем дело? Ведь подсчет до заданной точности - это сколько-то заранее фиксированных итераций (хоть число и не записанных явно). Ведь формула одна и та же. Питон в обоих тестах работает примерно одинаковое время, а C++ в 170 раз медленнее. Почему?
Что там такое во втором тесте, чего нет в первом? Криво написанная длинная арифметика без стандартных оптимизаций, которые реализованы в движке длинной арифметики в питоне? Тогда сравнение некорректное. Надо в С++ использовать тоже стандартную вылизанную длинную арифметику вроде libgmp.
Ну вот он медленный там, где есть "тяжeлые части" (например циклы, for). Да, плохой архитектурой и алгоритмами вы замедлите работу в сотни раз, а не в 30, как при использовании питона вместо C++. Но 30 питоновских раз никуда не пропадают даже при выборе правильной архитектуры.
Вынос частей в С++ - это костыль, как раз вызванный абстрактным "Питон медленный". Если бы он не был абстрактно медленным, не нужно было бы ничего никуда выносить.
Ну нет, тут секретные данные спрятаны. Если не разбирать "флешку", то и не узнать, что там на самом деле еще скрытый раздел есть. А запароленый архив видно и он подозрительно большой, а при его запуске какой-то пароль просит. А если его переименовать во что-то еще, то видно будет битый файл.
Понял, спасибо. А вы, кстати, в курсе, что WebCodecs не гарантирует быстрый аппаратный путь? Он может работать и на процессоре. Это можно проверить через MediaCapabilities API? Хотя даже в этом случае это скорее всего все-равно будет быстрее WASM. Все-таки, там нативно все работает.
Тут та же история, что и с браузером, написанным роем агентов? Кое как иногда работающий набор из существующих библеотек для всего подряд с абсолютно не поддерживаемым кодом?
Пиар акция. Смотрите, наши ИИ уже заменяют целую компанию (нет). Увольняйте всех программистов и отдавайте весь зарплатный бюджет нам (но его не хватит).
Зачем вообще тащить ffmpeg в wasm, если оно уже фактически встроено во все браузеры? Или WebCodecs API вашим нуждам не хватило? Вы пишите, что используете его в каких-то случаях, но почему не во всех?
Статья отличная, все детально и по делу написано. Но есть несколько мелких замечаний:
Выражение (size + 7) / 8 — стандартный приём округления вверх при делении на 8: для хранения, скажем, 20 бит нужно 3 байта (24 бита), потому что 20 нацело на 8 не делится, а два байта дадут только 16. Именно поэтому мы добавляем 7 перед делением — гарантируем, что байтов будет ровно столько, сколько нужно для размещения всех битов, включая последний неполный байт.
Тут вы не совсем ясно объясняете. Лучше было бы написать почему это работает. Если size уже делиться на 8 на цело, то прибавление 7 не изменит результат, ведь /8 - это деление с округлением вниз. 7/8 отбросятся. Если же size не делится на 8, то там остаток хотя бы 1. прибавив к нему 7 мы точно соберем 8 до следующего делящегося на 8 и результат /8 будет на 1 больше, т.е. мы округлим вниз, а потом прибавим 1, получив округление вверх.
Еще, там где вы выводите формулы ложных срабатываний стоило бы добавить вывод экстремумов хотя бы под спойлером. Если уж такую детальную статью писать, стоит показать. все шаги.
Автор: Шуравин Александр, к. т. н., доцент, в IT более 20 лет.
Тут автор чванится своими регалиями. Фи. В интернете так не принято. Как показывает практика, уровень материала с такими подписями часто гораздо ниже чувства собственного величия автора.
Уровень сложности: Средний
Ну как же так, аж целый к.т.н. и всего-то средний материал? Что же вы так по-скромничали?
Ладно, перестаю сарказмировать. Ниже замечания по делу:
Для Senior-разработчика эти эксперименты — не просто упражнения.
Сеньёр-разработчику вся эта статья очевидна, как будто вы тут в столбик и на счетах считаете 11+31. И, внезапно, получаете 42. Но он это число еще читая, что вы собираетесь делать, в уме получает.
Это достаточно тривиальные алгоритмы, чтобы чисто логически вывести точное количество всех операций на отсортированном массиве а также матожидание и дисперсию для случайных данных. И никаких тестов и замеров не надо, чтобы убедиться, что в одном случае будет O(n), а в другом O(n^2).
> Неожиданный результат: вопреки теории, Selection Sort оказался быстрее Insertion Sort на случайных данных во всех замерах (примерно на 30–40%).
Почему вопреки? Оба дают асимптотику O(n^2) на случайных данных. Далее вопрос остается о константе. Константа зависит от аппаратной реализации и специфики языка. Ниже вы пишите:
Это объясняется тем, что Insertion Sort выполняет значительно больше операций записи в память (~n²/4 против ~n у Selection Sort)
Вы тут ошиблиcь. Selection Sort делает ~3n^2/4 операций записи: там записывается переменная min_idx, а так же j. А insertion Sort выполняет ~n^2/2 операций записи: переменная j и массив.
Так вот, Insertion Sort выполняет меньше операций и записи и сравнения, чем Selection Sort. Но работает медленнее, потому что ее работа не дружественна работе современных процессоров. В частности - к кэшу. В Selection Sort запись идет в локальную переменную и чтение неизменяемого (внутри вложенного цикла) массива, да еще и чтение идет подряд. Данные в массиве оказываются в кэше и чтение происходит легко и быстро. В Insertion Sort идет переписывание данных из массива в него же задом наперед, что вытесняет данные из кэша, даже если они там оказались. Поэтому там очень много обращений к памяти, что гораздо медленнее чтения из кэша.
Удивительно что вы за 20 лет в IT этого не заметили.
Вот это - как раз то, что Senior-разработчик должен иметь в голове.
Разумеется, нет. Это доказательство скорее всего опубликовано в какой-нибудь статье в каком-нибудь научном журнале за условный 1987 год. Прямо вместе с алгоритмом. Но в свободном доступе этой статьи нет, ибо копирасты требуют за доступ к ней деньги. Хотя может даже там доказательство в полном виде не приводят, ибо специалистам доказываемый факт и так довольно очевиден и статья написана для специалистов.
Эта тема не настолько интересна и популярна, чтобы доказательство растиражировали в каких-нибудь блогах и опубликовали в интернете, тем более на русском языке.
Обратите внимание, "нет в интернете" != "не существует в мире". Я нигде не утверждал, что я такой гениальный придумал не существующее ранее доказательство.
Тут оно работает, потому что живые клетки в стандартных правилах “жизни” не могут двигаться быстрее, чем на T/2 клеток за T шагов,
Нет же. Берем длинную палку длинной L шириной 1. За один шаг она станет очень длинной O. За следующий шаг появятся 2 вертикальные полосы еще правее и еще левее. В итоге через L шагов родятся клетки отстоящие на L шагов вправо и влево от центра палки (и что-то еще по середине).
Скорость света - 1 клетка/шаг.
поэтому в корне всегда достаточно пустого периметра.
Да. Но только если каждый под-блок этого расширенного с периметром поля считать отдельно. Если бы скорость света действительно была 1/2 клеток/шаг, то не надо было бы и расширять. Вот в примере выше в поле уже по краям достаточно пустого места.
Кстати, если вот как вы там обобщаете на окрестность p x p, то там скорость света вообще может быть p/2 и, похоже, периметр надо будет делать еще больше.
А вот такой вопрос возник, что вы по этому поводу думаете?
Вот есть у нас поле, допустим оно все помещается в 3^k x 3^k. Допустим мы хотим получить все поле через 3^n шагов (n >> k). Вроде бы легко - расширяем поле с ранга k до ранга n+1 пустыми полями. Потом выполняем один шаг и получаем точный размер поля 3^n x 3^n.
Но, скорость света в игре жизнь - 1. Через 3^n шагов изначальное поле 3^k x 3^k может расползтись до (3^n+3^k) x (3^n + 3^k), что больше поля 3^n x 3^n. Т.е. чтобы получить все поле надо будет сделать шаг параллельно на нескольких полях, так? Это очень похоже на первый шаг во время эволюции состояния.
Похоже, у вас именно так и делается - вы там корень помещаете в центр массива 5x5. Это удобно делать когда дерево нечетное, с центром, как у вас 3x3.
Как это делается для дерева 2x2 вообще? В вашей реализации выше я такой обработки не нашел. Кажется, можно поместить состояние в центр массива 3x3 и сделать 4 эволюции блоков 2x2 и получить 4 квадранта ответа.
И оффтопик, я тут поэксперементировал и выяснил, что если добавить в мапу состояний 0: [0, 0, 0, ... 0] для обозначения пустого поля любого размера, то это упрощает код (не надо отдельного make_empty), и немного сокращает количество состояний. Только вместо проверки, что у вас лист 0 или 1 надо помнить какого размера текущее поле.
Асимптотически там везде K^n для n шагов. К зависит от того, как выбирать дерево. Чем больше промежуточных шагов, тем больше K. Все они экспоненциальны, но асимптотически различимы.
Да и не только в этих департаментах "разрабатывающих новые технологии". И не только в гугле/яндексе. Прям олимпиадные задачи встречаются много где. Гораздо чаще, чем люди думают. Ошибочная оценка возникает потому, что такие задачи большинством просто не распознаются алгоритмическими вообще.
Вон, те же задачи на литкоде очень часто в виде "сделайте вот это". И можно тупо перевести с человеческого на язык программирования не очень задействуя мозг довольно часто.
У программистов обычно задача - запилить фичу, исправить баг. Они в голове состоявляют план "вот надо сделать вот так и так" и делают наивное медленное тупое решение, или вообще думают "а не, так не получится сделать, давайте поменяем фичу". Перед ними не стоит алгоритмической задачи, они ее придумывают уже как решение и даже не задумываются, что тут, оказывается, надо еще что-то решать и можно эти ваши алгоритмы использовать.
Вот тут не соглашусь. Олимпиады - это не собраться раз в несколько месяцев на 5 часов, порешать задачи и все. Это надо месяцами учить разные темы. Это надо тренироваться - решать задачи почти каждый день. Это концентрация на одной теме месяцами а то и годами.
Ну да, так и есть. На C++ там тривиальная ручная реализация BigInt без оптимизаций, которая очевидно уступает вылизанной реализации длинной арифметики в питоне (которая, кстати, написана на С). Так что там не сравнение питона с С++, а сравнение Сишной реализации длинной арифметики в библиотеке питона с кустарной ручной реализацией (ну с примесью самого языка для обвязки, но вообще непонятно, какая там пропорция).
Короче, бенчмарк очень спорный, и никаких выводов по нему делать нельзя.
В тех сорсах только сортировка, числа по ней вопросов не вызывают. Вычисления Пи там нигде нет.
Как-то странно. При расчете по формуле в 10М операций C++ в 177 раз быстрее CPython. А при подсчете до заданной точности - сравним. В чем дело? Ведь подсчет до заданной точности - это сколько-то заранее фиксированных итераций (хоть число и не записанных явно). Ведь формула одна и та же. Питон в обоих тестах работает примерно одинаковое время, а C++ в 170 раз медленнее. Почему?
Что там такое во втором тесте, чего нет в первом? Криво написанная длинная арифметика без стандартных оптимизаций, которые реализованы в движке длинной арифметики в питоне? Тогда сравнение некорректное. Надо в С++ использовать тоже стандартную вылизанную длинную арифметику вроде libgmp.
Ну вот он медленный там, где есть "тяжeлые части" (например циклы, for). Да, плохой архитектурой и алгоритмами вы замедлите работу в сотни раз, а не в 30, как при использовании питона вместо C++. Но 30 питоновских раз никуда не пропадают даже при выборе правильной архитектуры.
Вынос частей в С++ - это костыль, как раз вызванный абстрактным "Питон медленный". Если бы он не был абстрактно медленным, не нужно было бы ничего никуда выносить.
Ну нет, тут секретные данные спрятаны. Если не разбирать "флешку", то и не узнать, что там на самом деле еще скрытый раздел есть. А запароленый архив видно и он подозрительно большой, а при его запуске какой-то пароль просит. А если его переименовать во что-то еще, то видно будет битый файл.
А у продавцов лопат эти "обязательства" в отчетах уже как будущая или состоявшаяся прибыль фигурируют, да?
Понял, спасибо. А вы, кстати, в курсе, что WebCodecs не гарантирует быстрый аппаратный путь? Он может работать и на процессоре. Это можно проверить через MediaCapabilities API? Хотя даже в этом случае это скорее всего все-равно будет быстрее WASM. Все-таки, там нативно все работает.
Тут та же история, что и с браузером, написанным роем агентов? Кое как иногда работающий набор из существующих библеотек для всего подряд с абсолютно не поддерживаемым кодом?
Пиар акция. Смотрите, наши ИИ уже заменяют целую компанию (нет). Увольняйте всех программистов и отдавайте весь зарплатный бюджет нам (но его не хватит).
Зачем вообще тащить ffmpeg в wasm, если оно уже фактически встроено во все браузеры? Или WebCodecs API вашим нуждам не хватило? Вы пишите, что используете его в каких-то случаях, но почему не во всех?
Статья отличная, все детально и по делу написано. Но есть несколько мелких замечаний:
Тут вы не совсем ясно объясняете. Лучше было бы написать почему это работает. Если size уже делиться на 8 на цело, то прибавление 7 не изменит результат, ведь /8 - это деление с округлением вниз. 7/8 отбросятся. Если же size не делится на 8, то там остаток хотя бы 1. прибавив к нему 7 мы точно соберем 8 до следующего делящегося на 8 и результат /8 будет на 1 больше, т.е. мы округлим вниз, а потом прибавим 1, получив округление вверх.
Еще, там где вы выводите формулы ложных срабатываний стоило бы добавить вывод экстремумов хотя бы под спойлером. Если уж такую детальную статью писать, стоит показать. все шаги.
Удивительно, но за это американская SEC сажает: https://www.bbc.com/news/articles/c052yv259jvo Хоть там никакие акции и ценные бумаги даже рядом не валялись.
Возможно совсем скоро и европейские регуляторы подтянутся.
Тут автор чванится своими регалиями. Фи. В интернете так не принято. Как показывает практика, уровень материала с такими подписями часто гораздо ниже чувства собственного величия автора.
Ну как же так, аж целый к.т.н. и всего-то средний материал? Что же вы так по-скромничали?
Ладно, перестаю сарказмировать. Ниже замечания по делу:
Сеньёр-разработчику вся эта статья очевидна, как будто вы тут в столбик и на счетах считаете 11+31. И, внезапно, получаете 42. Но он это число еще читая, что вы собираетесь делать, в уме получает.
Это достаточно тривиальные алгоритмы, чтобы чисто логически вывести точное количество всех операций на отсортированном массиве а также матожидание и дисперсию для случайных данных. И никаких тестов и замеров не надо, чтобы убедиться, что в одном случае будет O(n), а в другом O(n^2).
> Неожиданный результат: вопреки теории, Selection Sort оказался быстрее Insertion Sort на случайных данных во всех замерах (примерно на 30–40%).
Почему вопреки? Оба дают асимптотику O(n^2) на случайных данных. Далее вопрос остается о константе. Константа зависит от аппаратной реализации и специфики языка. Ниже вы пишите:
Вы тут ошиблиcь. Selection Sort делает ~3n^2/4 операций записи: там записывается переменная min_idx, а так же j. А insertion Sort выполняет ~n^2/2 операций записи: переменная j и массив.
Так вот, Insertion Sort выполняет меньше операций и записи и сравнения, чем Selection Sort. Но работает медленнее, потому что ее работа не дружественна работе современных процессоров. В частности - к кэшу. В Selection Sort запись идет в локальную переменную и чтение неизменяемого (внутри вложенного цикла) массива, да еще и чтение идет подряд. Данные в массиве оказываются в кэше и чтение происходит легко и быстро. В Insertion Sort идет переписывание данных из массива в него же задом наперед, что вытесняет данные из кэша, даже если они там оказались. Поэтому там очень много обращений к памяти, что гораздо медленнее чтения из кэша.
Удивительно что вы за 20 лет в IT этого не заметили.
Вот это - как раз то, что Senior-разработчик должен иметь в голове.
Разумеется, нет. Это доказательство скорее всего опубликовано в какой-нибудь статье в каком-нибудь научном журнале за условный 1987 год. Прямо вместе с алгоритмом. Но в свободном доступе этой статьи нет, ибо копирасты требуют за доступ к ней деньги. Хотя может даже там доказательство в полном виде не приводят, ибо специалистам доказываемый факт и так довольно очевиден и статья написана для специалистов.
Эта тема не настолько интересна и популярна, чтобы доказательство растиражировали в каких-нибудь блогах и опубликовали в интернете, тем более на русском языке.
Обратите внимание, "нет в интернете" != "не существует в мире". Я нигде не утверждал, что я такой гениальный придумал не существующее ранее доказательство.
Да, согласен.
Нет же. Берем длинную палку длинной L шириной 1. За один шаг она станет очень длинной O. За следующий шаг появятся 2 вертикальные полосы еще правее и еще левее. В итоге через L шагов родятся клетки отстоящие на L шагов вправо и влево от центра палки (и что-то еще по середине).
Скорость света - 1 клетка/шаг.
Да. Но только если каждый под-блок этого расширенного с периметром поля считать отдельно. Если бы скорость света действительно была 1/2 клеток/шаг, то не надо было бы и расширять. Вот в примере выше в поле уже по краям достаточно пустого места.
Кстати, если вот как вы там обобщаете на окрестность p x p, то там скорость света вообще может быть p/2 и, похоже, периметр надо будет делать еще больше.
Код я потом скину, еще не отдебажил.
А вот такой вопрос возник, что вы по этому поводу думаете?
Вот есть у нас поле, допустим оно все помещается в 3^k x 3^k. Допустим мы хотим получить все поле через 3^n шагов (n >> k). Вроде бы легко - расширяем поле с ранга k до ранга n+1 пустыми полями. Потом выполняем один шаг и получаем точный размер поля 3^n x 3^n.
Но, скорость света в игре жизнь - 1. Через 3^n шагов изначальное поле 3^k x 3^k может расползтись до (3^n+3^k) x (3^n + 3^k), что больше поля 3^n x 3^n. Т.е. чтобы получить все поле надо будет сделать шаг параллельно на нескольких полях, так? Это очень похоже на первый шаг во время эволюции состояния.
Похоже, у вас именно так и делается - вы там корень помещаете в центр массива 5x5. Это удобно делать когда дерево нечетное, с центром, как у вас 3x3.
Как это делается для дерева 2x2 вообще? В вашей реализации выше я такой обработки не нашел. Кажется, можно поместить состояние в центр массива 3x3 и сделать 4 эволюции блоков 2x2 и получить 4 квадранта ответа.
И оффтопик, я тут поэксперементировал и выяснил, что если добавить в мапу состояний
0: [0, 0, 0, ... 0]для обозначения пустого поля любого размера, то это упрощает код (не надо отдельного make_empty), и немного сокращает количество состояний. Только вместо проверки, что у вас лист 0 или 1 надо помнить какого размера текущее поле.Асимптотически там везде K^n для n шагов. К зависит от того, как выбирать дерево. Чем больше промежуточных шагов, тем больше K. Все они экспоненциальны, но асимптотически различимы.
Да и не только в этих департаментах "разрабатывающих новые технологии". И не только в гугле/яндексе. Прям олимпиадные задачи встречаются много где. Гораздо чаще, чем люди думают. Ошибочная оценка возникает потому, что такие задачи большинством просто не распознаются алгоритмическими вообще.
Вон, те же задачи на литкоде очень часто в виде "сделайте вот это". И можно тупо перевести с человеческого на язык программирования не очень задействуя мозг довольно часто.
У программистов обычно задача - запилить фичу, исправить баг. Они в голове состоявляют план "вот надо сделать вот так и так" и делают наивное медленное тупое решение, или вообще думают "а не, так не получится сделать, давайте поменяем фичу". Перед ними не стоит алгоритмической задачи, они ее придумывают уже как решение и даже не задумываются, что тут, оказывается, надо еще что-то решать и можно эти ваши алгоритмы использовать.
Вот тут не соглашусь. Олимпиады - это не собраться раз в несколько месяцев на 5 часов, порешать задачи и все. Это надо месяцами учить разные темы. Это надо тренироваться - решать задачи почти каждый день. Это концентрация на одной теме месяцами а то и годами.