Вопрос по performance, python – Является ли & быстрее, чем% при проверке нечетных чисел?

27

Чтобы проверить нечетное и четное целое число, является ли проверка младшего бита более эффективной, чем по модулю?

>>> def isodd(num):
        return num & 1 and True or False

>>> isodd(10)
False
>>> isodd(9)
True
Если вы пытаетесь получить логический результат, просто выполните bool (num & 1) FogleBird
Что с "и верно или неверно"? FogleBird
"0 - правда, а 1 - ложь" ?! Теперь это будет ИНТЕРЕСНЫЙ язык для программирования, действительно ... !!! Alex Martelli
Я использую Python 3.1 riza
Я облажался. В Python 0 ЛОЖНО и 1 ИСТИНА. (Но в * nix коды выхода 0 указывают на успех. Bash действительно интересен.) eksortso

Ваш Ответ

8   ответов
59

Ага.timeitодуль @ в стандартной библиотеке - это то, как вы проверяете эти вещи. Например

AmAir:stko aleax$ python -mtimeit -s'def isodd(x): x & 1' 'isodd(9)'
1000000 loops, best of 3: 0.446 usec per loop
AmAir:stko aleax$ python -mtimeit -s'def isodd(x): x & 1' 'isodd(10)'
1000000 loops, best of 3: 0.443 usec per loop
AmAir:stko aleax$ python -mtimeit -s'def isodd(x): x % 2' 'isodd(10)'
1000000 loops, best of 3: 0.453 usec per loop
AmAir:stko aleax$ python -mtimeit -s'def isodd(x): x % 2' 'isodd(9)'
1000000 loops, best of 3: 0.461 usec per loop

Как вы видите, на моем (первый день == старый == медленный ;-) Macbook Air,& решение повторяется на 7–18 наносекунд быстрее, чем% решение

timeit не только говорит вам, что быстрее, но и на сколько (просто запустите тесты несколько раз), что обычно показывает, насколько это неважно (выдействительн беспокоиться о разнице в 10 наносекунд, когда накладные расходы на вызов функции составляют около 400?! -) ...

Убедить программистов в том, что микрооптимизация, по сути, не имеет значения, оказалось невозможной задачей - даже несмотря на то, что прошло 35 лет (за которые компьютеры стали на порядок быстрее!) С момента Кнута Написал

Мы должны забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация - корень всего зла.

который, как он объяснил, является цитатой из еще более старого заявления Хоара. Я думаю, что все полностью убеждены, что их случай падает на оставшиеся 3%!

Так что вместо того, чтобы бесконечно повторять «это не имеет значения», мы (Тим Питерс, в частности, заслуживаем там почести) помещаем в стандартный модуль библиотеки Pythontimeit, что позволяет легко измерить такие микротесты и, таким образом, позволяет, по крайней мере,нескольк программисты убеждают себя, что, хм, этот случай попадает в группу 97%! -)

Нет, компилятор Python сам по себе оптимизирован, чтобы быть максимально простым, надежным и быстрым - он не выполняет оптимизацию, такую как изменение используемой операции (для которой он должен был бы вывести этоx всегда целое число, например). Попробуйте psyco, если вам нужна такая низкоуровневая оптимизация (т.е. если важна каждая наносекунда). Alex Martelli
Спасибо, что добавили замечание о неважности такой маленькой разницы. Даже выполняя вычисления сотни или даже тысячи раз, это, вероятно, одна из худших «оптимизаций», которую вы можете сделать - это не только ухудшает читабельность (IMO), но вы не получаете от этого ничего особенного. Я никогда не хочу платить больше, чем я получаю. Thomas Owens
О да, я забыл, что Python статически не напечатан. (верно?) Снова идет тревога невежества Python. GManNickG
@ Томас, я на самом деле неоднократно редактировал ответ, чтобы точно объяснить, насколько он не имеет значения, приведи цитату Кнута, объясни, почему мы поместили timeit в библиотеку, & c; но SO - это почти 100-ярдовый бросок, поэтому, чтобы узнать о нем любого представителя, я решил сначала найти решение, попробуйте позже. Похоже, на этот раз ваш выбор предоставить только проповеди, без кода или решения, выигрывает гонку повторений ;-). (Кстати, я не думаю, что & 1 или% 2 менее читабельны, чем другие, в этом случае). Alex Martelli
Предполагая, что любая заданная оптимизация преждевременна, является ошибкой Tibrogargan
23

Я не думаю, что это имеет значение.

Первая проблема - читабельность. Что имеет больше смысла для других разработчиков? Лично я бы ожидал по модулю при проверке четности / нечетности числа. Я ожидаю, что большинство других разработчиков ожидают того же. Внедряя другой, неожиданный метод, вы можете усложнить чтение кода и, следовательно, его обслуживание.

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

