Странное время выполнения count () - PullRequest
Новая
       38

Странное время выполнения count ()

4 голосов
/ 22 января 2020

Код: 

from timeit import Timer
print(min(Timer('y=x.count(1)',setup='x=[1] * 1000').repeat(number=1000000))) 
print(min(Timer('y=x.count(0)',setup='x=[1] * 1000').repeat(number=1000000)))

Результаты на моей машине: 

0.7033228789223358
10.16116041096393

Может кто-нибудь объяснить почему первый случай намного быстрее, чем второй ? Я ожидал, что оба раза будут похожи.

1 Ответ

6 голосов
/ 22 января 2020

Это связано с тем, как вы построили свой объект списка: 

x = [1] * 1000

Это создает список только с одним объектом, на который ссылаются 1000 раз; умножение списка не создает копии значения. Чтобы понять, почему это важно, нам нужно посмотреть, как Python списки выполняют подсчет.

list.count() l oop может выглядеть следующим образом, быстрый Python перевод реализации написано в C: 

def count(self, value):
    count = 0
    for elem in self:
        if elem == value:
            count += 1
    return count

Это достаточно просто, верно? Однако это не совсем так; фактический код использует PyObject_RichCompareBool(), что первые тесты для идентификации объекта . Это действительно: 

if elem is value or elem == value:

Идентификационное тестирование (простой тест на равенство указателей) выполняется намного быстрее, когда все ваши элементы списка являются одним и тем же объектом : 

>>> import random
>>> v = random.randint(1000, 100000000)
>>> x = [v] * 1000
>>> all(value is v for value in x)
True

Вы можете воспроизвести это с любым случайным значением: 

>>> from timeit import Timer
min(Timer('y=x.count(v)',setup='import random; v = random.randint(1000, 10000000); x=[v] * 1000').repeat(number=100000))
0.2716284029884264
>>> min(Timer('y=x.count(w)',setup='import random; v = random.randint(1000, 10000000); x=[v] * 1000; w = v + 1').repeat(number=100000))
1.0827720829984173

Простое сравнение указателей перед проверкой на равенство значений имеет смысл, как показывают эти числа. Именно поэтому реализация Python интернирует некоторые часто используемые значения, такие как маленькие целые числа ( от -5 до 256, включительно ) или строковые значения, которые также являются допустимыми Python идентификаторами.

Это не сработало бы, если бы вы не использовали здесь маленькое целое число в качестве аргумента x.count(); потому что 1 интернирован, что x.count(1) использует объект, который также является членом списка; x[0] is 1 верно.

...