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

Question

Я рисовал с помощью Python's 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 в основном разделены; a set - это просто frozenset с добавленными методами мутации, с той же самой реализацией хэш-таблицы. См. Objects/setobject.c source file; функции верхнего уровня PyFrozenSet_Type definition функционируют с помощью PySet_Type definition.

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

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

Попробуйте запустить тест с использованием timeit module, с одним значением из 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