如何在Scala中初始化和“修改”循环持久化数据结构?

12

我搜索了相关主题并找到了一些信息,但回答要么令人困惑,要么不适用。

我有以下代码:

class Thing (val name:String, val refs:IndexedSeq[Ref])
class Ref (val name:String, val thing:Thing)

现在,我想说的是,加载文件、解析它并从中填充这个数据结构。由于它是不可变的和循环的,有什么方法可以做到这一点?

另外,假设我已经填充了这个数据结构,现在我想修改它,比如更改rootThing.refs(3).name,有什么方法可以实现?


感谢在此发布的想法。目前,我的想法是,如果确实需要像这样的持久化数据结构,要跳出传统思维,考虑客户端代码需要提出哪些问题。因此,不要想着对象和字段,而是想着查询、索引等方面。作为起点,我正在思考以下方面: 是否存在双向多映射持久化数据结构?


文件长什么样? - Daniel C. Sobral
这个文件并不重要。我只是列出来表明我需要根据运行时数据而不是编译时数据来初始化它。 - mentics
由于您不知道解决方案,因此您没有评估何时相关何时不相关的资格。但如果您必须这样做,我会更改问题。数据结构是什么样子的?是任意图还是具有双向链接的树?它是如何初始化的?从根到底部,还是从任意点开始? - Daniel C. Sobral
它可能不是一个文件,而可能是来自内存中的某些用户交互或者其他来源的数据结构。整个数据结构就像一组类型。每种类型(给定代码中的Thing)都有一个属性列表(IndexedSeq [Ref])。每个属性都属于一种类型,因此Ref引用了它所属的Thing。 - mentics
4个回答

13

如果你准备引入一定程度的惰性,就可以初始化这种循环数据结构。

scala> class Thing (val name:String, refs0: => IndexedSeq[Ref]) { lazy val refs = refs0 } ; class Ref (val name:String, thing0: => Thing) { lazy val thing = thing0 }
defined class Thing
defined class Ref

scala> val names = Vector("foo", "bar", "baz")                                                                                                                       
names: scala.collection.immutable.Vector[java.lang.String] = Vector(foo, bar, baz)

scala> val rootThing : Thing = new Thing("root", names.map { new Ref(_, rootThing) })
rootThing: Thing = Thing@1f7dab1

scala> rootThing.refs(1).name
res0: String = bar

然而,您无法使其持久化:由于其循环结构,任何更改都可以通过结构中的每个元素看到,因此版本之间不存在共享机会。


非常好,我一直以为创建一个自引用的不可变结构是不可能的!谢谢 Miles! - Jean-Philippe Pellet
1
你说中了一个要点。无论能否初始化,它基本上都不能使用典型的持久数据结构优化来通过仅替换最少数量的节点来创建派生值。 - mentics

5

有一种替代方法需要重新思考如何表示对象关联:不是在对象本身内部存储对象之间的关联(通常在面向对象代码中执行),而是在单独的层中添加它们作为Map。

因为在创建关联时,对象图中的所有节点都已存在,所以可以使用Map轻松创建不可变的双向关联。

scala> class Thing (val name:String)
defined class Thing

scala> class Ref (val name:String)
defined class Ref

scala> new Thing("Thing1")
res0: Thing = Thing@5c2bae98

scala> new Ref("Ref1")
res1: Ref = Ref@7656acfa       

scala> val thing2Ref = Map(res0 -> res1)
thing2Ref: scala.collection.immutable.Map[Thing,Ref] = Map(Thing@5c2bae98 -> Ref
@7656acfa)

scala> val ref2Thing = Map(res1 -> res0)
ref2Thing: scala.collection.immutable.Map[Ref,Thing] = Map(Ref@7656acfa -> Thing
@5c2bae98)

