表示独立(Representation independent)的概念

本文是对MIT讲义Reading 12: Abstract Data Types的representation_independence部分进行的总结,涉及到表示独立(Representation independent)的概念以及规范(specification)、表示(representation)、实现(implementation)的区别


由于本人水平有限,本文难免会有不当之处,欢迎读者批评指正

表示独立(representation independent)

一个好的抽象数据类型应该是表示独立(representation independent)的,这意味着使用一个抽象数据类型是独立于它的具体实现的,representation指的就是实现这个抽象数据类型所使用的具体数据类型和数据域。所以改变表示对抽象数据类型外部的代码没有影响。例如,List提供的操作与列表是由链表还是数组实现的无关。

示例:strings的不同表示

让我们通过一个简单的抽象数据类型来探究表示独立是什么意思和它有什么用?下面的MyString比java中真正的String具有更少的操作,他们的规范(specs)也有所不同,但是它已经可以说明我们的意思了。下面是这个ADT的规范:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/** 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) { ... }
}

public操作和它们的规范是客户可知的唯一信息。根据优先测试编程的范例,事实上,我们创建的第一个客户应该是根据规范测试这些操作的测试套件。下面是对valueOf操作的一个测试:

1
2
3
4
5
6
MyString s = MyString.valueOf(true);
assertEquals(4, s.length());
assertEquals('t', s.charAt(0));
assertEquals('r', s.charAt(1));
assertEquals('u', s.charAt(2));
assertEquals('e', s.charAt(3));

现在,我们来看一个简单的MyString表示:就是一个确定了长度的字符数组。下面是它的内部表示,作为类中的一个实例变量:

1
private char[] a;

选择了这种表示方式,我们的实现也就直截了当了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}

上面这种实现方式的一个问题是它没办法进行性能优化。因为这个数据类型是不可变的,所以substring操作没有必要真的去将字符复制到一个新的数组中,他可以利用原始的MyString的数组,然后保存两个变量startend用以指示位置。

为了实现这种优化,我们要改变这个类的内部表示:

1
2
3
private char[] a;
private int start;
private int end;

利用这个新的表示,操作现在可以这样实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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' };
s.start = 0;
s.end = s.a.length;
return s;
}

public int length() {
return end - start;
}

public char charAt(int i) {
return a[start + i];
}

public MyString substring(int start, int end) {
MyString that = new MyString();
that.a = this.a;
that.start = this.start + start;
that.end = this.start + end;
return that;
}

因为MyString的客户依赖的是public方法的规范,而不是private的域,所以我们的改变不会影响客户端的代码,也就是说原有的客户端的代码不用做任何改变。这就是表示独立的强大之处。

规范(specification)、表示(representation)、实现(implementation)的区别

  • 规范(specification)包括类的名字,类前面的Javadoc注释,公有方法和公有域的规范(包括方法的Javadoc注释和方法签名)。
  • 表示(representation)包括ADT的域以及对这些域的任何假设和要求(这些假设和要求可能以注释的形式表示出来)。
  • 实现(implementation)包括具体方法的实现。

    讲义原文地址

    Reading 12: Abstract Data Types