欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

对于AF、RI以及Rep exposure的心得体会(复习笔记一)

程序员文章站 2024-02-09 18:10:46
...

对于AF、RI以及Rep exposure的心得体会(复习笔记一)
一、A与R
先介绍两个空间:
R: 表示值(rep值)的空间由实际实现实体的值组成。ADT将作为单个对象实现,但更常见的是需要一个小的对象网络,因此其值通常相当复杂。

A: 抽象值的空间由类型设计为支持的值组成。它们是柏拉图式的实体,不存在如前所述,但它们是我们希望将抽象类型的元素视为该类型的客户机的方式。

对于这两个空间,通俗易懂一点的讲,R为开发者所使用的空间,而A是客户所看到的空间。分别对应了代码端以及实际对象。

引入一个规约进行举例:

 In a Store, there are some kinds of items to sell. Each item has a price.
 * 
 * However, there are some special offers, and a special offer consists of one
 * or more different kinds of items with a sale price.
 * 
 * You are given the each item's price, a set of special offers, and the number
 * we need to buy for each item. The job is to output the lowest price you have
 * to pay for exactly certain items as given, where you could make optimal use
 * of the special offers.
 * 
 * Each special offer is represented in the form of an array, the last number
 * represents the price you need to pay for this special offer, other numbers
 * represents how many specific items you could get if you buy this offer.
 * 
 * You could use any of special offers as many times as you want.
 * 
 * Example 1:
 * 
 * Input: [2,5], [[3,0,5],[1,2,10]], [3,2] Output: 14
 * 
 * Explanation:
 * 
 * There are two kinds of items, A and B. Their prices are $2 and $5
 * respectively.
 * 
 * In special offer 1, you can pay $5 for 3A and 0B
 * 
 * In special offer 2, you can pay $10 for 1A and 2B.
 * 
 * You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer
 * #2), and $4 for 2A.
 * 
 * Example 2:
 * 
 * Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1] Output: 11
 * 
 * Explanation:
 * 
 * The price of A is $2, and $3 for B, $4 for C.
 * 
 * You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
 * 
 * You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer
 * #1), and $3 for 1B, $4 for 1C.
 * 
 * You cannot add more items, though only $9 for 2A ,2B and 1C.
 * 
 * 
 * Note:
 * 
 * 1. There are at most 6 kinds of items, 100 special offers.
 * 
 * 2. For each item, you need to buy at most 6 of them.
 * 
 * 3. You are not allowed to buy more items than you want, even if that would
 * lower the overall price.

在这其中,显而易见的是用户所能看到的空间。也就是实体对象:购买商品的个数,购买商品的种类,以及购买商品的特惠套餐,以及顾客的需求数目等等。这也是我们的A空间。
而这个空间是程序员所不能写入代码的空间,因此就需要一个R空间与它进行映射,从而形成了我们的代码,也就是我们的数据结构,也就是R空间。
如下面代码所示,函数传入的三个参数就分别对应了我们想要看到的三种A空间元素:商品种类价格,商品特惠套餐以及用户所需数目。

public class LowestPrice {

	public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
		return shopping(price, special, needs);
	}

	public int shopping(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
		try {
			if(price.size() > 6) {
				throw new RIException("输入的price多于6种,不符合要求");
			}
			if(special.size() > 100) {
				throw new RIException("输入special多余100种,不符合要求");
			}
			if(needs.size()!=price.size()) {
				throw new RIException("输入的price与nends关系不符合输入要求,种类数目不一样");
			}
		}catch(RIException ex) {
			ex.printStackTrace(System.out);
			return -1;
		}
		int j = 0, res = dot(needs, price);
		if(res == 0) {
			return 0;
		}
		for (List<Integer> s : special) {
			List<Integer> clone = new ArrayList<>(needs);
			for (j = 0; j < needs.size(); j++) {
				int diff = clone.get(j) - s.get(j);
				if (diff < 0)
					break;
				clone.set(j, diff);
			}
			if (j == needs.size())
				res = Math.min(res, s.get(j) + shopping(price, special, clone));
		}
		return res;
	}

	public int dot(List<Integer> a, List<Integer> b) {
		int sum = 0;
		for (int i = 0; i < a.size(); i++) {
			sum += a.get(i) * b.get(i);
		}
		return sum;
	}
}

二、AF
AF又叫抽象函数。
抽象函数:R和A之间映射关系的函数,即如何去解释R中的每一个值为A中的每一个值。
AF : R → A
AF:满射、非单射、未必双射→R中的部分值并非合法的,在A中无映射值。
先不谈AF的映射合法性,从上面的例子来看,AF也就是从List price, List<List> special, List needs向商品种类价格,商品特惠套餐以及用户所需数目的一组一一映射。
从而撰写AF:

		/**
		 * Abstraction function:
		 * price:商品各个种类及其价格,其中种类是key,而价格是value
		 * special:商品的各种优惠套餐,每个数组的前n(n为商品种类)个
		 * 			为商品个数,第n+1个为套餐价格
		 * needs:分别为每种商品的客户所需数目
		 */

三、RI
RI:将rep值映射到布尔值的rep不变量
RI : R → boolean
对于代表值r,RI(r)是真的,如果且仅当r由AF映射
换句话说,RI告诉我们给定的rep值是否格式良好;或者,可以将RI看作一个集合:它是定义AF的rep值的子集。

总的来说,可以把RI看成一个描述合法化的不变量,即描述AF中所合法的东西。回归上面所说的A空间,RI就是去除了A空间中的不合法化的对象,并让程序员有所实现。
因此,我们根据规约中对于合法性要求的一部分,对于RI进行撰写,首先看规约中对于合法性的要求:

/** 
* Note:
 * 
 * 1. There are at most 6 kinds of items, 100 special offers.
 * 
 * 2. For each item, you need to buy at most 6 of them.
 * 
 * 3. You are not allowed to buy more items than you want, even if that would
 * lower the overall price.
 * /

因此我们得知了对于传入参数List price, List<List> special, List needs的要求,撰写RI:

		/**
		 * Representation invariant:	
		 * price的元素个数多余6个;
		 * special的元素个数少于等于100个
		 * needs中的元素不能大于6
		 */

并在代码中进行相应的实现与检查:

try {
			if(price.size() > 6) {
				throw new RIException("输入的price多于6种,不符合要求");
			}
			if(special.size() > 100) {
				throw new RIException("输入special多余100种,不符合要求");
			}
			if(needs.size()!=price.size()) {
				throw new RIException("输入的price与nends关系不符合输入要求,
										种类数目不一样");
			}
			for(int i = 0;i<needs.size();i++) {
				if(needs.get(i) > 6) {
					throw new RIException("买的商品数目过多");
				}
			}
		}catch(RIException ex) {
			ex.printStackTrace(System.out);
			return -1;
		}

四、Documenting rep exposure safety argument
表示泄漏的安全声明。
这是一个注释,它检查rep的每个部分,查看处理该部分rep的代码(特别是有关参数和来自客户机的返回值的代码,因为这是rep公开发生的地方),并给出代码不公开rep的原因。
给出理由,证明代码并未对外泄露其内部表示——自证清白。