Это хорошая практика, чтобы заменить деление с умножением, когда это возможно?

73

Всякий раз, когда мне нужно деление, например, проверка условий, я хотел бы реорганизовать выражение деления на умножение, например:

Оригинальная версия:

if(newValue / oldValue >= SOME_CONSTANT)

Новая версия:

if(newValue >= oldValue * SOME_CONSTANT)

Потому что я думаю, что можно избежать:

  1. Деление на ноль

  2. Переполнение, когда oldValueочень мало

Это правильно? Есть ли проблема для этой привычки?

ocomfd
источник
41
Будьте осторожны, что с отрицательными числами две версии проверяют абсолютно разные вещи. Вы уверены в этом oldValue >= 0?
user2313067
37
В зависимости от языка (но прежде всего с C), независимо от оптимизации вы можете думать, что компилятор обычно может это сделать лучше, -ИЛИ- , имеет достаточно здравого смысла , чтобы не делать этого вообще.
Марк Беннингфилд
63
Никогда не бывает «хорошей практикой» всегда заменять код X кодом Y, когда X и Y не являются семантически эквивалентными. Но всегда полезно взглянуть на X и Y, включить мозг, подумать о требованиях , а затем принять решение, какой из двух вариантов является более правильным. И после этого вам также следует подумать о том, какие тесты необходимы для проверки правильности семантических различий.
Док Браун
12
@MarkBenningfield: Не важно, компилятор не может оптимизировать деление на ноль. «Оптимизация», о которой вы думаете, это «оптимизация скорости». ОП думает о другом виде оптимизации - избегании ошибок.
Slebetman
25
Точка 2 фальшивая. Исходная версия может переполняться при малых значениях, но новая версия может переполняться при больших значениях, поэтому ни один из них не является более безопасным в общем случае.
JacquesB

Ответы:

74

Два общих случая для рассмотрения:

Целочисленная арифметика

Очевидно, что если вы используете целочисленную арифметику (которая усекает), вы получите другой результат. Вот небольшой пример в C #:

