算法（4th ed）(92)：基础——数据抽象 4.4.1

阅读数：24 2019 年 11 月 2 日 12:14

算法（4th ed）(92)：基础——数据抽象 4.4.1

(更多抽象数据类型的实现：日期）

表 1.2.12 是我们在表 1.2.6 中定义的 Date 抽象数据类型的两种实现。简单起见，我们省略了解析字符串的构造函数（请见练习 1.2.19）和继承的方法 equals()（请见 1.2.5.8 节）、compareTo()（请见 2.1.1.4 节）和 hashCode()（请见练习 3.4.22）。表 1.2.12 中左侧的简单实现将日、月和年设为实例变量，这样实例方法就可以直接返回适当的值；右侧的实现更加节省空间，仅使用了一个 int 变量来表示一个日期。它将d 日、m 月和 y 年的一个日期表示为一个混合进制的整数 512y+32m+d。用例分辨这两种实现的区别的一种方法可能是打破我们对日期的隐式假设：第二种实现的正确性基于日的值在 0 到 31 之间，月的值在 0 到 15 之间，年的值为正（在实际应用中，两种实现都应该检查月份的值是否在 1 到 12 之间，日的值是否在 1 到 31 之间，以及例如 2009 年 6 月 31 日和 2 月 29 日这样的非法日期，尽管这么做要费些工夫）。这个例子的主要意思是说明我们在 API 中极少完整地指定对实现的要求（一般来说我们都会尽力而为，这里还可以做得更好）。用例要分辨出这两种实现的区别的另一种方法是性能：右侧的实现中保存数据类型的值所需的空间较少，代价是在向用例按照约定的格式提供这些值时花费的时间更多（需要进行一两次算术运算）。这种交换是很常见的：某些用例可能偏爱其中一种实现，而另一些用例可能更喜欢另一种，因此我们两者都要满足。事实上，本书中反复出现的一个主题就是我们需要理解各种实现对空间和时间的需求以及它们对各种用例的适用性。在实现中使用数据抽象的一个关键优势是我们可以将一种实现替换为另一种而无需改变用例的任何代码。

表 1.2.12　一种封装日期的抽象数据类型以及它的两种实现

APIpublic class Date
             Date(int month, int day, int year)创建一个日期
        int  day()日
        int  month()月
        int  year()年
     String  toString()对象的字符串表示
测试用例
public static void main(String[] args)
{
   int m = Integer.parseInt(args[0]);
   int d = Integer.parseInt(args[1]);
   int y = Integer.parseInt(args[2]);
   Date date = new Date(m, d, y);
   StdOut.println(date);
}

使用方法
% java Date 12 31 1999
12/31/1999

数据类型的实现
public class Date
{
   private final int month;
   private final int day;
   private final int year;
   public Date(int m, int d, int y)
   {  month = m; day = d; year = y; }
   public int month()
   {  return month;  }
   public int day()
   {  return day;  }
   public int year()
   {  return year;  }
   public String toString()
   {  return month() + "/" + day()
                     + "/" + year();  }
}

数据类型的另一种实现
public class Date
{
   private final int value;
   public Date(int m, int d, int y)
   { value = y\*512 + m\*32 + d; }
   public int month()
   { return (value / 32) % 16; }
   public int day()
   { return value % 32; }
   public int year()
   { return value / 512; }
 
   public String toString()
   {  return month() + "/" + day()
                     + "/" + year();  }
}
文化 & 方法最佳实践算法

评论

发布