E 'possibile dare a Python una capacità iniziale (ed è utile)

Question

Sto riempiendo un ditt di pitone con circa 10.000.000 di oggetti. La mia comprensione di dict (o hashtables) è che quando ci sono troppi elementi in essi, la necessità di ridimensionare, un'operazione che costa parecchio tempo.

C'è un modo per dire a un python dict che verranno memorizzati almeno n elementi in esso, in modo che possa allocare memoria dall'inizio? O questa ottimizzazione non farà bene alla mia velocità di marcia?

(E no, non ho verificato che la lentezza del mio piccolo script è a causa di questo, io in realtà non sarebbe ora come fare. Questo è comunque qualcosa che vorrei fare in Java, impostare la capacità iniziale di il diritto HashSet)

Answer 1

Prima di tutto, ho sentito dire che è possibile impostare la dimensione di un dizionario all'inizializzazione, ma non ho mai visto alcuna documentazione o PEP che descrivono come ciò sarebbe stato fatto.

Con questo in mente ho eseguito un'analisi sulla quantità di articoli, descritta di seguito. Mentre potrebbe essere necessario del tempo per ridimensionare il dizionario ogni volta, consiglierei di andare avanti senza preoccuparsi di questo, almeno fino a quando non potrai testarne le prestazioni.

Le due regole che ci riguardano nel determinare il ridimensionamento sono il numero di elementi e il fattore di ridimensionamento. Un dizionario si ridimensionerà quando sarà pieno per 2/3 sull'aggiunta dell'elemento mettendolo sopra il segno 2/3. Al di sotto di 50.000 elementi aumenterà di un fattore 4, superiore a tale importo di un fattore 2. Usando la tua stima di 10.000.000 di elementi (tra 2^23 e 2^24) il tuo dizionario si ridimensionerà 15 volte (7 volte sotto 50k, 8 volte sopra). Un altro ridimensionamento si sarebbe verificato appena oltre 11.100.000.

Il ridimensionamento e la sostituzione degli elementi correnti nella tabella di hashing richiedono un po 'di tempo, ma mi chiedo se lo si noterà con qualsiasi altra cosa si stia verificando nel codice vicino. Ho appena messo insieme una suite temporizzazione confronto inserti a cinque posti lungo ciascun contorno da dimensioni del dizionario di 2^3 a 2^24, e le aggiunte "confine" media 0,4 nanosecondi più lungo delle aggiunte "non confinanti". Questo è più lungo dello 0,17% ... probabilmente accettabile. Il minimo per tutte le operazioni era 0.2085 microsecondi e il massimo era 0,2412 microsecondi.

Spero che questo sia interessante, e se controlli la performance del tuo codice per favore segui una modifica! La mia risorsa primaria per interni Dictionary E 'stato lo splendido discorso tenuto da Brandon Rhodes a PyCon 2010: The Mighty Dictionary

Answer 2

Sì, è possibile ed ecco una soluzione che ho trovato in questione di un'altra persona che è legato al tuo troppo:

d = {} 
for i in xrange(4000000): 
d[i] = None 
# 722ms 

d = dict(itertools.izip(xrange(4000000), itertools.repeat(None))) 
# 634ms 

dict.fromkeys(xrange(4000000)) 
# 558ms 

s = set(xrange(4000000)) 
dict.fromkeys(s) 
# Not including set construction 353ms 

questi sono diversi modi per inizializzare un dizionario con una certa dimensione.