provide as a programming language library a 2D array data type in which data is neither stored column-wise nor row-wise but a mix of both so that nearby array entries in any direction tend to be close in memory, taking advantage of memory hierarchy.
k-d tree, quadtree. but our data is not sparse. Hilbert curve, Z-order curve. interleaving the bits of the coordinates might work when dimensions are exact powers of 2.
inspired by random walks in 2D. every walk step requires lookup by location into a 2D array. successive lookups are close in 2D.
read/write of a single entry is O(log n) instead of O(1), which might negate the gains from better use of memory hierarchy. can things be improved? maybe a cursor which can (usually) quickly be moved to nearby array entries.
provide an API to run a given function (map) over a rectangular subset of array entries. also fold?
generalize to arbitrary number of dimensions.
No comments :
Post a Comment