Comments 17
Нас учат, что чтение данных из оперативной памяти — ужасно долгая операция.
Объясните пожалуйста это утверждение. Откуда тогда чтение быстрее, чем из оперативной памяти?
for(let i = 0; i < matrixSize; i++)
for(let j = i + 1; j < matrixSize; j++)
let otherRowFirst = matrix[j][i];
Выглядит как, что на каждое чтение пары байт в цикле происходит постоянное считавание 64-байтовых строк из памяти в кэш процессора.
Вы же понимаете что Uint8Array оптимизирует только память? При каждом доступе JS проверяет выход за границы.
Если хотите реальной производительности (а ещё не писать всю эту математику) — берите lapack и компилируйте его в WebAssembly, любой другой путь — ССЗБ.
O(n^3)
раз брать по модулю не нужно, промежуточные вычисления вполне помещаются в разумные типы, если модуль маленький. Даже если он большой (порядка 10^9
), можно брать Uint64 и делать каждые 16 итераций одно сравнение с вычитанием (завести константу 16*Mod*Mod
).
Операция деления это далеко не 2 такта. На современных компьютерах деление порядка 50 тактов, а вот суммирование, умножение — один.
Кроме того, первоначальный вариант функции wholeMod
можно ускорить. if
дешевле, чем %
(эта операция, как известно, основана на делении), то есть лучше сделать взятие остатка и потом return res if res >=0 else res + domain
Никакие CPU-friendly оптимизации не исправят асимпоты алгоритмической сложности. То, что тут написано — это одна из методик динамического программирования, которая меняет асимптоту.
Далее: js, насколько я знаю, работает с f64, а деление в f64 довольно дорогое (особенно, если не на 2).
Третье: ковейеризация очень важна. Если есть зависимость между данных, то конвейер сбрасывается, и тогда деление (f64) делается за 20+ тактов. Это много и дорого.
Кэширование данных увеличивает скорость даже в неожиданных случаях