Набор против производительности Frozenset

Question

Я возился с питоном set а также frozenset типы коллекций.

Первоначально я предполагал, что frozenset обеспечит лучшую производительность поиска, чем set, поскольку его неизменный и, следовательно, может использовать структуру хранимых предметов.

Однако, похоже, что это не так в отношении следующего эксперимента:

import random
import time
import sys

def main(n):
    numbers = []
    for _ in xrange(n):
        numbers.append(random.randint(0, sys.maxint))
    set_ = set(numbers)
    frozenset_ = frozenset(set_)

    start = time.time()
    for number in numbers:
        number in set_
    set_duration = time.time() - start

    start = time.time()
    for number in numbers:
        number in frozenset_
    frozenset_duration = time.time() - start

    print "set      : %.3f" % set_duration
    print "frozenset: %.3f" % frozenset_duration


if __name__ == "__main__":
    n = int(sys.argv[1])
    main(n)

Я выполнил этот код, используя как CPython, так и PyPy, что дало следующие результаты:

> pypy set.py 100000000
set      : 6.156
frozenset: 6.166

> python set.py 100000000
set      : 16.824
frozenset: 17.248

Кажется, что frozenset на самом деле медленнее в отношении производительности поиска, как в CPython, так и в PyPy. У кого-нибудь есть идея, почему это так? Я не смотрел в реализации.

Answer 1

frozenset а также set реализации в основном являются общими; set это просто frozenset с добавленными методами мутации с точно такой же реализацией хеш-таблицы. Увидеть Objects/setobject.c исходный файл; верхний уровень PyFrozenSet_Type определение разделяет функции с PySet_Type определение.

Здесь нет оптимизации для морозильника, так как нет необходимости вычислять хэши для элементов в frozenset когда вы тестируете на членство. Элемент, который вы используете для проверки набора, все еще нуждается в вычислении его хеша, чтобы найти правильный слот в хеш-таблице набора, чтобы вы могли выполнить тест на равенство.

Таким образом, ваши временные результаты, вероятно, отключены из-за других процессов, работающих в вашей системе; Вы измерили время настенных часов и не отключили сборку мусора в Python, а также неоднократно проверяли одно и то же.

Попробуйте запустить тест, используя timeit модуль, с одним значением из numbers и один не в наборе:

import random
import sys
import timeit

numbers = [random.randrange(sys.maxsize) for _ in range(10000)]
set_ = set(numbers)
fset = frozenset(numbers)
present = random.choice(numbers)
notpresent = -1
test = 'present in s; notpresent in s'

settime = timeit.timeit(
    test,
    'from __main__ import set_ as s, present, notpresent')
fsettime = timeit.timeit(
    test,
    'from __main__ import fset as s, present, notpresent')

print('set      : {:.3f} seconds'.format(settime))
print('frozenset: {:.3f} seconds'.format(fsettime))

Это повторяет каждый тест 1 миллион раз и производит:

set      : 0.050 seconds
frozenset: 0.050 seconds

Answer 2

Причина двух разных типов данных не в производительности, а в функциональности. Поскольку frozensets являются неизменными, они могут быть использованы в качестве ключа в словарях. Наборы не могут быть использованы для этой цели.