dyerac  
dyerac In Java
公告

日历
<2007年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234
统计
  • 随笔 - 36
  • 文章 - 10
  • 评论 - 94
  • 引用 - 0

导航

常用链接

留言簿(5)

随笔分类(49)

随笔档案(36)

文章分类(11)

文章档案(10)

相册

dyerac

搜索

  •  

积分与排名

  • 积分 - 78536
  • 排名 - 707

最新随笔

最新评论

阅读排行榜

评论排行榜

 

转的这篇文章虽然是讲动态代理的
但是其中涉及到了Decorator模式 也是一个学习的亮点




-----------------------------------------------------------------------------------------------------
记忆是衍生自Lisp,Python,和Perl等过程性语言的一种设计模式,它可以对前次的计算结果进行记忆。 一个实现了记忆功能的函数, 带有显式的cache, 所以, 已经计算过的结果就能直接从cache中获得, 而不用每次都进行计算.
记忆能显著的提升大计算量代码的效率. 而且是一种可重用的方案.
本文阐述了在Java中使用这一模式的方法,并提供了一个可以提供上述功能的"记忆类":
     Foo foo = (Foo) Memoizer.memoize(new FooImpl());
     这里,Foo是一个接口,它含有的方法是需要记忆的.FooImpl是Foo的一个实现.foo是Foo的一个引用.方法与FooImpl基本相同,区别在于Foo返回的值,会被缓存起来.单个记忆类的优点在于为任何类添加记忆功能是很简单的:定义一个包含需要记忆的方法的接口,然后调用memoize来实现一个实例.

    为了理解记忆类是怎么实现的,我们将分几步来解释.首先,我解释一下为何缓存能够在需要它的类中实现.然后,我测试一下如何为一个特定的类添加缓存包装器.最后,我解释一下如何才能使得一个缓存包装器能够通用于任意的类.

