A simple doubt about // operator ....
Hal Daume III
hdaume at ISI.EDU
Sun Nov 2 08:59:22 EST 2003
> The GHC documentation says about // (update array operator):
> "For MOST array types, this operation is O(n) where n is the size of the
> array. However, the DiffArray type provides this operation with complexity
> linear in the number of updates".
> The word "MOST" sugggests that there are other array variants for which //
> is linear on the number of updates. For unboxed arrays, // is linear on the
> array size or number of updates ?
(//) is always* linear in the array size
* except for DiffArrays
this is because it copies the array, which takes linear time in the size
of the array.
In general, I think the name "array" for these data structures is a bit
misleading, since nearly everyone expects an array to have constant time
read and update, while these only have constant time read.
More information about the Glasgow-haskell-users