Java中的持久数据结构

Question

有没有人知道一个库或者至少有一些关于在Java中创建和使用持久数据结构的研究？我没有将持久性称为长期存储,而是将持久性称为不变性(参见维基百科条目).

我正在探索为持久性结构建模api的不同方法.使用构建器似乎是一个有趣的解决方案:

// create persistent instance
Person p = Builder.create(Person.class)
             .withName("Joe")
             .withAddress(Builder.create(Address.class)
                 .withCity("paris")
                 .build())
              .build();

// change persistent instance, i.e. create a new one 
Person p2 = Builder.update(p).withName("Jack");

Person p3 = Builder.update(p)
              .withAddress(Builder.update(p.address())
                .withCity("Berlin")
                .build)
            .build();

但这仍然有点像锅炉板.有任何想法吗？

Answer 1

构建器将使您的代码过于冗长而无法使用.在实践中,我见过的几乎所有不可变数据结构都通过构造函数传递状态.值得一提的是,这里有一系列很好的帖子描述了C#中的不可变数据结构(它应该很容易转换成Java):

• 第1部分:不变性的种类
• 第2部分:简单的不可变堆栈
• 第3部分:协变不可变堆栈
• 第4部分:不可变队列
• 第5部分:Lolz!(包括为完整性)
• 第6部分:简单二叉树
• 第7部分:关于二叉树的更多信息
• 第8部分:关于二叉树的更多信息
• 第9部分:AVL树实现
• 第10部分:双端队列
• 第11部分:工作双端队列实现

C#和Java非常冗长,所以这些文章中的代码非常可怕.我建议学习OCaml,F#或Scala,并熟悉这些语言的不变性.掌握了这项技术后,您将能够更轻松地将相同的编码风格应用于Java.

Answer 2

我想明显的选择是:

o切换到临时数据结构(构建器)以进行更新.这很正常.例如StringBuilder,String操纵.作为你的榜样.

Person p3 =
    Builder.update(p)
    .withAddress(
        Builder.update(p.address())
       .withCity("Berlin")
       .build()
    )
    .build();

o始终使用持久性结构.虽然看起来有很多复制,但实际上你应该分享几乎所有的状态,所以它远不如它看起来那么糟糕.

final Person p3 = p
    .withAddress(
        p.address().withCity("Berlin")
    );

o将数据结构分解为许多变量,并与一个庞大而混乱的构造函数重新组合.

final Person p3 = Person.of(
    p.name(),
    Address.of(
       p.house(), p.street(), "Berlin", p.country()
    ),
    p.x(),
    p.y(),
    p.z()
 );

o使用回调接口提供新数据.更多的样板.

final Person p3 = Person.of(new PersonInfo(
    public String  name   () { return p.name(); )
    public Address address() { return Address.of(new AddressInfo() {
       private final Address a = p.address();
       public String house  () { return a.house()  ; }
       public String street () { return a.street() ; }
       public String city   () { return "Berlin"   ; }
       public String country() { return a.country(); }
    })),
    public Xxx     x() { return p.x(); }
    public Yyy     y() { return p.y(); }
    public Zzz     z() { return p.z(); }
 });

o使用令人讨厌的黑客来使字段暂时可用于代码.

final Person p3 = new PersonExploder(p) {{
    a = new AddressExploder(a) {{
        city = "Berlin";
    }}.get();
}}.get();

(有趣的是,我刚刚放下了Chris Okasaki的Purely Functional Data Structures副本.)

Answer 3

看看Functional Java.目前提供的持久性数据结构包括:

• 单链表(fj.data.List)
• 懒惰的单链表(fj.data.Stream)
• 非空列表(fj.data.NonEmptyList)
• 可选值(长度为0或1的容器)(fj.data.Option)
• 设置(fj.data.Set)
• 多路树(又名玫瑰树)(fj.data.Tree)
• 不可变地图(fj.data.TreeMap)
• arity 1-8(fj.P1..P8)的产品(元组)
• arity 2-8的矢量图(fj.data.vector.V2..V8)
• 指向列表(fj.data.Zipper)
• 尖头树(fj.data.TreeZipper)
• 类型安全的通用异构列表(fj.data.hlist.HList)
• 不可变数组(fj.data.Array)
• 不相交联合数据类型(fj.data.Either)

二进制分发提供了许多用法示例.该来源可通过Google Code的BSD许可获得.

Answer 4

我在Java中实现了一些持久性数据结构.Google代码上的所有开源(GPL)适用于任何感兴趣的人:

http://code.google.com/p/mikeralib/source/browse/#svn/trunk/Mikera/src/mikera/persistent

我到目前为止的主要是:

• 持久可变测试对象
• 持久的哈希映射
• 持久向量/列表
• 持久集(包括一组专门的持久性int)