如何有效地將二維字節數組複製到較大的二維數組中？

我有一個稱爲Patch的結構，它表示一個二維數組數組。如何有效地將二維字節數組複製到較大的二維數組中？

newtype Size = (Int, Int) 
data Patch = Patch Size Strict.ByteString

我想從一組較小的修補程序及其指定的位置構造一個更大的修補程序。（修補程序不重疊）。功能如下所示：

newtype Position = (Int, Int) 

combinePatches :: [(Position, Patch)] -> Patch 
combinePatches plan = undefined

我看到兩個子問題。首先，我必須定義一個函數將2D陣列副本轉換爲一組一維陣列副本。其次，我必須從所有這些副本構建最終的補丁。

請注意，最終修補程序將大約4 MB的數據。這就是爲什麼我想避免一個天真的方法。

我相當有信心，我可以做到這種可怕的低效率，但我想就如何有效地操縱Haskell中的大型二維數組提供建議。我一直在尋找「矢量」庫，但我從來沒有使用過它。

謝謝你的時間。

來源

2010-06-29 Keith Holman

補丁不重疊，但它們覆蓋整個矩形嗎？ – yatima2975 2010-06-29 11:33:01

我不知道任何語言的任何非常好的解決方案。但我也不清楚你的用例的大背景。可能有其他已知的事情會改變照片。這是重複的操作，還是隻有一次？你是否對複合補丁進行中間操作？或者你只是在尋找一個與例如慣用C相匹配的解決方案嗎？ – sclv 2010-06-29 14:18:31

@ yatima2975：它們沒有覆蓋整個矩形。 @sclv：這不是我正在做的事，但我寧願不要花一分多鐘。如果不是優雅的話，這就是C中速度很快的那種東西。我只想要一個合理有效的方法來製作所有這些副本。「複合貼片的中間操作」是什麼意思？ – 2010-06-29 14:55:34

如果規範實際上只是從一組以前的和它們的位置創建一個新的Patch，那麼這是一個簡單的單通算法。從概念上講，我會將其視爲兩個步驟 - 首先，將現有補丁合併到數據結構中，併合理查找任何給定的位置。接下來，通過查詢複合結構來懶散地編寫新的結構。這應該大致爲O（n log（m）） - n是您正在編寫的新數組的大小，m是補丁的數量。

如果使用Vector庫而不是原始ByteString，這在概念上會簡單得多。但是，如果你簡單地使用Data.Array.Unboxed，它仍然更簡單。如果您需要可以與C互操作的數組，則可以使用Data.Array.Storable。

如果你溝渠純淨，至少在本地，並與ST陣列一起工作，你應該能夠在O（n）時間內做到這一點。當然，恆定的因素仍然會比一次快速複製大塊內存更糟糕，但是沒有辦法讓代碼看起來低級。

來源

2010-06-29 15:20:50 sclv

或使用Data.Vector.Storable.Vector/MVector（並從ST中凍結）。 – 2010-06-29 18:43:53

正確 - 你應該能夠使用slice和copy來將它從一些看起來比純粹C更清潔的東西上拉下來。但是我的偏好，除非我真的需要額外的性能，那就是用處理Array數組的庫以一定的成本考慮我的指標。 – sclv 2010-06-29 19:40:46

如何有效地將二維字節數組複製到較大的二維數組中？

回答

相關問題