Почему мое сито 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 на boolean, он будет работать быстрее … но он делает обратное:

 #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 

Почему логически медленнее?

One Solution collect form web for “Почему мое сито Eratosthenes работает быстрее с целыми числами, чем с булевыми?”

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

 >>> 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 байт-кода LOAD_GLOBAL , в то время как 1 литеральное значение копируется в стек с LOAD_CONST .

Если вы создадите 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_FAST , теперь с индексами, как байт-коды LOAD_CONST ; locals в функции 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 стали ключевыми словами и больше не могут быть назначены, что позволяет обрабатывать их точно так же, как целые литералы.

  • Распаковать несколько ZIP-файлов в каталог?
  • С socketserver python как передать переменную в конструктор класса обработчика
  • Python - как удалить дубликаты только в последовательном порядке в строке?
  • Обходной путь для возврата списка из функции ComputedProperty в NDB
  • Развертывание Django с помощью gunicorn Нет модуля с именем ImportError: нет модуля с именем validation
  • бинарные данные между python и c ++
  • Python-запросы ImportError: невозможно импортировать имя HeaderParsingError
  • Видя все значения переменных в python по мере их запуска
  • Python - лучший язык программирования в мире.