Подтвердить что ты не робот

Почему мое сито Eratosthenes работает быстрее с целыми числами, чем с булевыми?

Я написал простое сито из Eratosthenes, которое использует список из них и превращает их в нули, если не просто так:

def eSieve(n): #Where m is fixed-length list of all integers up to n
    '''Creates a list of primes less than or equal to n'''
    m = [1]*(n+1)
    for i in xrange(2,int((n)**0.5)+1):
        if m[i]:
            for j in xrange(i*i,n+1,i):
                m[j]=0
    return [i for i in xrange(2,n) if m[i]]

Я тестировал скорость, с которой он работал с %timeit, и получил:

#n: t
#10**1: 7 μs
#10**2: 26.6 μs
#10**3: 234 μs
#10**4: 2.46 ms
#10**5: 26.4 ms
#10**6: 292 ms
#10**7: 3.27 s

Я предположил, что если бы я изменил [1] и 0 на booleans, он будет работать быстрее... но он делает обратное:

#n: t
#10**1: 7.31 μs
#10**2: 29.5 μs
#10**3: 297 μs
#10**4: 2.99 ms
#10**5: 29.9 ms
#10**6: 331 ms
#10**7: 3.7 s

Почему булевы медленнее?

Ответ 1

Это происходит из-за того, что True и False рассматриваются как глобальные переменные в Python 2. Литералы 0 и 1 - это просто константы, искаженные быстрой ссылкой на массив, в то время как globals - это словарные запросы в глобальное пространство имен (попадание в пространство имен встроенных):

>>> import dis
>>> def foo():
...     a = True
...     b = 1
... 
>>> dis.dis(foo)
  2           0 LOAD_GLOBAL              0 (True)
              3 STORE_FAST               0 (a)

  3           6 LOAD_CONST               1 (1)
              9 STORE_FAST               1 (b)
             12 LOAD_CONST               0 (None)
             15 RETURN_VALUE

Значение True просматривается с помощью байт-кода LOAD_GLOBAL, в то время как литеральное значение 1 копируется в стек с помощью LOAD_CONST.

Если вы сделаете locals True и False, вы можете сделать их так же быстро:

def eSieve(n, True=True, False=False):
    m = [True]*(n+1)
    for i in xrange(2,int((n)**0.5)+1):
        if m[i]:
            for j in xrange(i*i,n+1,i):
                m[j]=False
    return [i for i in xrange(2,n) if m[i]]

Назначение True и False в качестве значений по умолчанию для аргументов дает функции эти имена как локальные, с одинаковыми значениями; снова используя упрощенную версию:

>>> def bar(True=True, False=False):
...     True == False
... 
>>> dis.dis(bar)
  2           0 LOAD_FAST                0 (True)
              3 LOAD_FAST                1 (False)
              6 COMPARE_OP               2 (==)
              9 POP_TOP             
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

Обратите внимание на коды операций LOAD_FAST, теперь с индексами, как и байт-коды LOAD_CONST; локали в функции CPython хранятся в массиве точно так же, как константы байткода.

С этим изменением выигрыш выигрывает, хотя и с небольшим отрывом; мои тайминги:

# n      integers  globals  locals
# 10**1  4.31 µs   4.2 µs   4.2 µs
# 10**2  17.1 µs   17.3 µs  16.5 µs
# 10**3  147 µs    158 µs   144 µs
# 10**4  1.5 ms    1.66 ms  1.48 ms
# 10**5  16.4 ms   18.2 ms  15.9 ms
# 10**6  190 ms    215 ms   189 ms   
# 10**7  2.21 s    2.47 s   2.18 s

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

Обратите внимание, что в Python 3, True и False стали ключевыми словами и больше не могут быть назначены, что позволяет обрабатывать их так же, как целые литералы.