Comments 19
Когда я впервые столкнулся с оператором Modulo (%), я ничего не понял
?. Тогда я учился в 9 классе...
шок-контент
следующий урок - возведение в степень?
Вам бы рефераты писать за деньги. Пока читал чуть не захлебнулся.
Если хотя бы абзац про целевую аудиторию вынести в самое начало (и желательно шрифтом в пол экрана), то этот текст имел бы хоть какой-то смысл
Про деление с остатком в js следует знать, что на отрицательном делимом оно работает неправильно (например, -1 % 3 === -1, хотя должно быть 2), и к результату надо прибавлять делитель. И как раз этот момент не был упомянут.
В JS используется вариант, когда знак остатка берётся из делителя. Он имеет свои плюсы.
Если x % y = z, то целочисленное деление [x / y] = (x - z) / y.
В JS: -1 % 3 === -1 => [-1 / 3] = (-1 + 1) / 3 = 0
Классическое деление по модулю: -1 mod 3 = 2 => [-1 / 3] = (-1 - 2) / 3 = -1, что, может, математически и верно, но контринтуитивно.
круче на самом деле: Представим ситуацию у вас сетка тайлов размером 2.5rem, а координата спрайта на нем допустим 6rem - внезапно 6 % 2.5 == 1 // (rem) смещение относительно тайла
а если у вас движок с индексированием спрайтов к ячейке тайлов (логически объект перемещается по клеткам дискретно) то вам удобнее хранить относительное смещение +-1/2 tileWidth (причем безразлично при каком spriteWidth)
тогда можно считать кооринаты от центров спрайта spriteX= objX - 1/2 * spriteWidth
перед делением по модулю производим стандартную модулярную операцию смещающую область определения диапазона:
offsetX= ( (spriteX + 1/2 * tileWidth) % tileWidth) - 1/2 * tileWidth
Умножение двух чисел x и y имеет линейную сложность, так как требуется выполнить x умножений
Что, простите? Даже если вы имели в виду "умножение на N = N сложений", то это все равно далеко от реальности, иначе перемножение/деление больших чисел занимало бы вечность. Деление, кстати, более сложная для процессора операция, чем умножение.
У нас есть запись вида x = y % z , которая будет эквивалентна x = x - y * (x / y)
А у вас спина белая переменные перепутались.
Обратите внимание, что на практике сложность операции взятия остатка может быть оптимизирована в зависимости от аппаратной архитектуры и используемого компилятора
Так может быть, расскажете, как на практике, а не как у вас в голове на основе мат. модели уровня 5 класса? Ведь задан контекст: браузерный JS, а иначе в этой информации не просто нет смысла, а она еще и вредит, т.к. создает ложные представления.
x + y – это простое сложение двух переменных. Вне зависимости от значений x и y, для выполнения сложения требуется одна операция. Следовательно, асимптотическая сложность этого выражения - константа O(1).
Сильное заявление, пахнет нобелевкой)
На самом деле это не так. Тот, кто умеет складывать числа в столбик знает, что для получеия суммы нужно сложить каждый разряд одного числа с тем же разрядом другого. Чтобы получить количество разрядов числа, нужно взять его логарифм. Так что сложность сложения двух чисел x и y произвольной длины - примерно O(log(x + y)).
Раз уж вы процитировали мой комментарий в статье, хочу ещё кое что пояснить.
Ваши замечания:
UPD: Как хорошо подметили в комментариях, если у нас безразмерные целые числа, то понятно, что ты за один такт процессора их не сложить даже на современных процессорах.
Но если мы говорим про Int64, то это определенно O(1), а если это безразмерный Int то логарифм более похож на правду.
Если открыть учебник по матанализу за первый курс и посмотреть, что вообще такое О-большое, то нетрудно увидеть, что в его определении используется понятие предела (стремления). Например, применительно к оценке сложности алгритмов, когда говорится f(n) = O(g(n)), (где n - длина данных на входе), подразумевается поведение функции f при n стремящемся к бесконечности. Для любого конечного множества, например, для целых чисел, помещающихся в Int64, понятие О-большого не имеет смысла.
Причём, это оганичение существенно: непонятно, как распространить определение на конечное множество так, чтобы получилось что-то полезное. Например, дальше автор рассуждает про "ассимптотическую сложность" умножения и деления, но если и здесь речь про Int64, то сложность тоже в некотором смысле константная: я смогу подобрать такую константу, что умножение любых двух чисел из Int64 в неё заведомо уложится.
Если автор статьи имел в виду, что на современных процессорах скорость сложения и умножения встроенных чисел зависит от их длины определенным образом, нужно было так и сказать, а не пользоваться математическими терминами.
Это частая ошибка не математиков вы правы конечно...
Однако O(1) сложность из такого выражения законна, если имеется ввиду что X и Y это не "слагаемые из разрядов" а ДВЕ автономные ячейки переменных для АЛУ в которых все ведущие нули СЧИТАЮТСЯ но зато гарантируется что больше или меньше разрядов не будет. То что вы сказали возникает при реализации длинной арифметики.
Подумайте еще над тем что в реальности вы не управляете тем в какой системе счисления считает АЛУ, да у вас есть биты которыми представлены данные но доступ у программиста только к представлению, и при всем желании минимальный счетный "разряд" на практике в 256-тичной системе... а когда long переменные считаем - то будет 4294967296-ичная система. Тот факт что кратные степеням 2ки системы легко визуально друг в друга переводятся, не должен бы сковывать мышление на двоичной (некоторые алгоритмы обретают гораздо более приятную математическую архитектуру если их рассматривать в 8-ичной или 4-ичной системах)
Однако O(1) сложность из такого выражения законна, если имеется ввиду что X и Y это не "слагаемые из разрядов" а ДВЕ автономные ячейки переменных для АЛУ в которых все ведущие нули СЧИТАЮТСЯ но зато гарантируется что больше или меньше разрядов не будет
Это неверно. Во втором комментарии (у меня он показывается прямо над вашим) я дополнил, что О-большое символика неприменима к конечным множествам чисел. В частности, ко всем числам, которые помещаются в ячейку.
Подумайте еще над тем что в реальности вы не управляете тем в какой системе счисления считает АЛУ, да у вас есть биты которыми представлены данные но доступ у программиста только к представлению
Для анализа алгоритмической сложности система счисления в целом не имеет значения (за исключением, наверное, некоторых алгоритмов, связанных с теорией чисел).
Спасибо, Вы прибавили мотивации тоже выложить свою статью на Хабре
Разработчик. Под тридцатку лет возраста. Только открыл для себя остаток от деления и решил его опробовать в JS. Поколение егэшников - это поистине чудо, потому что рационально объяснить это не представляется возможным.
Вайтишник прогуливал уроки и теперь догоняет...
Я так понимаю весь текст с упоминанием "асимптотической сложности" это гопотаЧат генеренный текст.
Что такое деление по модулю в JavaScript?