Эффективная проверка делимости печати

Question

В моей программе, когда я чувствую, что это занимает много времени, я реализую проверку прогресса: я печатаю текущее значение итератора и разницу во времени каждые n итераций, используя модуль 0 (if i % n == 0...).

Эффективно ли интерпретатор Python (или любой другой компилятор языка программирования) проверяет делимость на степени 2? Как взять последние биты (мощности) и проверить, все ли равны 0?

Answer 1

Глядя на отформатированный байт-код следующих лямбд, кажется, что нет никаких различий на уровне байт-кода в CPython:

In [1]: import dis

In [2]: dis.dis(lambda x: x % 3 == 0)
  1           0 LOAD_FAST                0 (x)
              2 LOAD_CONST               1 (3)
              4 BINARY_MODULO
              6 LOAD_CONST               2 (0)
              8 COMPARE_OP               2 (==)
             10 RETURN_VALUE

In [3]: dis.dis(lambda x: x % 2 == 0)
  1           0 LOAD_FAST                0 (x)
              2 LOAD_CONST               1 (2)
              4 BINARY_MODULO
              6 LOAD_CONST               2 (0)
              8 COMPARE_OP               2 (==)
             10 RETURN_VALUE

In [4]:

BINARY_MODULO (операция по модулю 2 параметра, то есть «двоичный»), в конечном итоге обрабатываются (для 2 целых чисел, AKA «longs») в CPython с помощью функции long_mod в Objects/longobject.c.

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

. Если этого не происходит, в итоге вызывается x_divrem, который содержит следующий комментарий:

/* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
       edn.), section 4.3.1, Algorithm D], except that we don't explicitly
       handle the special case when the initial estimate q for a quotient
       digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
       that won't overflow a digit. */

На самом деле я не хочу тратить время на понимание алгоритма из кода (и у меня нет упомянутой книги), но от просмотра его - похоже, он выполняет некоторые умные операции сдвига битов. Держу пари, что в тех случаях, когда делитель имеет степень двойки - этот алгоритм будет работать быстрее. Хотя не совсем уверен.

Вы можете проверить это здесь: https://github.com/python/cpython/blob/eb8ac57af26c4eb96a8230eba7492ce5ceef7886/Objects/longobject.c#L2712

Answer 2

Эффективность любой целочисленной операции в Python будет в лучшем случае сомнительной. Помимо накладных расходов интерпретатора, вы также оспариваете тот факт, что целые числа имеют переменную точность, требуя дополнительной обработки для каждой операции.

При этом вы можете использовать битовое перемешивание для проверки делимости на степень 2. Для данного n вы можете сделать

p = (1 <<  n) - 1 # n of your choice
...
if not i & p:
    ...

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