莊周夢蝶

          生活、程序、未來
             :: 首頁 ::  ::  :: 聚合  :: 管理

          習題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 閱讀(456) | 評論 (0)編輯 收藏

              最近被換工作的事情搞的心煩意亂,幾本正在讀的技術書進度都慢了下來。上周末,老婆回家參加同學婚禮,一個人去書店瞎逛,隨手拿起了溫伯格的《理解專業程序員》,讀了幾個短篇就被吸引住了。見天色已晚,遂買之回家,細細品讀。這本書是由一篇篇短小精悍的文章組成,按一定的主題組織在一起,你想知道如何稱為一名程序員嗎?什么才算是專業的程序員?程序員如何提高績效?如何更有效地進行思考?大師用幾十年的從業經驗為你慢慢道來。
              專業?到底什么樣的人才稱得上專業的程序員?溫伯格說,計算機編程領域具備了不起的技藝或經驗的那些人才能算得上是專業程序員。“技藝”這個詞用的很恰當。那么,要多長的時間才能稱為專業的人呢?大師的意見是怎么也得15年,15年以內的只能稱為業余程序員或者“不那么專業的程序員”。呵呵,我也曾在外行人面前冒充過專業程序員,想想都汗顏,當得上“專業”兩個字不僅僅是15年的從業經歷,更多是這15年中你做了什么,創造了什么,學到了什么。經驗與技藝缺一不可。書中充滿了真知灼見,有些故事讓你覺的臉紅,因為那些愚蠢的事情正是你不斷重復的;有些經驗讓你覺的很熟悉,是啊,我們就是這樣干的!而有些見解其實是一些勵志書籍不斷重復的老套教條,盡管老套,但是沒有經歷的人終究是難以理解的,我也不例外。這本書值的在以后多年的日子里重讀幾遍。

          posted @ 2007-10-17 16:38 dennis 閱讀(539) | 評論 (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 閱讀(684) | 評論 (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 閱讀(707) | 評論 (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 閱讀(1088) | 評論 (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 閱讀(561) | 評論 (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 閱讀(893) | 評論 (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 閱讀(389) | 評論 (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 閱讀(6001) | 評論 (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 閱讀(1477) | 評論 (0)編輯 收藏

          僅列出標題
          共56頁: First 上一頁 32 33 34 35 36 37 38 39 40 下一頁 Last 
          主站蜘蛛池模板: 佳木斯市| 湖北省| 灵石县| 应用必备| 团风县| 玉环县| 襄樊市| 阿拉尔市| 遂溪县| 昌黎县| 建昌县| 灌阳县| 大连市| 大田县| 舟山市| 登封市| 佛冈县| 中方县| 兴仁县| 泸州市| 阳朔县| 永平县| 湖南省| 景德镇市| 明光市| 阿尔山市| 富平县| 慈利县| 汽车| 重庆市| 绍兴市| 西吉县| 临桂县| 山东| 菏泽市| 横山县| 肇东市| 泸定县| 嘉峪关市| 彰武县| 如皋市|