Array in Haskell

Question

Wie wird ein Array in Haskell mithilfe des Konstruktorarrays erstellt? Ich meine, schafft es das erste Element und so weiter? In diesem Fall, wie liest es die zugehörige Liste?

Zum Beispiel, wenn wir die folgenden zwei Programme berücksichtigen: -

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

Werden diese zwei unterschiedliche Zeitkomplexität?

Answer 1

Das hängt von der Implementierung ab, aber in einer vernünftigen Implementierung haben beide die gleiche Komplexität (linear in der Array-Größe).

In Array-Implementierung GHC, wenn wir den Code anschauen

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# 

wir, dass zunächst ein neues Teil des Speichers sehen kann, ist für das Array zugeordnet wird, dass dann der Reihe nach mit arrEleBottom gefüllt (das ein error Rufen Sie mit der Nachricht "undefined array element" auf, und dann werden die in der Liste angegebenen Elemente in der Reihenfolge in die entsprechenden Indizes geschrieben, in der sie in der Liste erscheinen.

Im Allgemeinen, da es eine Box-Array ist, was auf das Array auf dem Bau geschrieben wird ein Thunk ist, der angibt, wie der Wert zu berechnen, wenn sie benötigt wird (explizit angegeben Werte, wie die wörtliche 1 in Ihre Beispiele , wird zu einem direkten Zeiger auf diesen Wert führen, der in das Array geschrieben wird.

Wenn die Auswertung eines solchen Thunks erzwungen wird, kann es auch die Auswertung weiterer Thunks im Array erzwingen - wenn sich der Thunk auf andere Array-Elemente bezieht, wie hier. In den spezifischen Beispielen führt das Erzwingen eines Thunk dazu, dass alle Thunks später gezwungen werden. früher im Array bis zum Ende mit dem Eintrag, der sich nicht auf ein anderes Array-Element bezieht, erreicht. Wenn das erste Array-Element, das erzwungen wird, das erste Array-Element im Index 0 ist, baut es im ersten Beispiel einen Thunk von Größe proportional zur Array-Länge auf, der dann reduziert wird, so dass das erste Array-Element dann Komplexität O (n) hat. dann werden alle weiteren Elemente bereits ausgewertet, und sie zu erzwingen ist O (1). Im zweiten Beispiel ist die Situation symmetrisch, da das letzte Element zuerst die Gesamtbewertungskosten verursacht. Wenn die Elemente in einer anderen Reihenfolge angefordert werden, verteilen sich die Kosten für die Bewertung aller Thunks auf die Anforderungen für verschiedene Elemente, aber die Gesamtkosten sind gleich. Die Kosten der Bewertung eines noch nicht ausgewerteten Thunks sind proportional zu seiner Entfernung von dem nächsten bereits ausgewerteten Thunk und umfassen die Auswertung aller Thunks dazwischen.

Da Array-Zugriff konstante Zeit ist (außer Cache-Effekte, aber diese sollten keinen Unterschied machen, wenn Sie das Array entweder vorwärts oder rückwärts füllen, könnten sie einen großen Unterschied machen, wenn die Indizes in zufälliger Reihenfolge, aber immer noch würde die zeitliche Komplexität nicht beeinflussen), beide haben die gleiche Komplexität.

Beachten Sie jedoch, dass Ihre Verwendung von ar n zur Definition der Array-Elemente das Risiko der Zuweisung mehrerer Arrays birgt (wenn GX ohne Optimierungen kompiliert wird, wird dies - nur getestet: selbst mit Optimierungen, die passieren können). Um sicherzustellen, dass nur eine konstruiert ist, machen Sie es

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