Cấu trúc dữ liệu hoàn toàn chức năng thực hiện hiệu quả việc hiển thị hình ảnh là gì?

Question

Hình ảnh và hiển thị pixel là một trong những điều cuối cùng trong Haskell tôi không thể chọn cấu trúc dữ liệu hoàn toàn có chức năng hiệu quả. Để đơn giản, hãy nói về các hình ảnh 1D vì những hình ảnh này có thể dễ dàng mở rộng thành hình ảnh n-d. Tôi đang sử dụng vectơ không có hộp bọc như các đại diện và xem có thể thay đổi họ cho rendering:

-- 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 ... 

Đây là thiết kế performant nhất cho CPU rendering tôi thấy, nhưng nó là khá xấu xí. Đối với một cấu trúc hoàn toàn chức năng thực hiện render, câu trả lời rõ ràng sẽ là sử dụng một bản đồ để đại diện cho Hình ảnh và danh sách các cặp (Position, Pixel) để đại diện cho sprite. Một cái gì đó như:

-- 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 

Đây là O(P * log(N)) (P = pixel để hiển thị, N = kích thước của hình ảnh). Có thể thấy rằng log(N) không thể tách rời, nhưng nếu bạn thấy nó một cách cẩn thận, render đang di chuyển cùng một đường dẫn qua Image nhiều lần (ví dụ, nếu bạn chèn ở vị trí 0, sau đó ở vị trí 1, bạn đang chạy hết cỡ xuống một chiếc lá , sau đó tất cả các con đường lên, sau đó tất cả các cách xuống lá láng giềng ...). Điều đó có vẻ giống như mô hình chính xác mà ví dụ như zippers, có thể cải thiện tiệm cận, dẫn tôi đến nghi ngờ render có thể được cải thiện. Có cấu trúc dữ liệu hoàn toàn chức năng nào cho phép triển khai render tốt hơn O(P*log N) không?

Lưu ý: do "hoàn toàn chức năng", tôi đặc biệt có nghĩa là một cấu trúc mà không sử dụng các kiểu dữ liệu đại số Haskell của mình, nghĩa là không có nguyên thủy có nguồn gốc như Int và Array (mặc dù những được phục vụ về mặt kỹ thuật như cấu trúc dữ liệu tinh khiết Nether ít).

Answer 1

Nếu vị trí trong một sprite có thể tùy ý (ví dụ [(0,x),(7,y),(5000,z)]), có vẻ như bạn không thể hy vọng làm tốt hơn O (P log N) nếu bạn chỉ được phép sử dụng cấu trúc dữ liệu của hệ số phân nhánh .

Nếu các vị trí trong một sprite liền nhau thì bạn có thể sử dụng Seq (ngón tay) hỗ trợ cắt logarit và nối để thực hiện render trong thời gian O (log N). Nếu sprite của bạn bao gồm k tách rời các chuỗi liền kề thì bạn có thể lặp lại k lần này cho O (k log N) render.

Tuy nhiên, tôi không nghĩ rằng phần mở rộng cho hai chiều là dễ dàng như bạn làm cho nó âm thanh trừ khi bạn sẵn sàng từ bỏ một yếu tố phụ của O (chiều dài của sprite trong một chiều). Có lẽ có một số loại cây finger-k-d tránh được yếu tố phụ này.

Answer 2

Bạn có thể sử dụng gói discrimination để xây dựng Map trong thời gian O (n + p) thời gian của bạn:

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