Я рисовал с помощью Python's set
и frozenset
типов коллекций.Набор против производительности 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. У кого-нибудь есть идея, почему это так? Я не рассматривал реализации.
«, как его неизменным и, следовательно, может использовать структуру хранимых предметов »- что именно вы ожидали от этого? Любая структура, к которой он имеет доступ, имеет значение 'set'. – user2357112
Ну, вот что я прошу. Я думал, что, возможно, frozenset может использовать какую-то предварительно вычисленную хеш-функцию, которая, в свою очередь, может обеспечить лучшую производительность поиска. –
Вам нужно рассчитать хэш любого элемента, который вы ищете, период. Вы не можете прекомпилировать хеши здесь, так как вы можете протестировать произвольный элемент против набора. Я не уверен, как вы оцениваете эту оптимизацию? Элементы * в * наборе не нужно вычислять свой хэш; они уже вставлены в хэш-таблицу. –