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

  • sqlite3.ProgrammingError: Неправильное количество подключений
  • Ошибка при использовании Python freeze.py
  • Scrapy Spider: перезапустите паук, когда закончите
  • Регулярное соответствие для специальных элементов списка II
  • Python os.walk Сделать его поддержкой Unicode / UTF-8?
  • Если индекс списка существует, сделайте X
  • Объединение двух PDF-файлов
  • Объект «NoneType» не имеет атрибута «sendall» PYTHON
  • ImportError: нет модуля с именем extern
  • Как удалить скобки из строки python?
  • получить всех родителей узла xml с помощью python
  •  
    Interesting Posts for Van-Lav

    Matplotlib – рисунок гладкого круга в полярном сюжете

    Прочитайте небольшой случайный образец из большого CSV-файла в фрейм данных Python

    n-наибольшие элементы в последовательности (необходимо сохранить дубликаты)

    Переменные среды доступа из Python

    Подсчет и создание идеальных квадратов

    Делает ли Theano автоматическое развертывание для BPTT?

    SqlAlchemy: преобразовать унаследованный тип от одного к другому

    Python Ссылка на файл Iterator не итерации

    Многочисленные значения полей ввода Django с одинаковым именем

    Переустановка python на Mac OS 10.6 с другой версией gcc

    Python: как разрешать URL-адреса, содержащие «..»

    Сбой сервера daemon python во время обратного вызова всплывающего окна HTML с помощью asyncio websocket coroutines

    Какое поле модели использовать в Django для хранения значений долготы и широты?

    Флакон Python и способ отображения кода на веб-странице

    Python – случайная выборка из диапазона, избегая определенных значений

    Python - лучший язык программирования в мире.