Set vs. prestazioni frozenset

Question

Mi sono occupato del lavoro con i tipi di raccolta set e frozenset di Python.

Inizialmente, ho assunto che frozenset fornirebbe prestazioni di ricerca migliori rispetto a set, come immutabile e quindi potrebbe sfruttare la struttura degli elementi memorizzati.

Tuttavia, questo non sembra essere il caso, per quanto riguarda il seguente esperimento:

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) 

ho eseguito questo codice utilizzando sia CPython e PyPy, che ha dato i seguenti risultati:

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

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

Sembra che frozenset sia effettivamente più lento per quanto riguarda le prestazioni di ricerca, sia in CPython che in PyPy. Qualcuno ha un'idea del perché questo è il caso? Non ho esaminato le implementazioni.

Answer 1

Le implementazioni frozenset e set sono ampiamente condivise; a set è semplicemente un frozenset con metodi di mutazione aggiunti, con la stessa implementazione di hashtable. Vedi lo Objects/setobject.c source file; le funzioni condivise PyFrozenSet_Type definition di livello superiore con PySet_Type definition.

Non c'è ottimizzazione per un frozenset qui, in quanto non v'è alcuna necessità di calcolare gli hash per le voci nel il frozenset quando si esegue il test per l'adesione. L'elemento che si utilizza per testare rispetto a, il set deve ancora calcolare il proprio hash, per trovare lo slot corretto nella serie di hash, in modo da poter eseguire un test di uguaglianza.

In questo modo, i risultati di temporizzazione sono probabilmente disattivati ​​a causa di altri processi in esecuzione sul sistema; hai misurato il tempo di wall-clock e non hai disattivato la garbage collection di Python né hai ripetutamente testato la stessa cosa.

Provare a eseguire il test utilizzando il timeit module, con un valore da numbers e non nel set:

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)) 

Questo si ripete ogni test 1 milione di volte e produce:

set  : 0.050 seconds 
frozenset: 0.050 seconds