什么是有效实现图像渲染的纯功能数据结构？

Question

图像和像素渲染是Haskell最后的事情之一我无法选择一个足够有效的纯功能数据结构.为简单起见,我们来谈谈1D图像,因为它们可以很容易地扩展到nd图像.我正在使用未装箱的矢量作为表示,并使用它们的可变视图进行渲染:

-- An 1D image is an unboxed vector of Pixels
type Position = Int
data Image    = Image { size :: Position, buffer :: UV.Vector Pixel }

-- A sprite is a recipe to draw something to an Image
newtype Sprite = Sprite (forall s .
    -> (Position -> Pixel -> ST s ()) -- setPixel
    -> ST s ())                       -- ST action that renders to Image

-- Things that can be rendered to screen provide a sprite
class Renderable a where
    getSprite a :: a -> Sprite

-- `render` applies all sprites, mutably, in sequence. `O(P)` (where P = pixels to draw)
render :: [Sprite] -> Image -> Image
render draws (Image size buffer) = Image size $ runST $ do ...

这是我发现的CPU渲染效率最高的设计,但它相当难看.对于实现的纯函数结构,render显而易见的答案是使用映射来表示Image和(Position, Pixel)用于表示sprite 的对列表.就像是:

-- 1D for simplicity
type Position = Int

-- An image is a map from positions to colors
type Image    = Map Position Pixel

-- A sprite is, too, a map from positions to colors
type Sprite   = [(Position, Pixel)]

-- Rendering is just inserting each pixel in sequence
-- (Not tested.)
render :: [Sprite] -> Image -> Image
render sprites image = foldr renderSprite image sprites
    where renderSprite sprite image = foldr (uncurry insert) image sprites

这是O(P * log(N))(P =要渲染的像素,N =图像的大小).它可能看起来log(N)是不可避免的,但如果你仔细看,它会render经过Image几次相同的路径(即,如果你插入位置0,然后在位置1,你一直跑到一片叶子,然后所有向上,然后一直到邻居叶...).这看起来像完全相同的模式zippers,例如,可以改善渐近,这使我怀疑render可以改善.是否有任何纯粹的功能数据结构允许实现render比O(P*log N)？

注意:通过"纯粹的功能",我特别指的是仅使用Haskell的代数数据类型的结构,即没有诸如Int和的原生基元Array(即使它们在技术上更纯粹地用作纯数据结构).

Answer 1

如果精灵中的位置可以是任意的(例如[(0,x),(7,y),(5000,z)]),如果只允许使用有界分支因子的数据结构,那么你似乎不能希望做得比O(P log N)更好.

如果精灵中的位置是连续的,那么你可以使用Seq支持对数切片和连接的(fingertree)来实现renderO(log N)时间.如果你的精灵由k个不相交的连续序列组成,那么你可以重复这个k次O(k log N)render.

但是,我认为除非你愿意放弃额外的O因子(一维中的精灵的边长),否则扩展到两个维度并不像你说的那么容易.也许有某种手指kd树可以避免这个额外的因素.