[Python] Numpy.array e tempi di accesso

[Pietro Battiston]

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