软件构造第三章第三部分

太过爱你忘了你带给我的痛 2021-12-18 16:39 378阅读 0赞

抽象数据型（ADT）

抽象数据类型与表示独立性：如何设计良好的抽象数据结构，通过封 装来避免客户端获取数据的内部表示（即“表示泄露”），避免潜在 的bug

ADT的特性：表示泄漏、抽象函数AF、表示不变量RI

基于数学的形式对ADT的这些核心特征进行描述并应用于设计中。

ADT的四种操作

1）Creators（构造器）：

创建某个类型的新对象，⼀个创建者可能会接受⼀个对象作为参数，但是这个对象的类型不能是它创建对象对应的类型。可能实现为构造函数或静态函数。（通常称为工厂方法）

t\* -> T

例子：Integer.valueOf( )

2）Producers（生产器）：通过接受同类型的对象创建新的对象。

T+ , t\* -> T

例子：String.concat( )

3）Observers（观察器）：获取抽象类型的对象然后返回一个不同类型的对象/值。

T+ , t\* -> t

例子：List.size( ) ；

4）Mutators（变值器）：

改变对象属性的方法 ，

变值器通常返回void，若为void，则必然意味着它改变了对象的某些内部状态；当然，也可能返回非空类型

T+ , t\* -> t || T || void

例子：List.add( )

解释：T是ADT本身；t是其他类型；+ 表示这个类型可能出现一次或多次；\* 表示可能出现0次或多次。

更多例子：

![1614222-20190620195628031-909099724.png][]

**设计ADT**

设计好的ADT，靠“经验法 则”，提供一组操作，设计其行为规约 spec

原则1：设计简洁、一致的操作

原则2：要足以支持client对数据所做的所有操作需要，且 用操作满足client需要的难度要低

原则3：要么抽象、要么具体，不要混合 --- 要么针对抽象 设计，要么针对具体应用的设计

**表示独立性**

client使用ADT时无需考虑其内部如何实 现，ADT内部表示的变化不应影响外部spec和客户端。

除非ADT的操作指明了具体的pre和post-condition，否则不能改变ADT的内部表示——spec规定了 client和implementer之间的契约。

下面举例说明

首先看一个表示独立的例子，

/** MyString represents an immutable sequence of characters. */
    public class MyString { 
    
         Example of a creator operation ///
        /** @param b a boolean value
         *  @return string representation of b, either "true" or "false" */
        public static MyString valueOf(boolean b) { ... }
    
         Examples of observer operations ///
        /** @return number of characters in this string */
        public int length() { ... }
    
        /** @param i character position (requires 0 <= i < string length)
         *  @return character at position i */
        public char charAt(int i) { ... }
    
         Example of a producer operation ///    
        /** Get the substring between start (inclusive) and end (exclusive).
         *  @param start starting index
         *  @param end ending index.  Requires 0 <= start <= end <= string length.
         *  @return string consisting of charAt(start)...charAt(end-1) */
        public MyString substring(int start, int end) { ... }
    }

使用者只需要知道公共方法与规格说明，下面是如何声明内部表示的方法，作为一个实例变量

private char\[\] a;

一个可能的实现方法如下;

public static MyString valueOf(boolean b) {
        MyString s = new MyString();
        s.a = b ? new char[] { 't', 'r', 'u', 'e' } 
                : new char[] { 'f', 'a', 'l', 's', 'e' };
        return s;
    }
    
    public int length() {
        return a.length;
    }
    
    public char charAt(int i) {
        return a[i];
    }
    
    public MyString substring(int start, int end) {
        MyString that = new MyString();
        that.a = new char[end - start];
        System.arraycopy(this.a, start, that.a, 0, end - start);
        return that;
    }

执行以下操作后，可以得到snapshot diagram

![1614222-20190620203938841-1866311788.png][]

因为这个数据类型是不可变的，那么 substring 实际上没有必要真正去复制子字符串到⼀个新的数组中。它可以仅仅指向原来的 MyString 字符数组，并且记录当前的起始位置和终⽌位置。

