Каков предпочтительный способ взять модуль с силой 2 из int в Python

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

field_value = counter % 2 ** n 

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

 field_value = counter % (1 << n) field_value = counter & (1 << n) - 1 field_value = counter & ~(-1 << 8) 

Каким образом опытные программисты Python предпочитают реализовать такое требование, пытаясь максимизировать ясность кода, не жертвуя слишком высокой производительностью?

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

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

Говоря о производительности, на самом деле вам не нужно слишком беспокоиться об этом в Python. Поскольку сама работа с самим объектом Python достаточно дорога, делая это в числовых операциях или побитовых операциях, это просто не имеет значения. Здесь я объясняю это визуально

 <-------------- Python object operation cost --------------><- bit op -> <-------------- Python object operation cost --------------><----- num op -----> 

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

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

  1. Напишите логику в модуле C / C ++ для Python, вы можете использовать такую ​​библиотеку, как Boost.Python
  2. Используйте стороннюю библиотеку для обработки массового числа, например numpy

вы должны просто выбросить верхние биты.

 #field_value = counter & (1 << n) - 1 field_value = counter & ALLOWED_BIT_WIDTH 

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

«Ограничение» в протоколе – это способ ограничения полосы пропускания служебной информации, необходимой протоколу.

Вероятно, он будет зависеть от реализации python, но в CPython 2.6 он выглядит так:

 In [1]: counter = 0xfedcba9876543210 In [10]: %timeit counter % 2**15 1000000 loops, best of 3: 304 ns per loop In [11]: %timeit counter % (1<<15) 1000000 loops, best of 3: 302 ns per loop In [12]: %timeit counter & ((1<<15)-1) 10000000 loops, best of 3: 104 ns per loop In [13]: %timeit counter & ~(1<<15) 10000000 loops, best of 3: 170 ns per loop 

В этом случае counter & ((1<<15)-1) является явным победителем. Интересно, что 2**15 и 1<<15 принимают одинаковое количество времени (более или менее); Я предполагаю, что Python внутренне оптимизирует этот случай и 2 ** 15 -> 1 << 15 в любом случае.

Я как-то написал класс, который позволяет вам просто сделать это:

  bc = BitSliceLong(counter) bc = bc[15:0] 

полученное из long, но это более общая реализация (позволяет использовать любой диапазон бит, а не только x: 0), и дополнительные накладные расходы для этого делают его медленнее на порядок, хотя он использует тот же метод внутри.

Изменить: BTW, предварительное вычисление значений не дает никакой пользы – доминирующим фактором здесь является не фактическая математическая операция. Если мы это сделаем

 cx_mask = 2**15 counter % cx_mask 

время такое же, как и при вычислении 2 ** 15. Это справедливо и для нашего «наилучшего случая» – предварительное вычисление ((1 << 15) -1) не имеет никакой пользы.

Кроме того, в предыдущем случае я использовал большое число, которое реализовано как long в python. На самом деле это не родной тип – он поддерживает произвольные номера длин, поэтому ему нужно обрабатывать практически все, поэтому реализация операций – это не только один вызов ALU – он включает в себя серию операций смещения бит и арифметики.

Если вы можете сохранить счетчик ниже sys.maxint , sys.maxint этого вы будете использовать типы int , и они оба выглядят быстрее, а также более доминируют в действительном математическом коде:

 In [55]: %timeit x % (1<<15) 10000000 loops, best of 3: 53.6 ns per loop In [56]: %timeit x & ((1<<15)-1) 10000000 loops, best of 3: 49.2 ns per loop In [57]: %timeit x % (2**15) 10000000 loops, best of 3: 53.9 ns per loop 

Все они примерно одинаковы, поэтому не имеет значения, какой из них вы используете здесь. (мода немного медленнее, но в пределах случайного изменения). Для div / mod имеет смысл быть дорогостоящей операцией на очень больших числах, с более сложным алгоритмом, тогда как для «малых» ints это может быть сделано на аппаратном уровне.