Array in Haskell

Question

In che modo una matrice viene creata in haskell usando l'array del costruttore? Voglio dire, crea il primo elemento e così via? In tal caso, come legge l'elenco associato?

Per esempio, se si considerano i seguenti due programmi: -

ar :: Int->(Array Int Int) 
ar n = array (0,(n-1)) (((n-1),1):[(i,((ar n)!(i+1))) | i<-[0..(n-2)]]) 

ar :: Int->(Array Int Int) 
ar n = array (0,(n-1)) ((0,1):[(i,((ar n)!(i-1))) | i<-[1..(n-1)]]) 

saranno questi due hanno differenti complessità temporale?

Answer 1

Ciò dipende dall'implementazione, ma in un'implementazione ragionevole, entrambi hanno la stessa complessità (lineare nella dimensione dell'array).

In attuazione matrice di GHC, se consideriamo il codice

array (l,u) ies 
    = let n = safeRangeSize (l,u) 
     in unsafeArray' (l,u) n 
         [(safeIndex (l,u) n i, e) | (i, e) <- ies] 

{-# INLINE unsafeArray' #-} 
unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e 
unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# -> 
    case newArray# n# arrEleBottom s1# of 
     (# s2#, marr# #) -> 
      foldr (fill marr#) (done l u n marr#) ies s2#) 

{-# INLINE fill #-} 
fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a 
-- NB: put the \s after the "=" so that 'fill' 
--  inlines when applied to three args 
fill marr# (I# i#, e) next 
= \s1# -> case writeArray# marr# i# e s1# of 
      s2# -> next s2# 

possiamo vedere che prima di un nuovo blocco di memoria è allocato per la matrice, che viene poi sequenzialmente riempito con arrEleBottom (che è un error chiamare con il messaggio "elemento dell'array non definito"), quindi gli elementi forniti nell'elenco vengono scritti nei rispettivi indici nell'ordine in cui appaiono nell'elenco.

In generale, dal momento che è una matrice in scatola, ciò che è scritto alla matrice in costruzione è un tonfo che specifica come calcolare il valore quando è necessario (espressamente specificato valori, come il letterale 1 nei tuoi esempi , risulterà in un puntatore diretto a quel valore scritto nell'array).

Quando la valutazione di un tale thunk è forzata, può forzare anche la valutazione di ulteriori thunk nell'array - se il thunk si riferisce ad altri elementi dell'array, come qui. Negli esempi specifici qui, forzare qualsiasi risultato thunk nel forzare tutti i thunk in seguito resp. prima nell'array fino alla fine con la voce che non si riferisce a un altro elemento dell'array viene raggiunto. Nel primo esempio, se il primo elemento dell'array che è forzato è quello dell'indice 0, questo crea un thunk di dimensione proporzionale alla lunghezza dell'array che viene quindi ridotta, quindi forzare il primo elemento dell'array ha quindi la complessità O (n), quindi tutti gli altri elementi sono già stati valutati e forzarli è O (1). Nel secondo esempio, la situazione è simmetrica, poiché forzare l'ultimo elemento comporta il costo totale della valutazione. Se gli elementi sono richiesti in un ordine diverso, il costo di valutazione di tutti i thunk viene distribuito tra le richieste di diversi elementi, ma il costo totale è lo stesso. Il costo di valutazione di qualsiasi thunk non ancora valutato è proporzionale alla sua distanza dal thunk già valutato, e include la valutazione di tutti i thunk in mezzo.

Poiché l'accesso all'array è un tempo costante (eccetto per gli effetti cache, ma questi non dovrebbero fare la differenza se si riempie l'array in avanti o all'indietro, potrebbero fare una grande differenza se gli indici fossero in ordine casuale, ma che comunque non influenzerebbe la complessità del tempo), entrambi hanno la stessa complessità.

nota però che la utilizza ar n per definire gli elementi della matrice comporta il rischio di array multipli ripartendo (se compilato senza ottimizzazioni, GHC lo fa - appena testato: anche con ottimizzazioni che possono accadere). Per assicurarti che ne sia costruito uno solo, rendilo

ar n = result 
    where 
    result = array (0,n-1) (... result!index ...)