那么另一种高效的实现如下：

![1614222-20190620204106095-179266004.png][]

此使执行相同的代码。snapshot diagram如下：

![1614222-20190620204131557-1430159007.png][]

不需要再拷贝一次char。

**不变量**

不变量：在任何时候总是true

由ADT 来负责其不变量，与client端的任何行为无关

为什么需要不变量：保持程序的“正确 性”，容易发现错误

**表示泄露**

下面举例来说明：

/**
     * This immutable data type represents a tweet from Twitter.
     */
    public class Tweet {
    
        public String author;
        public String text;
        public Date timestamp;
    
        /**
         * Make a Tweet.
         * @param author    Twitter user who wrote the tweet
         * @param text      text of the tweet
         * @param timestamp date/time when the tweet was sent
         */
        public Tweet(String author, String text, Date timestamp) {
            this.author = author;
            this.text = text;
            this.timestamp = timestamp;
        }
    }

因为变量都是public，所以下面的操作会直接访问到Tweet内部数据：

1 Tweet t = new Tweet("justinbieber", 
    2                     "Thanks to all those beliebers out there inspiring me every day", 
    3                     new Date());
    4 t.author = "rbmllr";

这样的表示泄露不仅影响不变性，也影响了表示独立性：无法在不影响客户 端的情况下改变其内部表示

那么将变量都改为private final会怎么样呢

看下面的代码

public class Tweet {
        private final String author;
        private final String text;
        private final Date timestamp;
    
        public Tweet(String author, String text, Date timestamp) {
            this.author = author;
            this.text = text;
            this.timestamp = timestamp;
        }
    
        /** @return Twitter user who wrote the tweet */
        public String getAuthor() {
            return author;
        }
    
        /** @return text of the tweet */
        public String getText() {
            return text;
        }
    
        /** @return date/time when the tweet was sent */
        public Date getTimestamp() {
            return timestamp;
        }
    }

在private和public关键字表明哪些字段和方法可访问时，只在类内部还是可以从类外部访问。所述final关键字还保证该变量的索引不会被更改，对于不可变的类型来说，就是确保了变量的值不可变。

但是上面的代码还是会有表示泄露产生，如下面的操作：

![1614222-20190620205214607-20500449.png][]

我们画出snap diagram来说明

![1614222-20190620205249349-406399280.png][]

d和Tweet中的timestamp指向相同的Date，但Date可变，d对Date修改，导致Tweet的timestamp也被修改。这样，Tweet的不变性就被破坏，Tweet将自己内部对于可变对象的索引“泄露”了出来，因此整个对象都变成可变的了，使用者在使用时也容易造成隐藏的bug。

我们可以通过防御性拷贝来解决该问题：

![1614222-20190620205541702-245096465.png][]

让getTimestamp返回一个新的对象实例。

即使这样，下面的操作还会导致表示泄露

/** @return a list of 24 inspiring tweets, one per hour today */
    public static List<Tweet> tweetEveryHourToday () {
        List<Tweet> list = new ArrayList<Tweet>(); 
        Date date = new Date();
        for (int i = 0; i < 24; i++) {
            date.setHours(i);
            list.add(new Tweet("rbmllr", "keep it up! you can do it", date));
        } 
        return list;
    }

该代码创建24个Tweet对象，但构造时都是用相同的date，导致最后24个Tweet都同一时间结束，如下图所示

![1614222-20190620205833893-77830299.png][]

所以我们对creator方法也做了防御性编程：

![1614222-20190620205917105-1241104723.png][]

但这样的拷贝非常浪费，但这没有办法

除非迫不得已，否则不要把希望寄托于客户端上，ADT有责任保证自 己的invariants，并避免“表示泄露”。

最好的办法就是使 用immutable的类型，彻底避免表示泄露

总结:

简单来说，一个主类有属性和方法两种成分，这里的主类是指用户直接使用的类，需要做到以下两点

