Комментарии 28
Как-то сложно змейка у Вас сделана. Ведь довольно очевидная формула R = (i+j-2)*(i+j-1)/2+(i+j)%2*(j-i)+i проще!
Первое слагаемое получается благодаря формуле суммы первых N натуральных чисел, а второе - из-за изменения направления...
Прошу простить - это только для первой половины так просто, а вот добавляя вторую получается уже длинновато:
int R = (i+j-2) * (i+j-1)/2 + (i+j)%2*(j-i) + i
+ (1 - N*N + 2*N*(i+j-1) - i - j - (i+j-2)*(i+j-1)) * ((i+j-1)/n); Или, используя D как у Вас:
int D = i+j-1;
int R = (D-1)*D/2 + D%2*(i-j)+j
- (D-N)*(D-N) * (D/N);Второе слагаемое длиннее и выводить его дольше.
(Сравнимо с Вашим вариантом.)
Да, я собирался написать Вам, что формула работает только наполовину. Так сказать рассчитана на бесконечно расширяющуюся матрицу. А так в целом получается почти то же самое . Не исключено, что обе формулы можно сократить немного . Однако и размер без того длинной статьи тогда увеличится .
Да и основной целью работы является - показать, доказать, обосновать математически приведённые пути решения.
Просто Вы два раза по модулю 2 делите, а я - один, а так получилось одно и то же, хотя мы немного по-разному, вроде бы, шли к окончательному варианту...
Кстати интересно еще вывести формулу для спирали.
Уже вывел. В начале этой статьи есть ссылка на нее https://habr.com/ru/post/560266/.
Уже вывел. В начале этой статьи есть ссылка на нее https://habr.com/ru/post/560266/.
Выглядит как безумно трудная работа. Респект!
... С точки зрения оптимизации, мне интуция говорит, что в формуле слишком много умножений и делений (mod тоже деление) для того, чтобы победить условные переходы по производительности.
Ну, mod 2 - не совсем деление, приличный компилятор соптимизирует до and 1 или подобного. А деление на 2 - сдвиг вправо на разряд.
int D = i+j-1;
int R = (((D-1)*D)>>1) + (D&1)*(i-j)+j
- (D-N)*(D-N) * (D/N);На ассемблере можно и от деления на N избавиться, оно нам нужно только для того, чтобы понять, нужно ли нам вообще это вычитаемое: мы сначала всё равно вычитаем из D N. Флаг переноса будет установлен соответствующим образом, так что можно использовать вычитание займом и побитовое "и" (т.е. (D-N)*(D-N)*(D/N) превращается во что-то такое: mov edx, N / sub edx, D / sbb eax, eax / and eax, edx / mul eax) , а зависимости регистров можно разбавить вычислением других слагаемых.
Да, часть уйдёт. Но всё равно есть 4 умножения и деление. Я не достаточно хорошо знаю что станет с data dependency из-за того, что D вычисляется строчкой выше (будет конвейеризация или нет?), но всё равно это выглядит как "много".
Мой поинт состоит в том, что часть умножений и делений тут - для выбора кусочной функции. Может быть, обычный if будет быстрее?
Вероятнее всего if будет быстрее, в этом я с Вами полностью согласен. Однако, статья отмечена тегом "Занимательные задачи", поэтому весь описанный процесс скорее является интересным кейсом (по мнению автора), чем работой претендующей на научность или практическую полезность.
Внимание больше акцентировано на самом анализе и пути построении формул, чем на итоговом результате.
Самым трудным, конечно, было обосновать и описать весь процесс.
Поначалу задача решена чисто интуитивным способом, только после пришлось переступить через программистскую лень и "сделать как надо", т.е. все разяснить. Любой программист поймет, очень часто мы пытаемся решить задачу "нахрапом", а потом не можем объяснить как оно работает или почему оно не работает, и самое худшее - через определенное время не можем вспомнить свою работу (здесь уместна шутка "Пишите код так, как будто сопровождать его будет склонный к насилию психопат, который знает, где вы живёте").
Прошёл для смеха змейку когда-то на Нокии, вроде 3210. Идем челноком от одного края экрана к другому, оставляя одну горизонтальную строку свободной, по которой возвращаемся назад. Повторять до полного заполнения экрана.
То, что вы называете змейкой с диагональным заполнением, называется zigzag ordering, оно например в jpeg применяется.
А зачем дважды вычислять определители половинок (для диагонального варианта, в частности)? Есть же универсальная формула 1-x для превращения 1 в 0 и наоборот
Вопрос: инструкции j** в ассемблере настолько тормозные что работают дольше чем куча арифметических операций?
Например так вы узнаете остаток от деления на 2 (пардон если чуток ошибся в написании ассемблера, не пользуюсь) и сделаете переход по условию:
shr eax, 1
jc label
(тут код если четное)
jmp next_code
label:
(тут код если нечётное)
next_code:Мне кажется даже из кеша не выходим.
PS: я где-то писал что-то похожее, нужно откопать процедуру и протестировать...
Здесь и не утверждается, что арифметический способ быстрее для заполнения всего массива. Однако у него есть одно преимущество - он позволяет вычислить значение любого элемента без необходимости проходить циклом по всем ячейкам находящимся до него (это указано в заключении статьи).
Кроме того, задача носит сугубо теоретический характер, а суть работы заключается скорее в пути построения формулы, нежели в конечном результате.
Мне кажется вам в статье совсем не нужно было приводить код, достаточно было математики (у вас и заголовок соответствующий), иначе неизбежно люди смотрят на качество кода, а это не входит в рамки статьи.
Ну не совсем все так печально.
Код здесь помогает наглядно продемонстрировать работу формул и выражений, причем он помещен в готовой для копипасты форме. Таким образом читатели могут воочию убедиться в его функциональности, а соответственно - и в функциональности математического аппарата (так сказать доказательная база).
Ну а ключевое слово "математическое" в заголовке ни в коем случае не ограничивает инструментарий только этой сферой, и не запрещает проверять мат.теорию на прог. практике.Тем более в современных условиях математика, точнее ее деятели, привязаны к компьютерным вычислениям (ну кто сейчас захочет на бумаге складывать столбиком или или использовать счетные палочки?).
Таким образом, код здесь не является движущей силой, а скорее средством моделирования.
Что касается комментаторов, - их замечания, дополнения, предложения непосредственно по коду, являются шагом к дальнейшему развитию мысли,и хоть, как было отмечено - выходят за рамки статьи, никоим образом не вносят какой-либо негатив в обсуждаемый вопрос.
Справедливости ради, решение через for и if трудно разбросать на несколько ядер. Так что не исключено, что хорошая векторизация даст заметный прирост производительности. Но эту гипотезу тоже надо проверять, конечно.
Очень может быть!
Все же основной оптимизацией в работе считается получение возможности независимого вычисление любого элемента по его координатам за одну циклическую операцию (не уверен в названии, но думаю моя мысль ясна).
А так, конечно, хотелось бы претендовать и на увеличение производительности в целом по процессу заполнения всей матрицы. Но подозреваю, что это врневозможнои, так как циклы-то присутсвовать будут все равно - циклы для пошаговой итерации. И плюс еще и само вычисление
А можно ещё решить задачу "обратным" способом: для каждого x из 1..N² вычислить его координаты (i, j) для конкретного заполнения
Что-то мне подумалось, что ведь можно сделать два цикла, один сначала идёт слева направо (x++), а потом второй справа налево (x--). В обоих "y" шагает +2 после прохода по "x". И никаких if и никаких арифметических операций. Ну на первый взгляд.
Во втором случае можно так же идти x++ но иначе вычислять значение в ячейке.
Если всё запихать в C# Parallel.For / Parallel.ForEach то будет весьма резво заполняться.
Математическое решение задачи о матрице «змейкой»