Я наполовину ожидаю отрицательного ответа по этому вопросу, но я думаю, что это важный момент для любого, кто задается этим (или другим подобным) вопросом, поэтому он останется. Thomas Owens
Нет, голосование против "за" ... Но в таких случаях это было решение Pythonic, чтобы профилировать "очевидные" варианты и отдавать предпочтение самым быстрым. Stan Graves
semiuseless: Я все еще изучаю Python, но лично я думаю, что оператор по модулю был бы более Pythonic просто потому, что вы делаете то, что ожидается. По крайней мере, для меня это намного очевиднее и яснее. Thomas Owens
Я с тобой об этом. Как сказал Дональд Кнут, «преждевременная оптимизация - корень всего зла Fernando
@ gutofb7: я дал полную цитатуа такж ссылка на PDF замечательной статьи Кнута (также, как я полагаю, первая статья, в которой отступы являются единственным средством обозначения блоков) в моем ответе за 8 минут до вашего комментария ;-). Кстати, в этом случае я считаю, что% 2 и & 1 имеют абсолютно эквивалентную читаемость (любой, кто не понимает поразрядно - и будет испытывать затруднения при понимании «%», который не имеет абсолютно никакого отношения к процентам, и т. Д .; Alex Martelli
10

которую вы можете получить - этон поставить тест в функцию.number % 2 'и' number & 1 '- это очень распространенные способы проверки нечетности / четности, опытные программисты сразу распознают шаблон, и вы всегда можете добавить комментарий, например: «# если число нечетное, тогда бла-бла-бла», если вы действительно нужно, чтобы это было очевидно.

# state whether number is odd or even
if number & 1:
    print "Your number is odd"
else:
    print "Your number is even"
Не могли бы вы объяснить, что делает% а также& делай в питоне? LWZ
как это число & 1 дает нечетное число? sam
4

вернуть num & 1 и True или False;? Вах! Если вы сошли с ума (1) «верните число и 1» (2), вставьте его:if somenumber % 2 == 1 разборчиво и бьетisodd(somenumber) потому что он избегает вызова функции Python.

Да, избегать вызова функции - большой выигрыш (хотя == 1 действительно избыточен) - избегая сокращения вызовов примерно на 300 наносекунд из 450 или около того, которые я измерял в своем ответе. Alex Martelli
4

[email protected] ~> python -mtimeit -s'9 % 2'
10000000 loops, best of 3: 0.0271 usec per loop
[email protected] ~> python -mtimeit -s'10 % 2'
10000000 loops, best of 3: 0.0271 usec per loop

[email protected] ~> python -mtimeit -s'9 & 1'
10000000 loops, best of 3: 0.0271 usec per loop
[email protected] ~> python -mtimeit -s'9 & 1'
10000000 loops, best of 3: 0.0271 usec per loop

[email protected] ~> python -mtimeit -s'def isodd(x): x % 2' 'isodd(10)'
1000000 loops, best of 3: 0.334 usec per loop
[email protected] ~> python -mtimeit -s'def isodd(x): x % 2' 'isodd(9)'
1000000 loops, best of 3: 0.358 usec per loop

[email protected] ~> python -mtimeit -s'def isodd(x): x & 1' 'isodd(10)'
1000000 loops, best of 3: 0.317 usec per loop
[email protected] ~> python -mtimeit -s'def isodd(x): x & 1' 'isodd(9)'
1000000 loops, best of 3: 0.319 usec per loop

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

Что если я использую лямбду для замены функции? isodd = лямбда-нум: num & 1 и True или False riza
1

он убирает очень идиоматическое «var% 2 == 0», которое каждый кодер понимает, не глядя дважды. Так что это нарушает питонов дзен, а также очень мало выгоды.

Кроме того a = b и True или False были заменены для лучшей читаемости

возвращают значение True, если num & 1 else False

1

Используя Python 3.6, ответе @ нет. Использование кода ниже на MBP 2017 показывает, что по модулю быстрее.

# odd.py
from datetime import datetime

iterations = 100_000_000


def is_even_modulo(n):
    return not n % 2


def is_even_and(n):
    return not n & 1


def time(fn):
    start = datetime.now()
    for i in range(iterations, iterations * 2):
        fn(i)
    print(f'{fn.__name__}:', datetime.now() - start)


time(is_even_modulo)
time(is_even_and)

Дает этот результат:

$ python3 -m odd
is_even_modulo: 0:00:14.347631
is_even_and: 0:00:17.476522
$ python3 --version
Python 3.6.1

Как указывалось в других ответах, вызовы функций - это большие издержки, однако их удаление показывает, что модуль по-прежнему быстрее, чем побитовый, и в Python 3.6.1:

# odd.py
from datetime import datetime

iterations = 100_000_000


def time_and():
    start = datetime.now()
    for i in range(iterations):
        i & 1 
    print('&:', datetime.now() - start)


def time_modulo():
    start = datetime.now()
    for i in range(iterations):
        i % 2
    print('%:', datetime.now() - start)


time_modulo()
time_and()

Полученные результаты

$ python3 -m odd
%: 0:00:05.134051
&: 0:00:07.250571

Bonus: оказывается, это занимает вдвое больше времени для запуска в Python 2.7.

$ time python2 -m odd
('&:', '0:00:20.169402')
('%:', '0:00:19.837755')

real    0m41.198s
user    0m39.091s
sys 0m1.899s
$ time python3 -m odd
&: 0:00:11.375059
%: 0:00:08.010738

real    0m19.452s
user    0m19.354s
sys 0m0.042s
0

что ни один из вышеприведенных ответов не сделал ни настройки переменных (литерал времени - это другая история), ни вызова функций (что явно скрывает «более низкие термины»). Застрял на этом времени из времени ipython, где я получил явный победитель x & 1 - лучше на ~ 18% при использовании python2.6 (~ 12% при использовании python3.1).

На моей очень старой машине:

$ python -mtimeit -s 'x = 777' 'x&1'
10000000 loops, best of 3: 0.18 usec per loop
$ python -mtimeit -s 'x = 777' 'x%2'
1000000 loops, best of 3: 0.219 usec per loop

$ python3 -mtimeit -s 'x = 777' 'x&1'
1000000 loops, best of 3: 0.282 usec per loop
$ python3 -mtimeit -s 'x = 777' 'x%2'
1000000 loops, best of 3: 0.323 usec per loop

Похожие вопросы