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

Question

图像和像素渲染是 Haskell 中最后一件我无法为其选择足够高效的纯函数式数据结构的事情。为简单起见，让我们谈谈 1D 图像，因为它们可以很容易地扩展到 n 维图像。我使用未装箱的向量作为表示，并使用它们的可变 View 进行渲染:

-- 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 的纯功能结构，显而易见的答案是使用 map 来表示图像和 (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 可以改进。 是否有任何纯函数式数据结构可以比 O(P*log N) 更好地实现 render？

注意:我所说的“纯函数式”，特指只使用 Haskell 的代数数据类型的结构，即不使用 Int 和 Array (尽管这些在技术上被用作纯粹的数据结构，但更少)。

Answer 1

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

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

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