efficiency of UArray

Hal Daume III hdaume@ISI.EDU
Thu, 16 May 2002 09:41:58 -0700 (PDT)


> GHC doesn't remove intermediate lists down both
> branches of a zip, so yes, you'll get intermediate lists.

Okay.

> Why not use array indexing, as per your second version
> (only in Haskell)?

something along the lines of:

f arr = f' low 0
    where (low,high) = bounds arr
          f' pos acc | pos > high = acc
                     | otherwise  = f' (pos+1) (acc + arr!pos)

?

would:

  sum [v!i + u!i | i <- range (bounds v)]

also generate an intermediate list?

And finally, what about something like:

  f u v = listArray (bounds u) [v!i * u!i | i <- range (bounds u)]

versus

  f u v = u // [(i, v!i*u!i) | i <- range (bounds u)]

?

It's very unclear to me exactly what is going on "behind the scenes" with
arrays.  I would like to see functions like:

  afoldl, afoldr, azipWith, etc...

to be defined in the libraries, since there are so many possible
implementations and, it seems, the "best" implementation could be very
compiler dependent.  but barring this happening, what's the best approach
to take for things like this.  is // fast, or is it better to create new
arrays?

 - Hal

> | -----Original Message-----
> | From: Hal Daume III [mailto:hdaume@ISI.EDU] 
> | Sent: 16 May 2002 00:55
> | To: GHC Users Mailing List
> | Subject: efficiency of UArray
> | 
> | 
> | can we expect a function like:
> | 
> |   sum [x*y | (x,y) <- zip (elems v) (elems u)]
> | 
> | to be as efficient as, say:
> | 
> | sum = 0
> | for i=1, n
> |   sum = sum + v[i] * u[i]
> | 
> | ?
> | 
> | Basically, will any intermediate lists be created here?
> | 
> | --
> | Hal Daume III
> | 
> |  "Computer science is no more about computers    | hdaume@isi.edu
> |   than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
> | 
> | _______________________________________________
> | Glasgow-haskell-users mailing list 
> | Glasgow-haskell-users@haskell.org 
> | http://www.haskell.org/mailman/listinfo/glasgow-| haskell-users
> | 
>