public static void TestIntegerArithmetic()
{
    int newValue = 101;
    int oldValue = 10;
    int SOME_CONSTANT = 10;

    if(newValue / oldValue > SOME_CONSTANT)
    {
        Console.WriteLine("First comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("First comparison says it's not bigger.");
    }

    if(newValue > oldValue * SOME_CONSTANT)
    {
        Console.WriteLine("Second comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("Second comparison says it's not bigger.");
    }
}

Выход:

First comparison says it's not bigger.
Second comparison says it's bigger.

Арифметика с плавающей точкой

Помимо того факта, что деление может дать другой результат, когда оно делится на ноль (оно генерирует исключение, а умножение - нет), оно также может привести к несколько иным ошибкам округления и другому результату. Простой пример в C #:

public static void TestFloatingPoint()
{
    double newValue = 1;
    double oldValue = 3;
    double SOME_CONSTANT = 0.33333333333333335;

    if(newValue / oldValue >= SOME_CONSTANT)
    {
        Console.WriteLine("First comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("First comparison says it's not bigger.");
    }

    if(newValue >= oldValue * SOME_CONSTANT)
    {
        Console.WriteLine("Second comparison says it's bigger.");
    }
    else
    {
        Console.WriteLine("Second comparison says it's not bigger.");
    }
}

Выход:

First comparison says it's not bigger.
Second comparison says it's bigger.

Если вы мне не верите, вот Скрипка, которую вы можете выполнить и увидеть сами.

Другие языки могут отличаться; Имейте в виду, однако, что C #, как и многие языки, реализует стандартную библиотеку IEEE (IEEE 754) с плавающей запятой, поэтому вы должны получить те же результаты в других стандартизированных временах выполнения.

Заключение

Если вы работаете с нуля , вы, вероятно, в порядке.

Если вы работаете над унаследованным кодом, а приложение является финансовым или другим чувствительным приложением, которое выполняет арифметику и должно обеспечивать согласованные результаты, будьте очень осторожны при переключении между операциями. Если вам необходимо, убедитесь, что у вас есть модульные тесты, которые обнаружат любые незначительные изменения в арифметике.

Если вы просто делаете такие вещи, как подсчет элементов в массиве или другие общие вычислительные функции, вы, вероятно, будете в порядке. Однако я не уверен, что метод умножения делает ваш код более понятным.

Если вы реализуете алгоритм в спецификации, я бы вообще ничего не изменил, не только из-за проблемы округления ошибок, но и чтобы разработчики могли просмотреть код и отобразить каждое выражение обратно в спецификацию, чтобы убедиться, что реализации нет. недостатки.

Джон Ву
источник
41
Второй финансовый бит. Этот тип переключателя просит, чтобы бухгалтеры преследовали вас вилами. Я помню 5000 строк, где мне приходилось прикладывать больше усилий, чтобы держать вилы в страхе, чем в поиске «правильного» ответа - что на самом деле было немного ошибочным. Отклонение на 0,01% не имело значения, абсолютно последовательные ответы были обязательными. Таким образом, я был вынужден сделать расчет таким образом, чтобы вызвать систематическую ошибку округления.
Лорен Печтел
8
Подумайте о покупке 5 центовых конфет (а их больше не существует). Купите 20 штук, «правильный» ответ не облагается налогом, поскольку не было налога на 20 покупок одной штуки.
Лорен Печтел
24
@LorenPechtel, это потому, что большинство налоговых систем включают правило (по очевидным причинам), что налог взимается за транзакцию, и налог должен взиматься с шагом, не меньшим, чем наименьшая монета в мире, а дробные суммы округляются в пользу налогоплательщика. Эти правила являются «правильными», потому что они законны и последовательны. Бухгалтеры с вилами, вероятно, знают, какие на самом деле правила, а не программисты (если только они не опытные бухгалтеры). Ошибка 0,01%, вероятно, приведет к ошибке балансировки, и иметь ошибку балансировки незаконно.
Стив
9
Поскольку раньше я никогда не слышал термин « зеленое поле» , я его искал. Википедия говорит, что это «проект, в котором отсутствуют какие-либо ограничения, налагаемые предыдущей работой».
Хенрик Рипа
9
@Steve: Мой босс недавно противопоставил «зеленое поле» «коричневому». Я заметил, что некоторые проекты больше похожи на «черные поля» ... :-D
DevSolar
25

Мне нравится ваш вопрос, поскольку он потенциально охватывает много идей. В целом, я подозреваю, что ответ - это зависит , вероятно, от задействованных типов и возможного диапазона значений в вашем конкретном случае.

Мой первоначальный инстинкт - размышлять о стиле , т.е. Ваша новая версия менее понятна читателю вашего кода. Я полагаю, мне придется подумать секунду или две (или, возможно, дольше), чтобы определить намерение вашей новой версии, тогда как ваша старая версия сразу станет понятной. Читаемость является важным атрибутом кода, поэтому в вашей новой версии есть цена.

Вы правы, что новая версия избегает деления на ноль. Конечно, вам не нужно добавлять охрану (по линии if (oldValue != 0)). Но имеет ли это смысл? Ваша старая версия отражает соотношение между двумя числами. Если делитель равен нулю, то ваше соотношение не определено. Это может быть более значимым в вашей ситуации, т.е. Вы не должны давать результат в этом случае.

Защита от переполнения является дискуссионной. Если вы знаете, что newValueвсегда больше, чем oldValue, то, возможно, вы могли бы сделать этот аргумент. Однако могут быть случаи, когда (oldValue * SOME_CONSTANT)также будут переполнены. Так что я не вижу здесь большого выигрыша.

Может быть аргумент, что вы получаете лучшую производительность, потому что умножение может быть быстрее, чем деление (на некоторых процессорах). Тем не менее, должно быть много расчетов, подобных этим, чтобы получить значительный выигрыш, т.е. остерегайтесь преждевременной оптимизации.

Размышляя над всем вышеизложенным, в целом, я не думаю, что можно получить что-то большее с вашей новой версией по сравнению со старой версией, особенно с учетом снижения ясности. Однако могут быть конкретные случаи, когда есть некоторая выгода.

Дейв
источник
16
Эмм, произвольное умножение, являющееся более эффективным, чем произвольное деление, в действительности не зависит от процессора для реальных машин.
Дедупликатор
1
Существует также проблема целочисленных и арифметических операций с плавающей точкой. Если отношение является дробным, деление должно выполняться с плавающей запятой, требующей приведения. Пропуск актерского состава вызовет непреднамеренную ошибку. Если дробь оказывается отношением двух небольших целых чисел, то их перестановка позволяет проводить сравнение в целочисленной арифметике. (В этот момент ваши аргументы будут применены.)
rwong
@ rwong Не всегда. Некоторые языки делят целочисленное деление, отбрасывая десятичную часть, поэтому приведение не требуется.
Т. Сар - Восстановить Монику
@ T.Sar Техника, которую вы описываете, и семантика, описанная в ответе, разные. Семантика заключается в том, намерен ли программист получить ответ с плавающей запятой или дробным значением; Техника, которую вы описываете, - это деление на обратное умножение, которое иногда является идеальным приближением (заменой) для целочисленного деления. Последний метод обычно применяется, когда делитель известен заранее, потому что вывод целочисленного значения (сдвинутый на 2 ** 32) может быть выполнен во время компиляции. Делать это во время выполнения было бы не выгодно, потому что это дороже процессора.
Руонг
22

Нет.

Вероятно, я бы назвал эту преждевременную оптимизацию в широком смысле, независимо от того, оптимизируете ли вы производительность , как обычно относится эта фраза, или что-либо еще, что можно оптимизировать, например, счетчик ребер , строки кода или в более широком смысле, такие вещи, как «дизайн».

Реализация такого рода оптимизации в качестве стандартной операционной процедуры подвергает риску семантику вашего кода и потенциально скрывает границы. Крайние случаи, которые вы считаете целесообразными для бесшумного устранения, в любом случае, возможно, должны быть явно рассмотрены . И бесконечно легче отлаживать проблемы вокруг шумных краев (тех, которые генерируют исключения), а не тех, которые молча терпят неудачу.

И в некоторых случаях даже выгодно «деоптимизировать» ради читабельности, ясности или ясности. В большинстве случаев ваши пользователи не заметят, что вы сохранили несколько строк кода или циклов ЦП, чтобы избежать обработки крайних случаев или обработки исключений. С другой стороны, неловкий или молчаливый код будет влиять на людей - по крайней мере, на ваших коллег. (А также, следовательно, стоимость создания и поддержки программного обеспечения.)

По умолчанию все, что является более «естественным» и читаемым в отношении домена приложения и конкретной проблемы. Держите это простым, явным и идиоматическим. Оптимизируйте по мере необходимости для получения значительных выгод или для достижения законного порога юзабилити.

Также обратите внимание: компиляторы часто оптимизируют деление для вас в любом случае - когда это безопасно .

svidgen
источник
11
-1 Этот ответ не совсем подходит к вопросу, который касается потенциальных ловушек деления - ничего общего с оптимизацией
Бен Коттрелл
13
@BenCottrell Это идеально подходит. Подводный камень заключается в том, что ценность бессмысленной оптимизации производительности снижается за счет удобства обслуживания. Из вопроса "есть ли проблема для этой привычки?" - да. Это быстро приведет к написанию абсолютной тарабарщины.
Майкл
9
@ Майкл, вопрос также не задает ни о одной из этих вещей - он конкретно спрашивает о правильности двух разных выражений, каждое из которых имеет разную семантику и поведение, но оба предназначены для соответствия одному и тому же требованию.
Бен Коттрелл
5
@BenCottrell Возможно, вы могли бы указать мне, где в вопросе есть упоминание о правильности?
Майкл
5
@BenCottrell Вы должны были просто сказать «Я не могу» :)
Майкл
13

Используйте тот, который менее глючит и имеет более логичный смысл.

Обычно деление на переменную в любом случае является плохой идеей, так как обычно делитель может быть нулевым.
Деление на константу обычно просто зависит от логического значения.

Вот несколько примеров, чтобы показать, что это зависит от ситуации:

Деление хорошее:

if ((ptr2 - ptr1) >= n / 3)  // good: check if length of subarray is at least n/3
    ...

Умножение плохое:

if ((ptr2 - ptr1) * 3 >= n)  // bad: confusing!! what is the intention of this code?
    ...

Умножение хорошо:

if (j - i >= 2 * min_length)  // good: obviously checking for a minimum length
    ...

Разделение плохое:

if ((j - i) / 2 >= min_length)  // bad: confusing!! what is the intention of this code?
    ...

Умножение хорошо:

if (new_length >= old_length * 1.5)  // good: is the new size at least 50% bigger?
    ...

Разделение плохое:

if (new_length / old_length >= 2)  // bad: BUGGY!! will fail if old_length = 0!
    ...
Mehrdad
источник
2
Я согласен, что это зависит от контекста, но ваши первые две пары примеров крайне скудны. Я не предпочел бы одно над другим в любом случае.
Майкл
6
@Michael: Хм ... ты находишь, (ptr2 - ptr1) * 3 >= nчто его так же легко понять, как выражение ptr2 - ptr1 >= n / 3? Это не заставит твой мозг сломаться и вернуться, пытаясь расшифровать смысл утроения различий между двумя указателями? Если это действительно очевидно для вас и вашей команды, тогда я полагаю, что для вас это больше; Я просто должен быть в медленном меньшинстве.
Мердад
2
Вызываемая переменная nи произвольное число 3 сбивают с толку в обоих случаях, но, замененные разумными именами, нет, я не нахожу ни одну более запутывающей, чем другую.
Майкл
1
Эти примеры не очень плохие ... определенно не «очень плохие» - даже если вы используете «разумные имена», они все равно будут иметь меньше смысла, когда вы меняете их на плохие дела. Если бы я был новичком в проекте, я бы предпочел увидеть «хорошие» случаи, перечисленные в этом ответе, когда я решил исправить производственный код.
Джон-М
3

Делать что-либо «по возможности» очень редко хорошая идея.

Ваш приоритет номер один должен быть правильностью, сопровождаемой удобочитаемостью и ремонтопригодностью. Слепая замена деления на умножение, когда это возможно, часто приводит к сбою в отделе правильности, иногда только в редких случаях, и поэтому трудно найти случаи.

Делайте то, что правильно и наиболее читабельно. Если у вас есть веские доказательства того, что написание кода наиболее читабельным способом вызывает проблемы с производительностью, вы можете рассмотреть возможность его изменения. Уход, математика и кодовые обзоры - ваши друзья.

gnasher729
источник
1

Что касается читабельности кода, я думаю, что умножение на самом деле более читабельно в некоторых случаях. Например, если есть что-то, что вы должны проверить newValue, увеличилось ли оно на 5 или более процентов выше oldValue, тогда 1.05 * oldValueесть порог, по которому нужно тестировать newValue, и естественно написать

    if (newValue >= 1.05 * oldValue)

Но остерегайтесь отрицательных чисел при рефакторинге вещей таким образом (либо заменяя деление умножением, либо заменяя умножение делением). Два условия, которые вы рассматривали, эквивалентны, если oldValueгарантированно не будет отрицательным; но предположим, что newValueна самом деле -13,5 и oldValue-10,1. затем

newValue/oldValue >= 1.05

оценивается как истина , но

newValue >= 1.05 * oldValue

оценивается как ложное .

Дэвид К
источник
1

Обратите внимание на знаменитое разделение по инвариантным целым числам с использованием умножения .

Компилятор фактически делает умножение, если целое число инвариантно! Не разделение. Это происходит даже для не степеней 2 значения. Сила 2 делений использует явно битовые сдвиги и поэтому еще быстрее.

Однако для неинвариантных целых чисел вы обязаны оптимизировать код. Перед оптимизацией убедитесь, что вы действительно оптимизируете настоящее узкое место, и что правильность не жертвуется. Остерегайтесь переполнения целых чисел.

Я забочусь о микрооптимизации, поэтому я, вероятно, взгляну на возможности оптимизации.

Подумайте также об архитектуре, на которой работает ваш код. Особенно ARM имеет крайне медленное деление; вам нужно вызвать функцию для деления, в ARM нет инструкции деления.

Кроме того, как я выяснил , на 32-битных архитектурах 64-битное деление не оптимизировано .

juhist
источник
1

Подняв вашу точку 2, она действительно предотвратит переполнение очень маленького размера oldValue. Однако, если SOME_CONSTANTон также очень мал, то ваш альтернативный метод в конечном итоге окажется с недостаточным значением, где значение не может быть точно представлено

И наоборот, что будет, если oldValueоно очень большое? У вас те же проблемы, только наоборот.

Если вы хотите избежать (или минимизировать) риск переполнения / недополнения, лучший способ - проверить, newValueявляется ли он наиболее близким по величине к oldValueили к SOME_CONSTANT. Затем вы можете выбрать соответствующую операцию деления, либо

    if(newValue / oldValue >= SOME_CONSTANT)

или же

    if(newValue / SOME_CONSTANT >= oldValue)

и результат будет наиболее точным.

Для деления на ноль, по моему опыту, это почти никогда не подходит для «решения» в математике. Если у вас есть деление на ноль в ваших непрерывных проверках, то почти наверняка у вас есть ситуация, которая требует некоторого анализа, и любые вычисления, основанные на этих данных, не имеют смысла. Явная проверка деления на ноль почти всегда является подходящим ходом. (Обратите внимание, что здесь я говорю «почти», потому что я не претендую на непогрешимость. Я просто отмечу, что я не помню, чтобы видел веские причины для этого через 20 лет написания встроенного программного обеспечения, и продолжаю .)

Однако, если у вас есть реальный риск переполнения / недополнения в вашем приложении, то это, вероятно, не правильное решение. Скорее всего, вам следует обычно проверять числовую стабильность вашего алгоритма или, возможно, просто переходить к более точному представлению.

И если у вас нет доказанного риска переполнения / недостаточного заполнения, то вы ни о чем не беспокоитесь. Это означает, что вы буквально должны доказать, что вам это нужно, с цифрами, в комментариях рядом с кодом, который объясняет сопровождающему, почему это необходимо. Как главный инженер, проверяющий чужой код, если бы я столкнулся с кем-то, кто прилагал дополнительные усилия, я лично не согласился бы на меньшее. Это своего рода противоположность преждевременной оптимизации, но обычно она имеет одну и ту же основную причину - одержимость деталями, которая не имеет функциональной разницы.

Грэхем
источник
0

Инкапсулируйте условную арифметику в значимых методах и свойствах. Мало того, что хорошее именование скажет вам, что означает «A / B» , проверка параметров и обработка ошибок также могут быть аккуратно скрыты.

Важно отметить, что поскольку эти методы состоят из более сложной логики, внешняя сложность остается очень управляемой.

Я бы сказал, что замена умножения кажется разумным решением, потому что проблема плохо определена.

radarbob
источник
0

Я думаю, что не может быть хорошей идеей заменить умножения на деления, потому что процессор ALU (Arithmetic-Logic Unit) выполняет алгоритмы, хотя они реализованы аппаратно. Более сложные методы доступны в новых процессорах. Обычно процессоры стремятся распараллелить операции пар битов, чтобы минимизировать требуемые тактовые циклы. Алгоритмы умножения можно распараллелить довольно эффективно (хотя требуется больше транзисторов). Алгоритмы деления не могут быть распараллелены так эффективно. Самые эффективные алгоритмы деления довольно сложны. Как правило, они требуют больше тактов на бит.

Ишан шах
источник