Какой самый быстрый способ реализовать операцию, которая возвращает абсолютное значение числа?
x=root(x²)
или
if !isPositive(x):
x=x*(-1)
На самом деле этот вопрос можно перевести как: насколько быстро if (и почему, пожалуйста).
Мои преподаватели, преподающие в колледже, всегда говорили мне избегать if, потому что они очень медленны, но я всегда забывал спросить, как медленно и почему. Кто-нибудь знает об этом?
Условные операции медленнее, чем простые арифметические операции, но намного, намного быстрее, чем что-то глупо, как вычисление квадратного корня.
Правила большого пальца из моих дней сборки:
Существует большой трюк для вычисления абсолютного значения целочисленного 2s-дополнения без использования оператора if. Теория идет, если значение отрицательное, вы хотите переключить биты и добавить один, иначе вы хотите передать бит через как есть. A XOR 1 происходит с переключением A и A XOR 0, что оставляет A неповрежденным. Итак, вы хотите сделать что-то вроде этого:
uint32_t temp = value >> 31; // make a mask of the sign bit
value ^= temp; // toggle the bits if value is negative
value += temp & 1; // add one if value was negative
В принципе, вы можете сделать это всего за три команды сборки (без ветки). И вы хотели бы думать, что функция abs(), которую вы получаете с помощью math.h, делает это оптимально.
Нет ветвей == более высокая производительность. В отличие от ответа @paxdiablo выше, это действительно важно в глубоких конвейерах, где больше ваших ветвей у вас в коде, тем больше вероятность того, что у вас есть предиктор вашего ветки, ошибайтесь и придется откатываться назад и т.д. Если вы избегаете ветвления, возможно, все будет двигаться вместе с полным дросселем в вашем ядре:).
Ух, ваши учителя на самом деле сказали вам это? Правило, которое большинство людей придерживается, состоит в том, чтобы сначала сделать ваш код доступным для чтения, а затем настроить любые проблемы с производительностью после того, как они оказались фактически проблемами. 99.999% времени, когда вы никогда не увидите проблему с производительностью, вы использовали слишком много утверждений if. Кнут сказал, что это лучше всего, "преждевременная оптимизация - корень всего зла".
Вычисление квадратного корня, вероятно, является одной из худших вещей, которые вы могли бы сделать, потому что это очень медленно. Обычно для этого есть функция библиотеки; что-то вроде Math.Abs (). Умножение на -1 также не нужно; просто верните -x. Поэтому хорошим решением будет следующее.
(x >= 0) ? x : -x
Компилятор, вероятно, оптимизирует это для отдельных инструкций. Условия могут быть довольно дорогими для современных процессоров из-за длинных конвейеров выполнения - вычисления должны быть выброшены, если ветвь была пропущена, и процессор начал выполнять инструкции с неправильного пути кода. Но из-за упомянутой оптимизации компилятора в этом случае вам не все равно.
Для полноты, вот способ сделать это для поплавок IEEE на системах x86 в С++:
*(reinterpret_cast<uint32_t*>(&foo)) &= 0xffffffff >> 1;
Вариант if почти наверняка будет ослепительно быстрым по сравнению с квадратным корнем, поскольку он обычно переводится на инструкцию условного перехода на уровне машинного кода (после оценки выражения, которое может быть сложным, но не в этот случай, так как это простая проверка для менее 0).
Взятие квадратного корня из числа, вероятно, будет намного медленнее (метод Ньютона, например, использовал бы множество операторов if на уровне машинного кода).
Вероятным источником путаницы является тот факт, что if неизменно приводит к изменению указателя инструкции в некотором последовательном порядке. Это может замедлить работу процессоров, которые предварительно собирают инструкции в конвейер, поскольку они должны повторно заполнить конвейер, когда адрес неожиданно изменится.
Однако стоимость этого будет незначительной по сравнению с выполнением операции с квадратным корнем, а не простой проверкой и отрицанием.
Какой самый быстрый способ получить абсолютное значение числа
Я думаю, что "правильный" ответ здесь не на самом деле. Самый быстрый способ получить абсолютное число - это, вероятно, использование Intel Intrinsic. См. https://software.intel.com/sites/landingpage/IntrinsicsGuide/ и найдите "vpabs" (или другое внутреннее значение, которое выполняет задание для вашего CPU). Я уверен, что он побьет все другие решения здесь.
Если вам не нравятся intrinsics (или не могут использовать их или...), вы можете проверить, достаточно ли компилятор достаточно умен, чтобы выяснить, вызван ли вызов "собственное абсолютное значение" (std::abs в С++ или Math.Abs(x) в С#) автоматически изменятся на внутреннее - в основном, что предполагает просмотр дизассемблированного (скомпилированного) кода. Если вы работаете в JIT, убедитесь, что оптимизация JIT не отключена.
Если это также не дает вам оптимизированных инструкций, вы можете использовать описанный здесь метод: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs.
Операция modulo используется для поиска остатка, вы имеете в виду абсолютное значение. Я изменил вопрос, потому что это должно быть, если! Pos (x), то x = x * -1. (не было)
Я бы не стал беспокоиться об эффективности оператора if. Вместо этого сосредоточьтесь на читабельности вашего кода. Если вы обнаружите, что есть проблема с эффективностью, тогда сосредоточьтесь на профилировании кода, чтобы найти реальные узкие места.
Если вы хотите следить за эффективностью во время кодирования, вы должны только беспокоиться о сложностях большого числа ваших алгоритмов.
Если утверждения очень эффективны, они оценивают любое выражение, а затем просто изменяют счетчик программ на основе этого условия. Счетчик программ хранит адрес следующей команды, которая должна быть выполнена.
Mulitplication by -1 и проверка, если значение больше 0, оба могут быть сведены к одной команде сборки.
Поиск корня числа и возведение в квадрат этого числа вначале, безусловно, больше операций, чем if с отрицанием.
Время, затрачиваемое на квадратный корень, намного больше времени, затраченного на выполнение условного. Если вас научили избегать условностей, потому что они медленны, то вы были дезинформированы. Они намного медленнее, чем тривиальные операции, такие как добавление или вычитание целых чисел или смещение битов - вот почему разворачивающиеся циклы могут принести пользу, только если вы делаете такие тривиальные операции. Но в великой схеме вещей условности хорошие и быстрые, неплохие и медленные. Сделать что-то сложное, как вызвать функцию или вычислить квадратный корень, чтобы избежать условного утверждения, является сумасшедшим.
Кроме того, вместо (x = x * -1) почему бы не сделать (x = 0 - x)? Может быть, компилятор будет оптимизировать их одинаково, но не все равно проще?
Используете ли вы сборку 8086?; -)
; abs value of AX
cwd ; replicate the high bit into DX
xor ax, dx ; take 1 complement if negative; no change if positive
sub ax, dx ; AX is 2 complement if it was negative The standard
: absolute value method works on any register but is much
; slower:
or bx, bx ; see if number is negative
jge notneg ; if it is negative...
neg bx ; ...make it positive
notneg: ; jump to here if positive
(вопиюще украденный)
Если вы просто сравниваете абсолютные значения двух чисел (например, вам не нужно абсолютное значение либо после сравнения), а просто квадратизируйте оба значения, чтобы сделать как положительные (удалить знак каждого значения), тем больше квадрат будет больше, чем меньший квадрат.
То, что быстрее, зависит от того, какой компилятор и какой процессор вы нацеливаете. На большинстве процессоров и всех компиляторов x = (x >= 0)? х: -x; это самый быстрый способ получить абсолютную величину, но на самом деле часто стандартные функции уже предлагают это решение (например, fabs()). Он компилируется в сравнение, за которым следует инструкция условного присваивания (CMOV), а не условный переход. Однако на некоторых платформах отсутствует эта инструкция. Хотя, компилятор Intel (но не Microsoft или GCC) автоматически преобразует if() в условное присваивание и даже попытается оптимизировать циклы (если это возможно).
Ветвление кода в общем случае медленнее, чем условное присвоение, если CPU использует статистическое прогнозирование. if() может быть медленнее в среднем, если операция повторяется многократно, а результат условия постоянно меняется. Процессоры, такие как Intel, начнут вычислять обе ветки и сбросят недопустимые значения. В случае больших if() тел или большого количества циклов, которые могут быть критическими.
sqr() и sqrt() на современных процессорах Intel являются единой встроенной инструкцией и не медленны, но они неточны, а регистры загрузки также занимают время.
Связанный с этим вопрос: Почему инструкция ветвления процессора медленная?
Скорее всего, профессор хотел, чтобы студент проводил исследования по этому вопросу, это полупровокативный вопрос\задача, который будет делать только хорошо, если бы учащийся научился самостоятельно мыслить и искать дополнительные источники.
Я делаю ретро-графическое программирование на C для 8088/8086, а вызов abs() занимает много времени, поэтому я заменил его на:
/* assuming 'i' is int; this WILL NOT WORK on floating point */
if (i < 0) {
i = ~i + 1;
}
Причина, по которой это происходит быстрее, заключается в том, что она по существу торгует CALL в сборке для JNE. Вызов метода изменяет пару регистров, подталкивает еще несколько, вставляет аргументы в стек и может очищать очередь предварительной выборки. Кроме того, эти действия необходимо поменять местами в конце функции, и все это очень дорого для процессора.
Для списка отрицательных чисел:
если в памяти хранится ноль, просто используйте 0 - x, где x - отрицательное число.
Или, если в памяти нет нуля:
x-x-x, где x - отрицательное число.
Или с помощью скобок для ясности:
(x) - (x) - (x) => (-n) - (-n) - (-n), где x = -n
т.е. вычтите отрицательное число из себя, чтобы получить ноль, затем вычтите его из нуля.