Алгоритмическое программирование и промышленное - это совсем разные вещи и разные навыки
Зависит от области. В бигтехе вполне себе алгоритмическое программирование нужно. Я несколько статей на эту тему на хабре написал: встречаются самые настоящие литкодовские задачи. Конечно, перекладывания джесонов гораздо больше, но навыки нужны для самых сложных задач, с которыми вы столкнетесь. А перекладывание джейсонов - это тоже алгоритмическая задача, хоть и тривиальная. Принципиально ничем не отличается.
Неподдерживаемый код - это понятная привычка, вызванная из-за ограничений времени и кода, который после сдачи задачи можно выбрасывать. Но это чисто стиль. Разбиение на подсистемы и логика у кода наоборот отличные, без этого сложные задачи, особенно быстро на олимпиаде, не решить. А стиль лечится буквально за пару недель при наличии код-ревью в процессе.
Зачем? У меня нет никаких претензий ни к SSIM, ни к графику из статьи. У меня лишь претензии к выводу, которым этот график сопроводили, который ни из графика, ни из считаемой метрики никак не выходит.
Ну тогда пишите не про глаз. Пишите, что график SSIM имеет перегиб вот в этой вот точке, потому что SSIM учитывает близость пикселей, также как и алгоритм JPG. Да, идея этой близости навеяна особенностями нашего глаза, но перегиб не по этому, а потому что SSIM и jpeg считают одно и то же.
Место, где кривая «выигрыш в качестве / проигрыш в размере» резко меняет наклон. И это место (сюрприз) определяется всё той же CSF. До quality ~80 квантование режет только те частоты, к которым ваш глаз слабо чувствителен.
Тут натягивание совы на глубус. У вас там график SSIM - тупо численная характеристика разности по пикселям, ей на частоты, и какие из них наш глаз хорошо видит, вообще пофигу.
Это просто универсальный принцип убывающей отдачи, или же принцип Парето - 20% усилий отвечает за 80% результата. Следующие 20 за 80 от остатка. И так дале. Поэтому чем больше усилий тем меньше скорость роста результата.
Текущая реализация защиты от переполнения просто выводит overflow и возможно выдает неправильный результат, если умножение переполняется. Но не обязательно это делать, можно выдать корректный результат.
Вот вам надо проверить, что a*b >= c*d, т.е. знак у векторного произведения отрицательный. a,b,c,d в 64 бита помещаются.
Можно все еще достоверно проверить условие без переполнения.
Во-первых, можно реализовать простую длинную арифметику. Пусть ваше произведение возвращает пару int64 чисел - составляющих 128 битное число.
В ассемблере это вообще можно вылизать со флагами переноса и половинами регистров.
Эту пару можно сравнивать потом. Только отдельно знаки сначала проверьте.
С другой стороны, есть еще красивое решение без длинной арифметики.
Вот надо вам проверить a*b <= c*d. Допустим нулей и отрицательных чисел нет, знаки и нули вы отдельно сначала проверили. Тогда можно переписать a/c <= d/b. Тут можно сравнить целые части от делений. Если они разные - можно сразу решить какой там знак в соотношении. Если же целые части совпали, их можно вычесть: a%c/c <= d%b/b.
А теперь трюк: перевернем дроби. И уже надо проверить c / a%c >= b/ d%b. Тут опять рекурсивно сравниваем целые части, вычитаем если совпало, переворачиваем и так далее. Это фактически 2 параллельных алгоритма эвклида, они за log (M) шагов получат в числителе 0, после чего можно сразу сказать, что там больше чего.
Т.е. у вас рекурсивная функция, которая сначала проверяет на нули в числителях, потом целые части, потом берет остатки, переворачивает дроби и рекурсивно вызывает себя, возвращая обратный результат.
// a*b <=> c*d
int Compare(int a, int b, int c, int d) {
if (b == 0 && c == 0) return 0;
if (b == 0) return 1;
if (c == 0) return -1;
int l = a/c;
int r = d/b;
if (l < r) return 1;
if (l > r) return -1;
return -Compare(c, d%b, a%c, b)
}
У ТСПУ предусмотрен режим bypass (с англ. «обход»), пояснил СМИ источник в ИБ-департаменте крупной компании: если система не справляется с обработкой трафика, его можно пустить напрямую, без фильтрации.
Ну так это же и есть "Роскомнадзор не справляется".
Автор, а еще у вас какой-то косяк в программе. Числа не сходятся.
Во-первых, в ваших 36^3*4 вариантах встречаются варианты с повторениями тетраэдров, т.е. с одинаковыми "фазами". У вас же 3 фазы разные должны быть? Тогда должно быть чуть больше 3000 канонизированных состояний:
Вот у тетраэдра 12 ориентаций. Вот у вас 3 тетраэдра, раз у них фазы разные, т.е. они уникальные, то запихать их три в 4 слота есть 4!=24 варианта. Это же перестановка из 4 элементов {0,1,2,∅}
Значит всего "неканонизированных" состояний должно быть 24*12^3=41472. Потом, судя по вашей визуализации, вы считаете повороты этих 4 слотов неразличимыми. И они у вас как тетраэдр вращаются. У тетраэдра 12 различных поворотов, значит канонизированных состояний должно быть в 12 раз меньше: 41472/12=3456.
Как вы там насчитали 15576 состояний?
Если же вы рассматриваете варианты с повторяющемися фазами, то там будет 12^3*(24/12+6*12/12+3*4/4) = 1728*(2+6+3)=19008 состояний. Опять не как у вас.
Тут простые вычисления: 12^3 - это каждый из тетраэдров как-то ориентирован.
24/12 - это сколько способов расположить 3 различных элемента + пустоту в вершинах тетраэдра. 4! перестановки, но каждая имеет 12 уникальных поворотов.
3*12/12 - это сколько способов расположить 3 элемента, из которых 2 неразличимы. Это если у вас одна фаза повторяется 2 раза. Множитель 6, потому что 3 варианта, какая фаза повторяется, потом 2 варианта, какая из оставшихся фаз присутствует. Потом есть 12 перестановок из элементов {a,b,b,c} (2 фазы + пустота). Потом все остается 12 уникальных поворотов: какое из 6 ребер будет покрыто повторяшками и 2 варианта, как будут оставшиеся вершины.
3*4/4 - это вариант когда у вас одна фаза повторяется 3 раза. Там всего 4 перестановки и 4 поворота тетраэдра.
Да нет, нету тут никакого бэкраунда заумного у автора. Автор просто выдумал эти термины. Возможно, так солиднее выглядит у автора в голове. По идее, это простенькая комбинаторная задачка, так что тут можно было бы натянуть ее на комбинаторный бэкраунд и использовать всем известные оттуда термины. Но автор их не знает.
Вот есть тетраедр. Его можно по разному крутить. Это 12 положений: 4 варианта, на какой грани он стоит, и для каждого из них по 3 варианта, как он повернут вкруг вертикальной оси ( какая из трех вершин смотрит условно на север). Фазой автор тут называет номер или цвет тетраедра. Вот решил он, что у него будет 3 тетраэдра на 4 слота и они все 3 уникальные, т.е. мы различаем где какой будет. Их можно по разному расставить в эти 4 слота. Но вместо того, что бы следить за перестановкой 4-х обхеъктов (3 тетраэдра и 1 пустота) и отдельно ориентацией каждого из трех тетраэдров, автор засунул эту информацию в каждый из 4-х слотов. Т.е. у него там хранится какой это тетраэдр + как он там ориентирован. Но при этом положение пустоты храниться где-то рядом. Странное решение.
Вот это все возможные состояния. Потом автор решает, что а давайте эти 4 слота тоже расположим в виде тетраедра и будем считать все состояния, переводимые в друг друга поворотами этого тетраэдра, идентичными. И называет это сжатием и каким-то его достижением. Но это просто он так с потолка взял, что у него важными состояниями считаются вот такие-то. А мог бы запросто считать их различными, или расположить эти 4 слота не в тетраэдре а просто по кругу и считать повороты не важными.
Абстрактная фундаментальная математика всегда хороша даже без конкретных сиюминутных применений. Никто даже не думал, что раскладывание чисел на простые множители кому-то может быть полезно на практике, а на этой математике сейчас куча криптографии и почти весь интернет держится. А от линейной алгебры умножения матриц мы получили чатГПТ. Какие-то совершенно абстрактные вещи через десятилетия оказались нужны в фундаментальной физике.
Вы представили себе комбинаторный объект, опеределили операции на нем а дальше реализовали чуть-чуть не самый наивный метод вычисления чего-то этих операций. Зачем?
Задача сама по себе с точки зрения комбинаторики или computer science очень типовая. Метод оптимизации через предподсчет - тоже.
Вообще, дарю вам идею, обощение вашего предподсчета: двочиная таблица предподсчета. Вы считайте не только F64, а считайте A_n = F{2^n} = A_{n-1}(A_{n-1}).
В table[state][0] подсчитайте результат применения операции один раз а потом тупо двумя вложенными циклами: table[state][n] = table[table[state][n-1]][n-1].
Еще в 10 раз ускорите, потратив в несколько раз больше памяти правда, но памяти-то надо всего 15к ячеек - фигня.
Edit: Ах, извиняюсь, вы до этого уже додумались, это у вас называется binary jump hierarchy.
Основной посыл моего комментария остался в силе. Смысла всего этого не вижу. Простое упражнение в базовых комбинаторных задачках.
Это ваша третья статья на хабр по этой маленькой демке. Я правильно понимаю, что единственное отличие от предыдущей статьи, что тут у вас 2x2 прохода вместо 8x8, а отличие от первой, что вы тут VSYNC запилили?
Вы будете после каждого тривиального изменения статью на хабр постить?
Если автору нужна точность, то именно всякие вручную реализованные длинные числа и дадут любую точность, а не какие-то жалкие 80-бит.
И это уже интереснее чем впенедюрить OpenMP и тупо отрендерить картинку в 4x разрешении для какого-то сглаживания. Которое, кстати, нужно только при интерактиве при движении. Если вам хочется качество статической картинки, то вам не нужно сглаживание - вам нужно тупо большее разрешение и все.
Ну неужели вам сложно "первому в мире" реализовать свои вычисления на основе трех float вместо одного, получив искомые 63 бита точности, если вам так надо? Эта троица даже отлично ложиться на шейдерную машинерию с их трехмерными векторами. А если добавить еще одно число, можно и экспоненту хранить гораздо большую, чем в 80-битных числах
Тут, правда, придется немного подумать над тем как такие числа умножать и складывать (это просто на самом деле).
Это, конечно, будет медленнее одной операции x87, но зато у вас потоков будет не 8, а тысячи.
Зависит от области. В бигтехе вполне себе алгоритмическое программирование нужно. Я несколько статей на эту тему на хабре написал: встречаются самые настоящие литкодовские задачи. Конечно, перекладывания джесонов гораздо больше, но навыки нужны для самых сложных задач, с которыми вы столкнетесь. А перекладывание джейсонов - это тоже алгоритмическая задача, хоть и тривиальная. Принципиально ничем не отличается.
Неподдерживаемый код - это понятная привычка, вызванная из-за ограничений времени и кода, который после сдачи задачи можно выбрасывать. Но это чисто стиль. Разбиение на подсистемы и логика у кода наоборот отличные, без этого сложные задачи, особенно быстро на олимпиаде, не решить. А стиль лечится буквально за пару недель при наличии код-ревью в процессе.
Зачем? У меня нет никаких претензий ни к SSIM, ни к графику из статьи. У меня лишь претензии к выводу, которым этот график сопроводили, который ни из графика, ни из считаемой метрики никак не выходит.
Ну тогда пишите не про глаз. Пишите, что график SSIM имеет перегиб вот в этой вот точке, потому что SSIM учитывает близость пикселей, также как и алгоритм JPG. Да, идея этой близости навеяна особенностями нашего глаза, но перегиб не по этому, а потому что SSIM и jpeg считают одно и то же.
Тут натягивание совы на глубус. У вас там график SSIM - тупо численная характеристика разности по пикселям, ей на частоты, и какие из них наш глаз хорошо видит, вообще пофигу.
Это просто универсальный принцип убывающей отдачи, или же принцип Парето - 20% усилий отвечает за 80% результата. Следующие 20 за 80 от остатка. И так дале. Поэтому чем больше усилий тем меньше скорость роста результата.
Текущая реализация защиты от переполнения просто выводит overflow и возможно выдает неправильный результат, если умножение переполняется. Но не обязательно это делать, можно выдать корректный результат.
Вот вам надо проверить, что a*b >= c*d, т.е. знак у векторного произведения отрицательный. a,b,c,d в 64 бита помещаются.
Можно все еще достоверно проверить условие без переполнения.
Во-первых, можно реализовать простую длинную арифметику. Пусть ваше произведение возвращает пару int64 чисел - составляющих 128 битное число.
Так:
В ассемблере это вообще можно вылизать со флагами переноса и половинами регистров.
Эту пару можно сравнивать потом. Только отдельно знаки сначала проверьте.
С другой стороны, есть еще красивое решение без длинной арифметики.
Вот надо вам проверить a*b <= c*d. Допустим нулей и отрицательных чисел нет, знаки и нули вы отдельно сначала проверили. Тогда можно переписать a/c <= d/b. Тут можно сравнить целые части от делений. Если они разные - можно сразу решить какой там знак в соотношении. Если же целые части совпали, их можно вычесть: a%c/c <= d%b/b.
А теперь трюк: перевернем дроби. И уже надо проверить c / a%c >= b/ d%b. Тут опять рекурсивно сравниваем целые части, вычитаем если совпало, переворачиваем и так далее. Это фактически 2 параллельных алгоритма эвклида, они за log (M) шагов получат в числителе 0, после чего можно сразу сказать, что там больше чего.
Т.е. у вас рекурсивная функция, которая сначала проверяет на нули в числителях, потом целые части, потом берет остатки, переворачивает дроби и рекурсивно вызывает себя, возвращая обратный результат.
Ну так это же и есть "Роскомнадзор не справляется".
Божечки, промотал ваш профиль на хабре, практически идентичных статей от вас аж 6(шесть) штук! Какое безобразие.
Ну смотрите, вот ваша статья от 25 февраля: https://habr.com/ru/articles/1001498/
И она и вот эта обе ссылаются на один и тот же репозиторий. В этом репозитории с 25 февраля было только 4 комита 15 марта. Из них только один менял код: https://github.com/Divetoxx/Mandelbrot-2/commit/118353923097e3756729c379dccd693631b0f66e#diff-e44b21fdead157a47cc6889827a81a973b681314398117f459c3a1955ca1e2e1
Там чуть-чуть поменяны какие-то константы, в одном месте переставлены 2 строчки, в другом исправлено форматирование и одна константа поменяна.
DwmFlush был добавлен раньше первой статьи - 17 февраля.
Т.е. то, что вы вот в этой статье аж в заголовок засунли, было уже на момент предыдущей статьи.
Спрашивается, нафига вы вот эту статью написали?
Т.е. "фаза" можно заменить в вашем тексте на "цвет" и ничего не поменяется?
Что такое вообще "фаза", откуда она взялась, что означает?
Хабр умеет формулы рисовать:
Вы их уже в формате латеха пишите, просто выделите и нажмите кнопку
Автор, а еще у вас какой-то косяк в программе. Числа не сходятся.
Во-первых, в ваших 36^3*4 вариантах встречаются варианты с повторениями тетраэдров, т.е. с одинаковыми "фазами". У вас же 3 фазы разные должны быть? Тогда должно быть чуть больше 3000 канонизированных состояний:
Вот у тетраэдра 12 ориентаций. Вот у вас 3 тетраэдра, раз у них фазы разные, т.е. они уникальные, то запихать их три в 4 слота есть 4!=24 варианта. Это же перестановка из 4 элементов {0,1,2,∅}
Значит всего "неканонизированных" состояний должно быть 24*12^3=41472. Потом, судя по вашей визуализации, вы считаете повороты этих 4 слотов неразличимыми. И они у вас как тетраэдр вращаются. У тетраэдра 12 различных поворотов, значит канонизированных состояний должно быть в 12 раз меньше: 41472/12=3456.
Как вы там насчитали 15576 состояний?
Если же вы рассматриваете варианты с повторяющемися фазами, то там будет 12^3*(24/12+6*12/12+3*4/4) = 1728*(2+6+3)=19008 состояний. Опять не как у вас.
Тут простые вычисления: 12^3 - это каждый из тетраэдров как-то ориентирован.
24/12 - это сколько способов расположить 3 различных элемента + пустоту в вершинах тетраэдра. 4! перестановки, но каждая имеет 12 уникальных поворотов.
3*12/12 - это сколько способов расположить 3 элемента, из которых 2 неразличимы. Это если у вас одна фаза повторяется 2 раза. Множитель 6, потому что 3 варианта, какая фаза повторяется, потом 2 варианта, какая из оставшихся фаз присутствует. Потом есть 12 перестановок из элементов {a,b,b,c} (2 фазы + пустота). Потом все остается 12 уникальных поворотов: какое из 6 ребер будет покрыто повторяшками и 2 варианта, как будут оставшиеся вершины.
3*4/4 - это вариант когда у вас одна фаза повторяется 3 раза. Там всего 4 перестановки и 4 поворота тетраэдра.
Да нет, нету тут никакого бэкраунда заумного у автора. Автор просто выдумал эти термины. Возможно, так солиднее выглядит у автора в голове. По идее, это простенькая комбинаторная задачка, так что тут можно было бы натянуть ее на комбинаторный бэкраунд и использовать всем известные оттуда термины. Но автор их не знает.
Вот есть тетраедр. Его можно по разному крутить. Это 12 положений: 4 варианта, на какой грани он стоит, и для каждого из них по 3 варианта, как он повернут вкруг вертикальной оси ( какая из трех вершин смотрит условно на север). Фазой автор тут называет номер или цвет тетраедра. Вот решил он, что у него будет 3 тетраэдра на 4 слота и они все 3 уникальные, т.е. мы различаем где какой будет. Их можно по разному расставить в эти 4 слота. Но вместо того, что бы следить за перестановкой 4-х обхеъктов (3 тетраэдра и 1 пустота) и отдельно ориентацией каждого из трех тетраэдров, автор засунул эту информацию в каждый из 4-х слотов. Т.е. у него там хранится какой это тетраэдр + как он там ориентирован. Но при этом положение пустоты храниться где-то рядом. Странное решение.
Вот это все возможные состояния. Потом автор решает, что а давайте эти 4 слота тоже расположим в виде тетраедра и будем считать все состояния, переводимые в друг друга поворотами этого тетраэдра, идентичными. И называет это сжатием и каким-то его достижением. Но это просто он так с потолка взял, что у него важными состояниями считаются вот такие-то. А мог бы запросто считать их различными, или расположить эти 4 слота не в тетраэдре а просто по кругу и считать повороты не важными.
По-вашему воткнуть вызов DwmFlush() в функцию прорисовки - это нетривиальное изменение, заслуживающее отдельной статьи?
Повторю свой вопрос: Вы будете после каждого тривиального изменения статью на хабр постить?
Зачем? Это просто офигенно же.
Абстрактная фундаментальная математика всегда хороша даже без конкретных сиюминутных применений. Никто даже не думал, что раскладывание чисел на простые множители кому-то может быть полезно на практике, а на этой математике сейчас куча криптографии и почти весь интернет держится. А от линейной алгебры умножения матриц мы получили чатГПТ. Какие-то совершенно абстрактные вещи через десятилетия оказались нужны в фундаментальной физике.
Вы представили себе комбинаторный объект, опеределили операции на нем а дальше реализовали чуть-чуть не самый наивный метод вычисления чего-то этих операций. Зачем?
Задача сама по себе с точки зрения комбинаторики или computer science очень типовая. Метод оптимизации через предподсчет - тоже.
Вообще, дарю вам идею, обощение вашего предподсчета: двочиная таблица предподсчета. Вы считайте не только F64, а считайте A_n = F{2^n} = A_{n-1}(A_{n-1}).
В
table[state][0]подсчитайте результат применения операции один раз а потом тупо двумя вложенными циклами:table[state][n] = table[table[state][n-1]][n-1].Еще в 10 раз ускорите, потратив в несколько раз больше памяти правда, но памяти-то надо всего 15к ячеек - фигня.
Edit: Ах, извиняюсь, вы до этого уже додумались, это у вас называется binary jump hierarchy.
Основной посыл моего комментария остался в силе. Смысла всего этого не вижу. Простое упражнение в базовых комбинаторных задачках.
Это ваша третья статья на хабр по этой маленькой демке. Я правильно понимаю, что единственное отличие от предыдущей статьи, что тут у вас 2x2 прохода вместо 8x8, а отличие от первой, что вы тут VSYNC запилили?
Вы будете после каждого тривиального изменения статью на хабр постить?
Ну извините, это же все меняет. 8x разрешение - это же принципиально другое, чем 4x /s.
Если автору нужна точность, то именно всякие вручную реализованные длинные числа и дадут любую точность, а не какие-то жалкие 80-бит.
И это уже интереснее чем впенедюрить OpenMP и тупо отрендерить картинку в 4x разрешении для какого-то сглаживания. Которое, кстати, нужно только при интерактиве при движении. Если вам хочется качество статической картинки, то вам не нужно сглаживание - вам нужно тупо большее разрешение и все.
Ну неужели вам сложно "первому в мире" реализовать свои вычисления на основе трех float вместо одного, получив искомые 63 бита точности, если вам так надо? Эта троица даже отлично ложиться на шейдерную машинерию с их трехмерными векторами. А если добавить еще одно число, можно и экспоненту хранить гораздо большую, чем в 80-битных числах
Тут, правда, придется немного подумать над тем как такие числа умножать и складывать (это просто на самом деле).
Это, конечно, будет медленнее одной операции x87, но зато у вас потоков будет не 8, а тысячи.