1、将类中所有的属性（变量）定义为private类型，目的是不让用户得到你的内部属性

2、方法或者返回immutable data，或者返回本应该返回的mutable data的副本，或者返回一个不可修改的mutable data

为了做到第二点的三个方面

1、尽量使用immutable数据类型，比如能使用String就不使用StringBuilder，能使用Instance就不使用Data

2、为了创造mutable data的副本，可以进行defensive copy。可以在主类方法中构造然后返回，但是推荐方法是使用mutable数据类型的clone，假如该mutable数据类型是自己写的类，那么推荐在类中写一个clone的方法

3、使用Collections.unmodifiableSet等方法这里需要注意的是第二个方面，如果想要返回一个Collection类的数据，有人说我创建了一个Collection类，向里面添加数据后，不管数据怎样，都算defensive copy了，但是如果数据是mutable类型，那么就不算defensive copy，因为Collection类储存的是地址，尽管new了一个hashSet或者hashMap，但是没有真正的对mutable数据进行defensive copy。

**抽象函数AF与表示不变量RI**

![1614222-20190620210553995-872849666.png][]

在研究抽象类型的时候，先思考一下两个值域之间的关系：

表示域（rep values）里面**包含的是值具体的实现实体**。一般情况下ADT的表示比较简单，有些时候需要复杂表示。

抽象域（A）里面包含的则是类型设计时支持使用的值。**这些值是由表示域“抽象/想象”出来的，也是使用者关注的。**

ADT实现者关注表示空间R，用户关注抽象空间A 。

R->A的映射特点：

**每一个抽象值都是由表示值映射而来** ，即满射：每个抽象值被映射到一些rep值**一**

**些抽象值是被多个表示值映射而来的，**即未必单射：一些抽象值被映射到多个rep值

**不是所有的表示值都能映射到抽象域中，**即未必双射：并非所有的rep值都被映射。

抽象函数（AF）：R和A之间映射关系的函数

表示不变量（RI）：将rep值映射到布尔值

对于表示值r，当且仅当r被AF映射到了A，RI(r)为真。

表示不变性RI：某个具体的“表示”是否是“合法的”

也可将RI看作：所有表示值的一个子集，包含了所有合法的表示值

也可将RI看作：一个条件，描述了什么是“合法”的表示值

在下图中，绿色表示的就是RI(r)为真的部分，AF只在这个子集上有定义。

![1614222-20190620210729128-427333218.png][]

转载于:https://www.cnblogs.com/boston-o/p/11061368.html

[1614222-20190620195628031-909099724.png]: /images/20211218/95dbc746569e4532b66528e7594c1a88.png
[1614222-20190620203938841-1866311788.png]: /images/20211218/69c1e6f94b734ad9856d8266b881cb44.png
[1614222-20190620204106095-179266004.png]: /images/20211218/9f14b140924a4d5ab354253d9820b5f5.png
[1614222-20190620204131557-1430159007.png]: /images/20211218/91435ad96be74c22bf0ae7e68d2479ae.png
[1614222-20190620205214607-20500449.png]: /images/20211218/b8866b1dec52447e9f1cf4afe702551a.png
[1614222-20190620205249349-406399280.png]: /images/20211218/0e854b67b58948239ebddfdd458ea9ab.png
[1614222-20190620205541702-245096465.png]: /images/20211218/69e2ae6da3e64315886f6d6c60a4d8b3.png
[1614222-20190620205833893-77830299.png]: /images/20211218/5678f5fe29074304bba5339ae698f005.png
[1614222-20190620205917105-1241104723.png]: /images/20211218/8b67c0435f834beb9aaedc4fd5707a9a.png
[1614222-20190620210553995-872849666.png]: /images/20211218/3e0ece51a3d04e728904c768016aac26.png
[1614222-20190620210729128-427333218.png]: /images/20211218/7e16bd33938040b582310da1cb9a7b6c.png