庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

习题3.12,append不是改变函数,不会改变x的结构。append!是改变函数,显然第一个response是(b),第二个就是(b c d)。图就不画了,画了一次太麻烦了。

习题3.13,利用set-cdr!形成环,比较有意思:
(define z (make-cycle (list 'a 'b 'c 'd)))

z在DrScheme上表示为:
#0=(a b c d . #0#)

形象地展示了一个环,显然运行(last-pair z)将陷入无限递归,因为(null? (cdr x))永远不会为真。

习题3.14,这道题运行下就知道了,是个倒排list的过程,分析下(mystery v)的运行过程:
(loop (a b c d) '())
(loop (b c d) (a '()))
(loop (c d) (b a))
(loop (d) (c b a))
(loop '() (d c b a))

习题进度落后于读书进度,残念。



posted @ 2007-10-18 15:56 dennis 阅读(449) | 评论 (0)编辑 收藏

    最近被换工作的事情搞的心烦意乱,几本正在读的技术书进度都慢了下来。上周末,老婆回家参加同学婚礼,一个人去书店瞎逛,随手拿起了温伯格的《理解专业程序员》,读了几个短篇就被吸引住了。见天色已晚,遂买之回家,细细品读。这本书是由一篇篇短小精悍的文章组成,按一定的主题组织在一起,你想知道如何称为一名程序员吗?什么才算是专业的程序员?程序员如何提高绩效?如何更有效地进行思考?大师用几十年的从业经验为你慢慢道来。
    专业?到底什么样的人才称得上专业的程序员?温伯格说,计算机编程领域具备了不起的技艺或经验的那些人才能算得上是专业程序员。“技艺”这个词用的很恰当。那么,要多长的时间才能称为专业的人呢?大师的意见是怎么也得15年,15年以内的只能称为业余程序员或者“不那么专业的程序员”。呵呵,我也曾在外行人面前冒充过专业程序员,想想都汗颜,当得上“专业”两个字不仅仅是15年的从业经历,更多是这15年中你做了什么,创造了什么,学到了什么。经验与技艺缺一不可。书中充满了真知灼见,有些故事让你觉的脸红,因为那些愚蠢的事情正是你不断重复的;有些经验让你觉的很熟悉,是啊,我们就是这样干的!而有些见解其实是一些励志书籍不断重复的老套教条,尽管老套,但是没有经历的人终究是难以理解的,我也不例外。这本书值的在以后多年的日子里重读几遍。

posted @ 2007-10-17 16:38 dennis 阅读(531) | 评论 (2)编辑 收藏

    hack有水平高低之分,最近看到一个blog,牛人的hack水平让你不得不服。情况是这样的,牛人在使用 mongrel_light_cluster的过程中,发现这个cluster违反了copy-on-write的语义,导致占用了太多的内存。根本原因在于Ruby的GC机制是marks all memory pages as dirty。为了减少内存的占用,让集群跑更多mongrel,牛人走上了hack之路,给c ruby打补丁,他也真的做到了。c ruby的GC使用的是mark and sweep(标记并清除)的垃圾收集算法,他发现在mark过程中使用了st_table,这个数据结构占用了很大的内存,那么就改用Google’s sparse_hash。然后他又写了一个memory pool,以应对marking和sweep使用过程中对malloc和free调用带来的内存损失,因为在x86 GNU/linux gcc上,malloc函数如果申请的内存小于76KB,那么当free的时候这些内存不会被返还给操作系统。他的hack之路还没结束,有兴趣的关注他的blog:

 http://izumi.plan99.net/blog/index.php/


posted @ 2007-10-15 09:09 dennis 阅读(667) | 评论 (0)编辑 收藏

    昨天晚上搞到深夜,终于将资源模块搞定。到今天已经完成的功能包括:
1.四种基本路由:顺序、选择、并行、循环
2.流程定义文件和系统配置文件的读取和解析
3.使用内存作为流程数据和案例数据存储的MemoryWorkFlowDAO的开发
4.资源模块的开发
5.并发情况下的正确性测试等

    计划中的功能:
1.一个GUI的流程定义工具,这个不急,也还没想好用什么做,web还是桌面?
2.各个数据库版本的WorkFlowDAO的开发,将流程数据和案例数据保存在数据库中。
3.更多的测试和example试验。

    回到资源这个概念,工作流中工作项(work item)的由资源来驱动的,这个资源(resource)可能是用户、角色、定时时间或者某个事件消息。在标准petri网中,工作项对应于transition(变迁),变迁都是自动的,不需要所谓资源来驱动,显然,这与工作流系统不同。具体到insect workflow(我取的名字,小巧之意),每个transition都有一个resource,用于驱动自身的firing,所有的resource都实现Resource接口:
public interface Resource extends Serializable {

    
public void start(Transition transition, Token token, Object args);
           
    
public ResourceType getType();

    
public long getId();

}
    每个资源都有一个类型,以及这个类型中独一无二的id,start方法用于驱动transtion的firing。一般情况下,你不需要实现这个接口,只要继承这个接口的抽象实现类AbstractResource,AbstractResource的start方法默认实现是首先调用模板方法doAction(稍后解释),然后检查触发条件,如果通过就直接调用transition的fire方法:
public abstract class AbstractResource implements Resource {
         
    
public void start(Transition transition, Token token, Object args) {
        doAction(transition, token, args);

        
if (transition.getCondition() != null
                
&& !transition.getCondition().check(token))
            
throw new ConditionException(transition.getName()
                    
+ " transition没有满足触发条件");
        transition.fire(token, args);
    }
    
public abstract void doAction(Transition transition, Token token,
            Object args)
;
       
}

    Transtion类的fire方法有三个操作组成:从输入库所移走token,往输出库所放入token,回调handler:
    public void fire(Token token, Object args) {
        removeTokenFromInputs(token);
        addTokenToOutputs(token);
        invokeHandler(token, args);
    }
    那么具体的资源显然要实现AbstractResource中的doAction抽象方法,系统内置了五种资源:自动资源(AutoResource)、用户(User)、用户组(Group)、定时器(TimerResource)和事件监听器(ObserverResource)。显然,AutoResource、User和Group的doAction方法不需要做任何事情:
public class User extends AbstractResource {
    
protected Group group;
            
    @Override
    
public void doAction(Transition transition, Token token, Object arg){
    }

}
   
    而TimerResource就需要做特殊处理了,比如我们要达到这样的效果:节点1状态已经处于就绪,可以被触发,可我们希望在就绪后延迟半分钟再触发,或者在晚上10点触发等等。这样的定时需求很常见,我采用了jdk5引入的ScheduledExecutorService来处理。系统中启动这样一个线程池,每个类似上面的请求都提交给这个线程池来处理,那么TimerResource就需要进行相应的修改:
public abstract class TimerResource extends AbstractResource {

    
protected int pool_size;

    
protected static ScheduledExecutorService scheduledExecutorService;

    @Override
    
public long getId() {
        
// TODO Auto-generated method stub
        return Common.TIMER_RESOURCE_ID;
    }

    
public TimerResource() {
        
this.pool_size = 5;
        scheduledExecutorService 
= Executors.newScheduledThreadPool(pool_size);
    }

    
public static void shutdownPool() {
        
if (scheduledExecutorService != null)
            scheduledExecutorService.shutdown();
    }

    
public final void start(Transition transition, Token token, Object args)
            
throws InterruptedException {
        
if (transition.getCondition() != null
                
&& !transition.getCondition().check(token))
            
throw new ConditionException(transition.getName()
                    
+ " transition没有满足触发条件");
        transition.removeTokenFromInputs(token);
        doAction(transition, token, args);
    }

    
protected class ChangeRunner implements Runnable {
        
private Transition transition;

        
private Token token;

        
private Object[] args;

        
public ChangeRunner(Transition transition, Token token, Object args) {
            
this.transition = transition;
            
this.token = token;
            
this.args = args;
        }

        
public void run() {
            
if (transition.getCondition() != null
                    
&& !transition.getCondition().check(token))
                
throw new ConditionException(transition.getName()
                        
+ " transition没有满足触发条件");
            transition.addTokenToOutputs(token);
            Object real_args[] 
= new Object[args.length - 2];
            
for (int i = 0; i < real_args.length; i++)
                real_args[i] 
= args[i + 2];
            transition.invokeHandler(token, real_args);
            
try {
                
// 回调
                ((WorkFlowAlgorithm) args[1]).enabledTraversing(token
                        .getWorkFlow());
                ((WorkFlowManager) args[
0]).doAction(token.getId());

            } 
catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
}
    注意到,start方法不再是直接调用transition的fire方法,而仅仅是进行了第一步操作:移除输入库所的place防止重复提交。后两步操作都延迟到了提交给线程池的任务中,也就是代码中的ChangeRunner类中的run方法。例如TimerResource的子类DelayTimerResource用于处理延迟的触发,doAction就像这样:
public class DelayTimerResource extends TimerResource {
    
    @Override
    
public void doAction(Transition transition, Token token, Object args){
        scheduledExecutorService.schedule(
new ChangeRunner(transition, token,
                args), 
this.delay, this.timeUnit);

    }
}
    延迟的时间,时间单位这些信息都可以在流程定义文件中设置。事件监听器资源与此类似,ObserverResource实现了java.util.Observer接口,往输出库所放入token和回调handler两步操作被放在了update方法中提供给Subject回调。
   


posted @ 2007-10-13 17:15 dennis 阅读(699) | 评论 (0)编辑 收藏

    上午测试了下并发情况下的表现,测试场景:一个有20个节点,包括选择、顺序、并行路由的流程,所有节点都设置为自动执行,1000个线程并发启动案例,也就是这个流程同时有1000个案例在跑,全部跑完结果差强人意,比单线程慢了接近30倍。仔细调整了算法和加锁粒度,尽管整体性能有所提高,但是多线程和单线程间执行的差距仍然没有多大变化,性能瓶颈还是在核心的调度算法上,还需要分析下。测试程序如下:
package net.rubyeye.insect.workflow.test;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CyclicBarrier;

import net.rubyeye.insect.workflow.Place;
import net.rubyeye.insect.workflow.Token;
import net.rubyeye.insect.workflow.Transition;
import net.rubyeye.insect.workflow.WorkFlow;
import net.rubyeye.insect.workflow.WorkFlowManager;
import net.rubyeye.insect.workflow.basic.BasicWorkflowManager;
import net.rubyeye.insect.workflow.comm.TransitionType;
import net.rubyeye.insect.workflow.config.DefaultConfiguration;
import junit.framework.TestCase;

public class CompositeProcessTest extends TestCase {
    
private WorkFlowManager wm;

    WorkFlow composite;

    
private CyclicBarrier barrier;

    
private static final int total = 1000;

    @Override
    
protected void setUp() throws Exception {
        
this.barrier = new CyclicBarrier(total + 1);
        wm 
= new BasicWorkflowManager();
        wm.setConfiguration(
new DefaultConfiguration());

        WorkFlow sequence 
= wm.getWorkFlow("sequence");
        WorkFlow concurrency 
= wm.getWorkFlow("concurrency");
        WorkFlow choose 
= wm.getWorkFlow("choose");

        
// 组合流程
        composite = new WorkFlow();
        composite.setName(
"composite");
        composite.setId(
100);

        wm.saveWorkFlow(composite);

        
// 修改开始结束节点的输入输出库所
        sequence.getEnd().setType(TransitionType.NORMAL);
        sequence.getEnd().setOutputs(concurrency.getStart().getInputs());

        concurrency.getEnd().setType(TransitionType.NORMAL);
        concurrency.getEnd().setOutputs(choose.getStart().getInputs());

        composite.setStart(sequence.getStart());
        composite.setEnd(choose.getEnd());
        List
<Transition> transitions = new ArrayList<Transition>();
        transitions.addAll(sequence.getTransitions());
        transitions.addAll(concurrency.getTransitions());
        transitions.addAll(choose.getTransitions());
        composite.setTransitions(transitions);
    }

    
public void testConcurrencyCompositeProcesss() throws Exception {
        
for (int i = 0; i < total; i++) {
            
new FlowThread().start();
        }
        barrier.await();
        
long start = System.currentTimeMillis();
        barrier.await();
        
long end = System.currentTimeMillis();
        System.out.println(
"创建" + total + "个流程并发运行完毕\n花费时间:" + (end - start)
                
/ 1000.0 + "");
        
for (Transition transition : composite.getTransitions()) {
            System.out.println(transition.getName() 
+ "  "
                    
+ transition.isEnable());
            
for (Place place : transition.getOutputs()) {
                System.out.println(
"place " + place.getId() + " "
                        
+ place.getTokens().size());
            }
        }
    }

    
public void testCompositeProcesss() throws Exception {
        
long start = System.currentTimeMillis();
        
for (int i = 0; i < total; i++) {
            Token token1 
= wm.startWorkFlow("composite");
            token1.setAttribute(
"name""dennis");
            token1.setAttribute(
"num"21);
            wm.doAction(token1.getId());
            assertTrue(token1.isFinished());
        }
        
long end = System.currentTimeMillis();
        System.out.println(
"创建" + total + "个流程运行完毕\n花费时间:" + (end - start)
                
/ 1000.0 + "");
    }

    
class FlowThread extends Thread {

        @Override
        
public void run() {
            
try {
                barrier.await();
                
// wm = new BasicWorkflowManager();
                Token token1 = wm.startWorkFlow("composite");
                token1.setAttribute(
"name""dennis");
                token1.setAttribute(
"num"21);
                wm.doAction(token1.getId());
                assertTrue(token1.isFinished());
                barrier.await();
            } 
catch (Exception e) {
                
throw new RuntimeException(e);
            }
        }

    }
}

posted @ 2007-10-12 13:01 dennis 阅读(1065) | 评论 (9)编辑 收藏

    hoho,今天完成了选择路由的实现,完成了配置文件的读写和解析,流程定义文件还是决定采用xml文件,不过与其他工作流引擎采用的xml完全不同,因为是基于petri网的,因此引入了place的概念,比如下面这个4个节点的顺序路由的流程:
<workflow maxCases="100">
    
<node type="start" name="start" id="0">
        
<inputs>
            
<place id="1" />
        
</inputs>
        
<outputs>
            
<place id="2" />
        
</outputs>
    
</node>
    
<node name="hello" id="1" resource="user">
        
<conditions type="and">
            
<condition
                
class="net.rubyeye.insect.workflow.impl.NullHandler" value="false"
                variable-name
="name" />
        
</conditions>
        
<handler
            
class="net.rubyeye.insect.workflow.test.HelloWorldHandler" />
        
<inputs>
            
<place id="2" />
        
</inputs>
        
<outputs>
            
<place id="3" />
        
</outputs>
    
</node>
    
<node name="calc" id="2" resource="user">
        
<conditions type="and">
            
<condition variable-name="num">
                
<exp>
                    
<![CDATA[num<=1000]]>
                
</exp>
            
</condition>
            
<conditions type="or">
                
<condition variable-name="num">
                    
<exp>
                        
<![CDATA[num>=10]]>
                    
</exp>
                
</condition>
                
<condition
                    
class="net.rubyeye.insect.workflow.impl.NullHandler" value="false"
                    variable-name
="name" />
            
</conditions>
        
</conditions>
        
<handler
            
class="net.rubyeye.insect.workflow.test.CalculateHandler" />
        
<inputs>
            
<place id="3" />
        
</inputs>
        
<outputs>
            
<place id="4" />
        
</outputs>
    
</node>
    
<node type="end" name="hello" id="3">
        
<inputs>
            
<place id="4" />
        
</inputs>
        
<outputs>
            
<place id="5" />
        
</outputs>
    
</node>
</workflow>
   
并行路由和选择路由引入了and-split,and-join,or-split,or-join四种transition,比如and-split,它就有多个输出place:

<node name="split" type="and-split" id="1" resource="user">
        
<inputs>
            
<place id="2" />
        
</inputs>
        
<outputs>
            
<place id="3" />
            
<place id="4" />
        
</outputs>
    
</node>

   Place和Transition都有条件,用于决定操作是否执行,Transition额外指定了驱动的资源以及回调的handler,这一点非常重要,资源可能是用户、用户组、某个时间点定时事件、特定消息等等。
   今天额外发现的一个好处就是,引入Place之后,我可以轻易地将不同的流程连接起来组织成一个更复杂的流程,仅仅是需要修改各个流程的开始和结束的节点的输入输出库所,从而实现了层次化的Petri网,,类似代码:
WorkFlow sequence = wm.getWorkFlow("sequence");
        WorkFlow concurrency 
= wm.getWorkFlow("concurrency");
        WorkFlow choose 
= wm.getWorkFlow("choose");

        
//组合流程
        composite = new WorkFlow();
        composite.setName(
"composite");
        composite.setId(
100);
        
        wm.saveWorkFlow(composite);

        
//修改开始结束节点的输入输出库所
        sequence.getEnd().setType(TransitionType.NORMAL);
        sequence.getEnd().setOutputs(concurrency.getStart().getInputs());

        concurrency.getEnd().setType(TransitionType.NORMAL);
        concurrency.getEnd().setOutputs(choose.getStart().getInputs());
        
        composite.setStart(sequence.getStart());
        composite.setEnd(choose.getEnd());
        List
<Transition> transitions = new ArrayList<Transition>();
        transitions.addAll(sequence.getTransitions());
        transitions.addAll(concurrency.getTransitions());
        transitions.addAll(choose.getTransitions());
        composite.setTransitions(transitions);




posted @ 2007-10-11 16:51 dennis 阅读(557) | 评论 (0)编辑 收藏

    写一个简单的工作流一直停留在我的“计划”中,最近趁改造绩效系统的机会,决定自己写一个基于petri网原理的工作流来改写绩效考核流程部分。基于petri网的工作流的基本算法,就是当每一个firing发生后,应当遍历整个流程重新改变transition的enable,那么当资源驱动某个transition其实就是将它的输入place中的token转移到输出place。大概的接口类似:

WorkFlowManager wm = new BasicWorkflowManager(this.workFlowDAO);
Token token1 = wm.startWorkFlow(0); //为流程0新启动一个案例
wm.doAction(token1,resource,args);  //传入资源和参数以驱动firing

今天完成了顺序路由和并行路由的实现,选择和循环也准备加入。暂时只实现了内存存储案例数据和流程数据,显然,应当实现一个数据库版本,慢慢来吧。

posted @ 2007-10-10 18:03 dennis 阅读(891) | 评论 (0)编辑 收藏

    引入了赋值之后,代换模型失效,3.2小节引入了环境模型。3.9题用于考察对环境模型的理解。递归版本的(factorial 6)的环境结构如下图:
   
    blogjava不允许太长的图片,省略了n=3,2,1的三个frame,这些frame的关联环境都是全局环境。
    再看看迭代版本的(factorial 6)的环境结构,同样省去了部分迭代过程,当counter=7的时候迭代停止:



posted @ 2007-10-08 14:55 dennis 阅读(382) | 评论 (0)编辑 收藏

update1:第二个实现,读操作不必要采用独占锁,缓存显然是读多于写,读的时候一开始用独占锁是考虑到要递增计数和更新时间戳要加锁,不过这两个变量都是采用原子变量,因此也不必采用独占锁,修改为读写锁。
update2:一个错误,老是写错关键字啊,LRUCache的maxCapacity应该声明为volatile,而不是transient。
  
   最简单的LRU算法实现,就是利用jdk的LinkedHashMap,覆写其中的removeEldestEntry(Map.Entry)方法即可,如下所示:
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.Map;


/**
 * 类说明:利用LinkedHashMap实现简单的缓存, 必须实现removeEldestEntry方法,具体参见JDK文档
 * 
 * 
@author dennis
 * 
 * 
@param <K>
 * 
@param <V>
 
*/
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
    
private final int maxCapacity;

    
private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    
private final Lock lock = new ReentrantLock();

    
public LRULinkedHashMap(int maxCapacity) {
        
super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
        
this.maxCapacity = maxCapacity;
    }

    @Override
    
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        
return size() > maxCapacity;
    }
    @Override
    
public boolean containsKey(Object key) {
        
try {
            lock.lock();
            
return super.containsKey(key);
        } 
finally {
            lock.unlock();
        }
    }

    
    @Override
    
public V get(Object key) {
        
try {
            lock.lock();
            
return super.get(key);
        } 
finally {
            lock.unlock();
        }
    }

    @Override
    
public V put(K key, V value) {
        
try {
            lock.lock();
            
return super.put(key, value);
        } 
finally {
            lock.unlock();
        }
    }

    
public int size() {
        
try {
            lock.lock();
            
return super.size();
        } 
finally {
            lock.unlock();
        }
    }

    
public void clear() {
        
try {
            lock.lock();
            
super.clear();
        } 
finally {
            lock.unlock();
        }
    }

    
public Collection<Map.Entry<K, V>> getAll() {
        
try {
            lock.lock();
            
return new ArrayList<Map.Entry<K, V>>(super.entrySet());
        } 
finally {
            lock.unlock();
        }
    }
}
    如果你去看LinkedHashMap的源码可知,LRU算法是通过双向链表来实现,当某个位置被命中,通过调整链表的指向将该位置调整到头位置,新加入的内容直接放在链表头,如此一来,最近被命中的内容就向链表头移动,需要替换时,链表最后的位置就是最近最少使用的位置。
    LRU算法还可以通过计数来实现,缓存存储的位置附带一个计数器,当命中时将计数器加1,替换时就查找计数最小的位置并替换,结合访问时间戳来实现。这种算法比较适合缓存数据量较小的场景,显然,遍历查找计数最小位置的时间复杂度为O(n)。我实现了一个,结合了访问时间戳,当最小计数大于MINI_ACESS时(这个参数的调整对命中率有较大影响),就移除最久没有被访问的项:
package net.rubyeye.codelib.util.concurrency.cache;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 
 * 
@author dennis 类说明:当缓存数目不多时,才用缓存计数的传统LRU算法
 * 
@param <K>
 * 
@param <V>
 
*/
public class LRUCache<K, V> implements Serializable {

    
private static final int DEFAULT_CAPACITY = 100;

    
protected Map<K, ValueEntry> map;

    
private final ReadWriteLock lock = new ReentrantReadWriteLock();

    
private final Lock readLock = lock.readLock();

    
private final Lock writeLock = lock.writeLock();

    
private final volatile int maxCapacity;  //保持可见性

    
public static int MINI_ACCESS = 5;

    
public LRUCache() {
        
this(DEFAULT_CAPACITY);
    }

    
public LRUCache(int capacity) {
        
if (capacity <= 0)
            
throw new RuntimeException("缓存容量不得小于0");
        
this.maxCapacity = capacity;
        
this.map = new HashMap<K, ValueEntry>(maxCapacity);
    }

    
public boolean ContainsKey(K key) {
        
try {
            readLock.lock();
            
return this.map.containsKey(key);
        } 
finally {
            readLock.unlock();
        }
    }

    
public V put(K key, V value) {
        
try {
            writeLock.lock();
            
if ((map.size() > maxCapacity - 1&& !map.containsKey(key)) {
                
// System.out.println("开始");
                Set<Map.Entry<K, ValueEntry>> entries = this.map.entrySet();
                removeRencentlyLeastAccess(entries);
            }
            ValueEntry new_value 
= new ValueEntry(value);
            ValueEntry old_value 
= map.put(key, new_value);
            
if (old_value != null) {
                new_value.count 
= old_value.count;
                
return old_value.value;
            } 
else
                
return null;
        } 
finally {
            writeLock.unlock();
        }
    }

    
/**
     * 移除最近最少访问
     
*/
    
protected void removeRencentlyLeastAccess(
            Set
<Map.Entry<K, ValueEntry>> entries) {
        
// 最小使用次数
        long least = 0;
        
// 访问时间最早
        long earliest = 0;
        K toBeRemovedByCount 
= null;
        K toBeRemovedByTime 
= null;
        Iterator
<Map.Entry<K, ValueEntry>> it = entries.iterator();
        
if (it.hasNext()) {
            Map.Entry
<K, ValueEntry> valueEntry = it.next();
            least 
= valueEntry.getValue().count.get();
            toBeRemovedByCount 
= valueEntry.getKey();
            earliest 
= valueEntry.getValue().lastAccess.get();
            toBeRemovedByTime 
= valueEntry.getKey();
        }
        
while (it.hasNext()) {
            Map.Entry
<K, ValueEntry> valueEntry = it.next();
            
if (valueEntry.getValue().count.get() < least) {
                least 
= valueEntry.getValue().count.get();
                toBeRemovedByCount 
= valueEntry.getKey();
            }
            
if (valueEntry.getValue().lastAccess.get() < earliest) {
                earliest 
= valueEntry.getValue().count.get();
                toBeRemovedByTime 
= valueEntry.getKey();
            }
        }
        
// System.out.println("remove:" + toBeRemoved);
        
// 如果最少使用次数大于MINI_ACCESS,那么移除访问时间最早的项(也就是最久没有被访问的项)
        if (least > MINI_ACCESS) {
            map.remove(toBeRemovedByTime);
        } 
else {
            map.remove(toBeRemovedByCount);
        }
    }

    
public V get(K key) {
        
try {
            readLock.lock();
            V value 
= null;
            ValueEntry valueEntry 
= map.get(key);
            
if (valueEntry != null) {
                
// 更新访问时间戳
                valueEntry.updateLastAccess();
                
// 更新访问次数
                valueEntry.count.incrementAndGet();
                value 
= valueEntry.value;
            }
            
return value;
        } 
finally {
            readLock.unlock();
        }
    }

    
public void clear() {
        
try {
            writeLock.lock();
            map.clear();
        } 
finally {
            writeLock.unlock();
        }
    }

    
public int size() {
        
try {
            readLock.lock();
            
return map.size();
        } 
finally {
            readLock.unlock();
        }
    }

    
public long getCount(K key) {
        
try {
            readLock.lock();
            ValueEntry valueEntry 
= map.get(key);
            
if (valueEntry != null) {
                
return valueEntry.count.get();
            }
            
return 0;
        } 
finally {
            readLock.unlock();
        }
    }

    
public Collection<Map.Entry<K, V>> getAll() {
        
try {
            readLock.lock();
            Set
<K> keys = map.keySet();
            Map
<K, V> tmp = new HashMap<K, V>();
            
for (K key : keys) {
                tmp.put(key, map.get(key).value);
            }
            
return new ArrayList<Map.Entry<K, V>>(tmp.entrySet());
        } 
finally {
            readLock.unlock();
        }
    }

    
class ValueEntry implements Serializable {
        
private V value;

        
private AtomicLong count;

        
private AtomicLong lastAccess;

        
public ValueEntry(V value) {
            
this.value = value;
            
this.count = new AtomicLong(0);
            lastAccess 
= new AtomicLong(System.nanoTime());
        }

        
public void updateLastAccess() {
            
this.lastAccess.set(System.nanoTime());
        }

    }
}



posted @ 2007-09-29 17:49 dennis 阅读(5970) | 评论 (5)编辑 收藏

    Ruby的对象模型,包含在下面这张图中:


    首先要知道,Ruby中的类也是对象,类相比于其他对象特殊的地方在于能够产生对象,既然类是对象,那么它显然也有类,也就是所谓类的类,这个类的类在Ruby中就是类的metaclass,图中的(OtherClass),(OtherClass)就是类OtherClass的klass(C层次),(OtherClass)存储了类的方法(类方法)和类的实例变量,并且是唯一的且不可实例化。在Ruby层次上我们想操作(otherclass)应该类似:
  
class OtherClass
  
end
class<<OtherClass
  attr_accessor:name 
#name是OtherClass的实例变量
  def test
    p 
'hello'
  end
end
OtherClass.name
='1'
p OtherClass.name
OtherClass.test
    图中的instance是OtherClass的一个实例,那么显然instance的class是OtherClass,可是图中的(instance)又是什么呢?(instance)就是对象的singleton类,singleton类这个名称怪怪的,不过每个对象只能有一个singleton类的角度上说也可以理解。看看下面的例子:
class OtherClass
end
instance
=OtherClass.new
class<<instance
  
def test
    p 
"a.test"
  end
  attr_accessor:name
end
instance.test
instance.name
="dennis"
p instance.name

     instance通过OtherClass.new创建,但是此时(instance)还不存在,这与(OtherClass)情况不同,每个类一经创建就有一个metaclass,而对象就不一样,只有当你通过class<<instance 语法创建的时候,(instance)才被创建。注意test方法和name变量都将是instance对象特有的,类OtherClass并没有改变。观察下,发现(instance)继承于OtherClass,引出类的metaclass与对象的singleton类的又一个区别:类的metaclass继承自父类的metaclass,而对象的singleton类则是继承于对象的class。
    那么当我们调用instance.class的时候,怎么不返回(instance)?这是c ruby在底层做了处理,instance的class在c ruby层次是(instance),当查找的时候忽略了singleton类以及下面将要谈到的include模块的代理类,沿着继承链上查找:
86 VALUE
87 rb_obj_class(obj)
88 VALUE obj;
89 {
90 return rb_class_real(CLASS_OF(obj));
91 }

76 VALUE
77 rb_class_real(cl)
78 VALUE cl;
79 {
80 while (FL_TEST(cl, FL_SINGLETON) || TYPE(cl) == T_ICLASS) {
81 cl = RCLASS(cl)->super;
82 }
83 return cl;
84 }

(object.c)

核心代码就是:
while (FL_TEST(cl, FL_SINGLETON) || TYPE(cl) == T_ICLASS) {
  cl = RCLASS(cl)->super;
 }
    其中FL_TEST(cl,FL_SINGLETON)用于测试是否是singleton类,而TYPE(cl)==TL_ICLASS是否是包含模块的代理类,TL_ICLASS的I就是include的意思。
    图中类OtherClass继承Object,这个是显而易见的,不再多说。而Object、Class和Module这三个类是没办法通过API创建的,称为元类,他们的之间的关系如图所示,Object的class是Class,Module继承Object,而Class又继承Module,因此Class.kind_of? Object返回true,这个问题类似先有鸡,还是先有蛋的问题,是先有Object?还是先有Class?而c ruby的解决办法是不管谁先有,创建Object开始,接着创建Module和Class,然后分别创建它们的metaclass,从此整个Ruby的对象模型开始运转。

1243 rb_cObject = boot_defclass("Object", 0);
1244 rb_cModule = boot_defclass("Module", rb_cObject);
1245 rb_cClass = boot_defclass("Class", rb_cModule);
1246
1247 metaclass = rb_make_metaclass(rb_cObject, rb_cClass);
1248 metaclass = rb_make_metaclass(rb_cModule, metaclass);
1249 metaclass = rb_make_metaclass(rb_cClass, metaclass);

(object.c)

那么当我们调用Class.class发生了什么?Class的klass其实指向的是(Class),可根据上面的代码,我们知道会忽略这个(Class),继续往上找就是(Module),同理找到(Object),而(Object)继承自Class,显然Class的类仍然是Class,Class的类的类也是Class,多么有趣。同理,Object.class和Module.class都将是Class类。

    再来看看include模块时发生的故事。include模块的过程如下图所示:

include模块,本质上是在对象或者类的klass和super之间插入了一个代理类iclass,这个代理类的方法表(m_table)和变量表(iv_table)分别指向了被包含的模块的方法表和变量表(通过指针,因此当包含的Module变化的时候,对象或者类也能相应变化),那么在查找类或者对象的class的时候,上面已经说明将忽略这些代理类。



posted @ 2007-09-29 09:43 dennis 阅读(1464) | 评论 (0)编辑 收藏

仅列出标题
共56页: First 上一页 32 33 34 35 36 37 38 39 40 下一页 Last