什么是高效实现图像渲染的纯函数数据结构？

Question

图像和像素渲染是 Haskell 中最后的事情之一，我无法为其选择足够高效的纯函数数据结构。为简单起见，让我们谈谈 1D 图像，因为这些图像可以轻松扩展到 n 维图像。我正在使用未装箱的矢量作为表示及其可变视图进行渲染：

-- 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-rendering 性能最高的设计，但它相当丑陋。对于实现 render 的纯功能结构，显而易见的答案是使用地图来表示图像，并使用 (Position, Pixel) 对的列表来表示精灵。类似于：

-- 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) 更好地实现？

注意："purely functional" 特指仅使用 Haskell 的代数数据类型的结构，即不使用 Int 和 [=24 等原生基元的结构=]（尽管从技术上讲，这些都是纯粹的数据结构）。

Answer 1

如果 sprite 中的位置可以是任意的（例如 [(0,x),(7,y),(5000,z)]），那么很明显，如果只允许使用数据，你就不能指望比 O(P log N) 做得更好有界分支因子的结构。

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

但是，我认为二维的扩展并不像你说的那么容易，除非你愿意放弃一个额外的因子 O（一维精灵的边长）。也许有某种 finger-k-d 树可以避免这个额外的因素。

Answer 2

您可以使用 discrimination 包在 O(n+p) 时间内构建您的 Map：

render sprites image
    = flip union image
    . toMapWith (\new old -> new)
    . concat
    $ sprites

什么是高效实现图像渲染的纯函数数据结构？

What is a purely functional data structure that efficiently implements rendering to an image?

algorithm

haskell

time-complexity

data-structures