18

问题说明：

我目前正在寻找一个优雅和/但有效的解决方案来解决我认为很常见的问题。考虑以下情况：

我定义了一个基于BTree的文件格式（以简化的方式），如下所示：

data FileTree = FileNode [Key] [FileOffset]
              | FileLeaf [Key] [Data]

从文件中读取并将其写入惰性数据结构已实现并且工作正常。这将导致以下实例：

data MemTree = MemNode [Key] [MemTree]
             | MemLeaf [Key] [Data]

现在我的目标是拥有一个通用函数updateFile :: FilePath -> (MemTree -> MemTree) -> IO ()，它将读入FileTree并将其转换为 MemTree，应用该MemTree -> MemTree函数并将更改写回树结构。问题是必须以某种方式保存 FileOffsets。

我有两种方法来解决这个问题。他们都缺乏优雅和/或效率：

方法 1：扩展 MemTree 以包含偏移量

这种方法扩展了 MemTree 以包含偏移量：

data MemTree = MemNode [Key] [(MemTree, Maybe FileOffset)]
             | MemNode [Key] [Data]

然后 read 函数将读入FileTree并存储在参考FileOffset旁边MemTree。写入将检查引用是否已经具有关联的偏移量，如果有，则仅使用它。

优点：易于实现，无需开销即可找到偏移量

缺点：向负责将偏移量设置为的用户公开内部信息Nothing

方法 2：在二级结构中存储偏移量

解决这个问题的另一种方法是读入FileTree并创建一个StableName.Map保留在FileOffsets. 这样（如果我理解正确的语义）StableName应该可以在. 如果有条目，则节点是干净的，不必再次写入。MemTreeStableNameStableName.Map

优点：不向用户公开内部结构

缺点：涉及在地图中查找的开销

结论

这是我能想到的两种方法。第一个应该更高效，第二个更悦目。我希望您对我的想法发表评论，也许有人甚至有更好的方法？

[编辑] 合理

我正在寻找这样的解决方案有两个原因：

一方面，您应该尝试使用类型系统在错误出现之前对其进行处理。前面提到的用户当然是系统下一层的设计者（即我）。通过处理纯树表示，某些类型的错误将不会发生。对文件中树的所有更改都应该在一个地方。这应该使推理更容易。

另一方面，我可以实现类似的东西insert :: FilePath -> Key -> Value -> IO ()并完成它。但是，当我通过更新树来保留（一种）日志时，我将失去一个非常好的特征。事务（即合并多个插入）只是在内存中的同一棵树上工作并将差异写回文件的问题。

4

2 回答 2

2

我认为包Data.Generic.Diff可能完全符合您的要求。它参考了某人的论文来了解它是如何工作的。

于 2015-12-26T04:18:34.487 回答
1

我是 Haskell 的新手，所以我不会显示代码，但希望我的解释可能有助于解决问题。

首先，为什么不只向用户公开 MemTree，因为这是他们将更新的内容，并且 FileTree 可以完全隐藏。这样，稍后，如果您想将其更改为访问数据库，例如，用户不会看到任何差异。

所以，既然 FileTree 是隐藏的，为什么不在你要更新的时候把它读进去，那么你就有了偏移量，所以更新，然后再次关闭文件。

保留偏移量的一个问题是它会阻止另一个程序对文件进行任何更改，在您的情况下这可能很好，但我认为一般来说这是一个糟糕的设计。

我看到的主要变化是 MemTree 不应该是懒惰的，因为文件不会保持打开状态。

于 2012-10-15T10:39:45.160 回答