Что такое чисто функциональная структура данных, которая эффективно реализует рендеринг изображения?

Изображения и рендеринг пикселей - одна из последних вещей в Haskell. Я не мог выбрать достаточно эффективную чисто функциональную структуру данных. Для простоты давайте поговорим о 1D изображениях, так как они могут легко распространяться на n-d изображения. Я использую unboxed векторы как представление и их изменяемый вид для рендеринга:

-- 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, очевидным ответом будет использование карты для представления изображения и списка пар (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)?

Примечание: под "чисто функциональным" я имею в виду структуру, которая не использует ничего, кроме только алгебраических типов данных Haskell, т.е. без нативных примитивов, таких как Int и Array (даже если они технически служат чистыми структурами данных ниже).

Ответы

Ответ 1

Если позиции в спрайте могут быть произвольными (например, [(0,x),(7,y),(5000,z)]), кажется довольно очевидным, что вы не можете надеяться на лучшее, чем O (P log N), если вам разрешено использовать структуры данных ограниченного разветвления фактор.

Если позиции в спрайте смежны, вы можете использовать Seq (fingertree), который поддерживает логарифмическую нарезку и конкатенацию для реализации render в O ( log N). Если ваш спрайт состоит из k непересекающихся смежных последовательностей, вы можете повторить это k раз для O (k log N) render.

Однако, я не думаю, что расширение до двух измерений так же просто, как вы делаете звук, если только вы не готовы отказаться от дополнительного коэффициента O (длина стороны спрайта в одном измерении). Возможно, есть какое-то дерево finger-k-d, которое позволяет избежать этого лишнего фактора.

Ответ 2

Вы можете использовать discrimination для создания своего Map в O (n + p) времени:

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