为大计算量的程序添加缓存
    作为一个大计算量程序的例子,我们考虑PiBinaryDigitsCalculator这个例子-计算二进制数据pi.仅有的public方法calculateBinaryDigit带有一个参数:整数n,代表需要精确到的位数.例如,1000000,将会返回小数点后的一百万位,通过byte值返回-每位为0或者1.(算法可以参考: http://www.cecm.sfu.ca/~pborwein/PAPERS/P123.pdf)

public class PiBinaryDigitsCalculator {
  /**
   * Returns the coefficient of 2^n in the binary
   * expansion of pi.
   * @param n the binary digit of pi to calculate.
   * @throws ValidityCheckFailedException if the validity
   * check fails, this means the implementation is buggy
   * or n is too large for sufficient precision to be
   * retained.
   */
  public byte calculateBinaryDigit(final int n) {
      return runBBPAlgorithm(n);
  }
    
  private byte runBBPAlgorithm(final int n) {
      // Lengthy routine goes here ...
  }

}

    最简单直接的方法来缓存返回值可以通过修改这个类来实现:添加一个Map来保存之前计算得到的值,如下:
import java.util.HashMap;

public class PiBinaryDigitsCalculator {

  private HashMap cache = new HashMap();

  public synchronized byte calculateBinaryDigit(
  final int n) {

      final Integer N = new Integer(n);
      Byte B = (Byte) cache.get(N);
      if (B == null) {
          byte b = runBBPAlgorithm(n);
          cache.put(N, new Byte(b));
          return b;
      } else {
          return B.bytevalue();
      }
  }

  private byte runBBPAlgorithm(final int n) {
      // Lengthy routine goes here ...
  }
}

 
    calculateBinaryDigit方法首先会检查HashMap里面是否缓存了这个关键字-参数n,如果找到了,就直接返回这个值.否则,就会进行这个冗长的计算,并将结果保存到缓存里面.在添加进HashMap的时候,在原始类型和对象之间还要进行小小的转换.
    尽管这个方法是可行的,但是有几个缺点.首先,进行缓存的代码和正常的算法代码不是显著分开的.一个类,不仅负责进行计算,也要负责进行维护缓存数据.这样,要进行一些测试就会显得很困难.比如,不能写一个测试程序来测试这个算法持续地返回相同的值,因为,从第二次开始,结果都是直接从cache中获得了.
    其次,当缓存代码不再需要,移除它会变得困难,因为它和算法块地代码是紧密结合在一起的.所以,要想知道缓存是否带来了很高的效率提升也是很困难的,因为不能写一个测试程序是和缓存数据分开的.当你改进了你的算法,缓存有可能失效-但是这个时候你并不知道.
    第三,缓存代码不能被重用.尽管代码遵从了一个普通的模式,但是都是在一个类- PiBinaryDigitsCalculator里面.

    前面两个问题都可以通过构造一个缓存包装器来解决.

缓存包装器
    通过使用Decorator模式,要分开计算代码和缓存代码是很容易的.首先,定义一个接口,里面定义基本的方法.
     public interface BinaryDigitsCalculator {

  public byte calculateBinaryDigit(final int n);
}

    

    然后定义两个实现,分别负责两个任务:
public class PiBinaryDigitsCalculator
  implements BinaryDigitsCalculator {

  public byte calculateBinaryDigit(final int n) {
      return runBBPAlgorithm(n);
  }

  private byte runBBPAlgorithm(final int n) {
      // Lengthy routine goes here ...
  }

}

import java.util.HashMap;

public class CachingBinaryDigitsCalculator implements
BinaryDigitsCalculator {

  private BinaryDigitsCalculator binaryDigitsCalculator;
  private HashMap cache = new HashMap();

  public CachingBinaryDigitsCalculator(
  BinaryDigitsCalculator calculator) {
      this.binaryDigitsCalculator = calculator;
  }

  public synchronized byte calculateBinaryDigit(int n) {
      final Integer N = new Integer(n);
      Byte B = (Byte) cache.get(N);
      if (B == null) {
          byte b =
            binaryDigitsCalculator.calculateBinaryDigit(n);
          cache.put(N, new Byte(b));
          return b;
      } else {
          return B.bytevalue();
      }
  }
}

    
    这是很之前的实现PiBinaryDigitsCalculator的一种简单的refactored版本. CachingBinaryDigitsCalculator包装了BinaryDigitsCalculator句柄,并增加了缓存,供calculateBinaryDigit的方法调用. 这种方法提高了代码的可读性与可维护性. 用户不能直接使用BinaryDigitsCalculator接口来实现算法,所以,如果需要关闭缓存块,将是很容易实现的.
    还有,合适的测试程序很容易写出来.比如,我们写一个假的BinaryDigitsCalculator实现,每次calculateBinaryDigit被调用,赋予相同的参数,返回不同的值. 这样,我们就能测试缓存是否工作了,因为如果每次都返回相同的值,则证明缓存是正常工作了. 这种测试在之前那种简单的实现是不可能的.

这是很之前的实现PiBinaryDigitsCalculator的一种简单的refactored版本. CachingBinaryDigitsCalculator包装了BinaryDigitsCalculator句柄,并增加了缓存,供calculateBinaryDigit的方法调用. 这种方法提高了代码的可读性与可维护性. 用户不能直接使用BinaryDigitsCalculator接口来实现算法,所以,如果需要关闭缓存块,将是很容易实现的.

    还有,合适的测试程序很容易写出来.比如,我们写一个假的BinaryDigitsCalculator实现,每次calculateBinaryDigit被调用,赋予相同的参数,返回不同的值. 这样,我们就能测试缓存是否工作了,因为如果每次都返回相同的值,则证明缓存是正常工作了. 这种测试在之前那种简单的实现是不可能的。
通过动态代理类来创建一个通用的缓存包装器\r

    上面第二种方法仅有的缺点就是缓存包装器不能重用,每次我们希望添加一个缓存给某个类,我们就要写一个特殊的缓存包装器给目标接口.这是一个很慢,容易出错的过程.

    Jdk1.3开始支持动态代理类: 特别的类能够在运行期决定实现哪个接口-通常的模式都是,在运行期即决定实现哪个接口.通过这个,我们有可能实现一个通用的缓存包装器,我们称它为Memoizer,在运行期决定实现哪个接口.这样, CachingBinaryDigitsCalculator就是不再需要的.它是这样被调用的:

BinaryDigitsCalculator calculator =
new CachingBinaryDigitsCalculator(
new PiBinaryDigitsCalculator()
);  

    可以通过Memoizer来重写如下:

BinaryDigitsCalculator calculator =
(BinaryDigitsCalculator) Memoizer.memoize(
new PiBinaryDigitsCalculator()
);

Memoizer的代码如下:

package demo.proxy;

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Memorizer implements InvocationHandler {
    
public static Object memorize(Object object) {
        
return Proxy.newProxyInstance(object.getClass().getClassLoader(),
                object.getClass().getInterfaces(), 
new Memorizer(object));
    }


    
private Object object;

    
private Map caches = new HashMap();

    
private Memorizer(Object object) {
        
this.object = object;
    }


    
public Object invoke(Object proxy, Method method, Object[] args)
            
throws Throwable {
        
// Don't cache void methods
        if (method.getReturnType().equals(Void.TYPE)) {
            
return invoke(method, args);
        }
 else {
            Map cache 
= getCache(method);
            List key 
= Arrays.asList(args);
            Object value 
= cache.get(key);
            
if (value == null && !cache.containsKey(key)) {
                value 
= invoke(method, args);
                cache.put(key, value);
            }

            
return value;
        }

    }


    
private Object invoke(Method method, Object[] args) throws Throwable {
        
try {
            
return method.invoke(object, args);
        }
 catch (InvocationTargetException e) {
            
throw e.getTargetException();
        }

    }


    
private synchronized Map getCache(Method m) {
        Map cache 
= (Map) caches.get(m);
        
if (cache == null{
            cache 
= Collections.synchronizedMap(new HashMap());
            caches.put(m, cache);
        }

        
return cache;
    }

}
 



当调用静态方法memoize的时候,将会创建一个新的代理实例-也就是一个java.lang.reflect.proxy的实例.实现了一个接口集.这个接口集由object.getClass().getInterfaces()来决定.每个代理实例包含一个java.lang.reflect.InvocationHandler实例来处理这个代理实例调用的相关方法.在我们的例子里,Memoizer就是一个InvocationHandler实例.

    当一个方法在代理实例里被调用,比如, calculateBinaryDigit,那么, Memoizer实例里的invoke方法就会被调用,相关信息会传给invoke方法,以决定proxy实例调用了哪个方法,包含参数信息.在我们的例子里,传入Memoizer的java.lang.Method参数是calculateBinaryDigit,而参数信息则是pi需要精确的位数-整数n.在这个基础上,Memoizer能够进一步进行缓存操作的.

    在例子里(caches是一个Hashmap,cache是一个map)里用到的Key,主要是传入的方法信息:Method对象和参数对象. 为了实现的简单与通用性,Memoizer有一个关于cache的HashMap caches,每个method是一个key,对应的value为一个cache.然后把参数信息转化成一个List对象,作为cache的Key.使用List是很方便的,同时也可以保证equals()方法,所以能够保证当且仅当参数信息完全相同的时候这个List才相等.

    一旦一个cache的Key被创建,那么,计算之前都会先查找这个cache,如果找到,则返回cache里的值.否则,如果带有这些参数的这个方法没有被调用过,那么,则会通过invoke来调用这个method.在我们的例子里, 实例PiBinaryDigitsCalculator 里的calculateBinaryDigit方法将会通过invoke被调用.而且计算结果将会被存在cache里.
何时使用Memoizer

    作为一条通用的规则,Memoizer能够在任何需要传统的cache的时候使用-比如上面提到的例子. 特别地,接口里每个需要使用记忆功能的method需要满足下面几条条件:

    1. 这个method的返回值最好不要每次调用都会改变\r

    2. 这个method不要有副效应

    3. 这个method的参数是确定的,非mutable的.

    显然,如果每次调用这个method返回值都不同,那么cache就毫无用处了.同样也是很重要的一点是,因为有副效应的method不会被重复,所以这个method不能有副效应(method自动更新某些状态).当然,void方法除外.

    同样,memorize一个带有未定(mutable)参数的method是很危险的,因为,要把这些参数储存到hashmap里会是很危险的一件事.根据Map的定义,当这个Map里的key发生改变,Map是不知道的.所以,当你执行了一次这个method之后,相关信息添加进了Map,然后参数发生变异(mutate),第二次调用的时候,就会得到错误的结果.

    性能

    使用cache的主要目的就是为了提升你的程序的速度.然而,reflection确是众所周知的低效(在jdk1.4里有所改进,通过reflection调用方法是普通调用速度的1/2,这个比jdk1.3要快40倍).Memoizer主要依靠reflection来调用方法,所以,它看上去并不是一个好的途径.但是,如果使用cache能给程序速度带来的提升远高于reflection对速度的影响,那么,使用Memoizer是值得考虑的.

    在我们对PiBinaryDigitsCalculator的测试中,测试环境为jdk1.4,当n小于10的时候,使不使用cache速度是相当的.但是,当n增大的时候,使用cache的优势就开始显示出来.所以,经常使用PiBinaryDigitsCalculator的用户,可以考虑使用cache.

    不幸的是,唯一测试你的程序是否需要cache的途径是比较你的程序在两种情况下的运行效率.尽管如此,因为为一个程序构造一个cache包装器是很容易的一件事,移除它也是很容易的,下面的建议可以作为一个参考的步骤:

    1. 选择需要记忆操作的类\r

    2. 运行它\r

    3. 如果效率是满意的,go to 6

    4. 添加memoizer,使用cache

    5. 如果效率没有显著提升,移初memoizer

    6. 如果需要,重试.

    理论上,你需要分析为一个类添加记忆功能对整个系统的影响.只有你自己清楚是否值得添加.有些方法,即使是计算量很大的,但是在这个系统里很少被调用,所以,没必要为它添加记忆功能.为了保证这个,我开发了一个更有特点的Memoizer,实现了一个叫做CacheStatistics的接口,你能从它得到cache的数量以及无效的cache.你可以使用它作为判断的一个尺度.

    扩展Memoizer

    修改Memoizer类来支持不同的cache策略是很简单的.一个比较普通的类型就是Least-Recently-Used(LRU)cahce,拥有固定数量的入口.这个cache确保入口不大于它的最大数目,如果超过,就摒弃最旧的缓存数据.也就是,能够从cache里得到的是新的数据.一个类可以使用LRU cache来防止一个程序长期保持一个状态.你可以仅仅传递一个参数给CacheFactory里的memoize方法来选择你需要的cache类型.下面的例子,LRU cache最多有1000个入口:

BinaryDigitsCalculator calculator =
(BinaryDigitsCalculator) Memoizer.memoize(
new PiBinaryDigitsCalculator(),
new LruCacheFactory(1000)
);

    即使是这么简单,Memoizer也应该是java程序员一个有用的工具.

posted on 2007-07-24 14:03 dyerac in java... 阅读(734) 评论(0)  编辑  收藏 所属分类: JavaSE

只有注册用户登录后才能发表评论。


网站导航:
 
 
Copyright © dyerac in java... Powered by: 博客园 模板提供:沪江博客