如何有效地将二维字节数组复制到较大的二维数组中？

我有一个称为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

如何有效地将二维字节数组复制到较大的二维数组中？

回答

相关问题