如果你仔细想一想,这种方法类似于关系数据库的工作方式。表之间的多值关联不是存储在行本身中,而是存在单独的索引中。即使没有关联索引,并且使用表扫描解析查询时,也会使用主键索引来定位结果的所有候选行。
这种风格的优点是可以添加或更改关联而不影响对象本身,并且可以为不同的受众/用例使用不同的关联。缺点是关联映射不能直接访问关联起始实例;必须传递并提供单独的映射。

5

对于单个循环引用,您可以使用 lazy:

lazy val t: Thing = new Thing("thing", Vector(new Ref("ref", t)))

然而,当涉及到多对多的连接时,显然会变得更加复杂。

我不知道是否存在一个通用的纯函数循环图数据结构。对于无环图来说,这将是很容易的,因为你可以进行拓扑排序,然后逐步初始化它。

也许对您来说使用间接引用是一种选择,比如通过标识符而不是实际的Scala对象引用来引用对象?

case class ThingByID(id: Int, name: String, refs: IndexedSeq[RefByID])
case class RefByID(name: String, thingID: Int)

然后,您可以在加载文件后,按其ID将内容收集到不可变映射(例如collection.immutable.IntMap)中,并在从引用处查找它们。

编辑

Miles在lazy val t的第一种情况上是正确的。确实,您需要按名称传递参数,就像他的答案一样。

class Thing(val name: String, val refs: IndexedSeq[Ref])
class Ref(val name: String, _thing: => Thing) { def thing = _thing }

val t: Thing = new Thing("thing", Vector(new Ref("ref", t)))

1
很抱歉,您对t的定义还不够懒惰。任何尝试使用它都会导致StackOverflowError错误。 - Miles Sabin
你提到的ID是我在询问后想出来的。看起来这会导致显著的性能损失。但它也使其成为一种持久的数据结构,尽管人们必须有一种方法找到所有指向某个ID的Ref,这将使修改变得更加昂贵。这就引出了一个问题:与考虑到所有涉及的工作相比,这样做是否值得?有什么优点? - mentics
啊,不过了解从 Ref 到 Thing 的所有链接还是有用的——而且这是我们需要的东西,所以这就引出了我想到的另一件事情……为链接建立一个单独的多对多数据结构。因此,也许考虑将数据结构转换为可持久化的形式,而不是试图找出一些复杂的方法使循环起作用,可能会更有收益。 - mentics

3
不可变数据结构可以完全通过其构造函数进行初始化,或者您可以接受在更改其属性时保持复制该结构的需要。因此,为了回答问题的第一部分,您可以通过定义接受您的数据中的所有信息的构造函数将数据加载到不可变数据结构中,或确保您了解循环子图。
循环数据结构不一定完全是循环的,我认为。如果您想象一下单个实例/状态所拥有的指针网络,您可能会有一个包含相互指向的父级和子级的子图,但没有其他循环结构。在这种情况下,将实例1复制以懒惰地创建具有不同父节点的实例2(例如)将需要复制父节点和子节点,因为它们形成循环子图。但是,除父项之外的子项中保存的引用可以继续引用与第一个实例相同的不可变结构。
例如,我的House类具有对Door、Window和Roof的引用。门有颜色和对房子的引用,窗户有大小和屋顶有坡度。因此,我使用绿色的门、大窗户和平屋顶创建bobsHouse。实际上,由于所有这些都是不可变的,理论上只有一个大窗户-所有具有大窗户的房屋都有相同的窗户。第二个实例janesHouse与bobsHouse完全相同,但具有山形屋顶。因此,如果我说janesHouse = bobsHouse.withRoof(gabled),那么我应该得到一个新的House实例,其中包含一个新的(也是绿色的)门和一个新的(山形)屋顶,但具有相同的窗户。
因此,如果惰性地评估janesHouse,则只有在引用Door或Roof时才需要创建新的House。如果请求janesHouse.Window,则根本不需要创建新的House-只需要bobsHouse即可。
简而言之:您可以拥有持久的(懒惰的)循环数据结构,但前提是您可以找到其中的非循环子图,即它不是链式的。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接