 | lazyarray-0.1: Efficient implementation of lazy monolithic arrays (lazy in indexes). | Source code | Contents | Index |
| Data.LazyArray |
|
| Contents |
This is an implementation of monolithic lazy array. If you want to know what an monolithic lazy array is good for, you can read for example the paper "Efficient Graph Algorithms Using Lazy Monolithic Arrays" (http://citeseer.ist.psu.edu/95126.html).
Module Data.LazyArray implements the monolithic lazy array using Array with temporary buffer. For implementation without the temporary buffer see Data.LazyArray.Lowlevel module.
Don't forget to import some kind of arrays when using this module. Results of small benchmark and a discussion can be found at the bottom of this page.
| lArray :: Ix i => (i, i) -> [(i, e)] -> Array i [e] |
| lArrayMap :: Ix i => ([e] -> e') -> (i, i) -> [(i, e)] -> Array i e' |
| lArrayMaybe :: Ix i => (i, i) -> [(i, e)] -> Array i (Maybe e) |
| lArrayFirst :: Ix i => e -> (i, i) -> [(i, e)] -> Array i e |
| lArray | Source |
| :: Ix i | |
| => (i, i) | bounds of the array |
| -> [(i, e)] | list of associations |
| -> Array i [e] | resulting array |
This function returns an array, which i-th element is a list, that contains all values associated with i in the list of associations, in that order. In other words, the result of lArray bnds assoc is lArray bnds assoc = array bnds [(i,[e|(i',e)<-assoc,i'==i] | i<-range bnds]. The important difference between the two sides of previous equation is that lArray works in linear time, ie. each member in the assoc list is accessed exactly once, and lArray is lazy in its second argument. It means the assoc list is left intact until an i-th element of the resulting array needs to be evaluated. At that time the assoc list is examined until the first pair (i,e') is found. Until such pair is found, processed elements of assoc are stored at appropriate indexes in the resulting array. The implementation uses temporary array for such processed elements of assoc list, that were not yet 'requested' [or 'evaluated'] in the resulting array. This array can be freed when all lists of the resulting array are fully evaluated. Here is an example of how to use the monolithic lazy array. Given a graph of type Array Int [Int] we construct the dfs numbering from a given vertex. Obviously, only the first element of the lArray is needed - lArrayFirst, lArrayMaybe or Data.LazyArray.Lowlevel are better choice here. dnum::Array Int [Int]->Int->Array Int (Maybe Int) dnum g s = amap listToMaybe marks where list = dfs' [s] 0 marks = lArray (bounds g) list dfs' [] _ = [] dfs' (s:ss) n = (s,n) : if n == head (marks!s) then dfs' ((g!s)++ss) (n+1) else dfs' ss n | |
| lArrayMap | Source |
| :: Ix i | |
| => [e] -> e' | function to apply to the list of elements belonging to the same index |
| -> (i, i) | bounds of the array |
| -> [(i, e)] | list of associations |
| -> Array i e' | resulting array |
| It is often needed to apply some function to the list of elements belonging to the same index. Function lArrayMap is provided, and could be defined like lArrayMap f = (amap f) . lArray. Obviously, lArray = lArrayMap id. | |
| lArrayMaybe | Source |
| :: Ix i | |
| => (i, i) | bounds of the array |
| -> [(i, e)] | list of associations |
| -> Array i (Maybe e) | resulting array |
| This is equivalent to lArrayMaybe = lArrayMap listToMaybe but a bit faster. | |
| lArrayFirst | Source |
| :: Ix i | |
| => e | 'zero' element, |
| -> (i, i) | bounds of the array |
| -> [(i, e)] | list of associations |
| -> Array i e | resulting array |
| This is equivalent to lArrayFirst zero = lArrayMap (\x->case x of []->zero; e:_->e) but a bit faster. | |
For comparison, various implementations of DFS numbering have been benchmarked. The benchmark can be found in the lazyarray package, in the file bench/bench.hs. The DFS was implemented using Data.LazyArray, Data.LazyArray.Lowlevel, Data.Array.Diff, Data.Map and Data.IntMap. Three graphs were used, a path, a graph with 20 edges at each vertex, and a complete graph; each graph was used once as connected and once with isolated vertex iv. The DFS number of the isolated vertex was never asked for. Details can be found in the source file. This whole benchmark is written in Haskell, so it is only approximate.
DFS implemented using | path |path+iv|20-path|20path+iv|cmplt gph|cmplt gph+iv --------------------------|------|-------|-------|---------|---------|------------- lArrayFirst | 5456 | 5572 | 1956 | 1968 | 1316 | 1296 lArrayFirst with lArrayMap| 5248 | 5248 | 3456 | 3452 | 3072 | 3040 lArrayMaybe | 5772 | 5724 | 2044 | 2064 | 1308 | 1312 lArrayMaybe with lArrayMap| 5380 | 5352 | 3560 | 3564 | 3048 | 3024 Data.LazyArray.Lowlevel.laCreate | 4560 | 4700 | 4984 | 9360 | 5280 | 11140 Data.LazyArray.Lowlevel.mlaCreate | 5308 | 5824 | 5972 | 11508 | 6328 | 13712 Data.Array.Diff |29089 | 29173 | 14652 | 14144 | 15072 | 14988 Data.Map | 7216 | 7292 | 4892 | 4912 | 3316 | 3300 Data.IntMap | 3328 | 3280 | 2616 | 2640 | 2492 | 2524
The numbers are elapsed time in ms, but use these numbers only to compare implementations in one column. The first two columns are quite inconclusive, because the DFS does not really do much when graph is a path and Data.Map and Data.IntMap implementations don't do exactly the same as the others implementations. The Data.LazyArray.Lowlevel.laCreate and Data.LazyArray.Lowlevel.mlaCreate perform very badly in the presence of isolated vertex - Data.LazyArray.Lowlevel.laFreeze tries hard to find a connection to the isolated vertex even if it is not asked for.