Salve a tutti di nuovo,
se definisco un semplice Fibonacci con una cache (volutamente un po'
stupida):
def _fib(n, cache):
cached = cache[n]
if cached != -1:
return cached
res = _fib(n-1, cache) + _fib(n-2, cache)
cache[n] = res
return res
def dfib(n):
cache = {i:-1 for i in range(n+1)}
cache[0] = cache[1] = 1
return _fib(n, cache)
... %timeit dfib(91) mi dà "29.6 µs per loop". Se la cache invece che
un dict è un numpy.array, come in
def afib(n):
cache = -ones(shape=n+1, dtype=int64)
cache[0] = cache[1] = 1
return _fib(n, cache)
... %timeit afib(91) mi dà invece "53.2 µs per loop". E va bene che il
dizionario Python è una struttura efficiente, ma... è sempre una hash
table più un indexing, come fa a battere un semplice indexing?! Riesco
ad abbassare a "46.7 µs per loop" se sostituisco
if cached != -1:
con
if cached != EMPTY:
dove ho precedentemente definito
EMPTY = np.int64(-1)
... ma resta il fatto (verificato con %lprun) che "cached = cache[n]" è più
veloce quando cache è un dizionario (~0.3 µs) che quando è un array (~0.4 µs).
Ciò umilia quel briciolo di comprensione delle strutture di dati che credevo di
avere. Qualcuno sa illuminarmi?
(per la cronaca: la cosa l'ho notata in un algoritmo in cui la cache era molto
più grande, e con indici non interi ma tuple di interi)
Pietro
_______________________________________________
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
