replacecomputing.java

一宗队列算法

//Source file: E:/工作和学习/工作/硕士论文工作/程序/数据库缓存管理/20040304/src/MemCachePak/ReplaceComputing.java

/* tangtang */

package MemCachePak;


public class ReplaceComputing implements ReplaceComInterface
{
   public MemCacheInterface theCache;

   public ReplaceComputing()
   {
   }

   /**
   @roseuid 4177275602EE
   */
   public boolean InsertNewObj(String[] RefArray, int ObjSize, int TimeCost)
   {
      WebObj obj = new WebObj();
      obj.SetSourceFileName(RefArray[0]);
      obj.SetCachedFileName(RefArray[1]);
      obj.SetObjRef(RefArray);
      obj.SetCost(TimeCost);
      obj.SetFileSize(ObjSize);
      obj.SetEnterTime();
      theCache.InsertNewObj(obj);
      theCache.InsertNewVector(TimeCost,RefArray[0],RefArray[1],RefArray[0]);
     return true;
   }

   /**
   @roseuid 4181A7CE0165
   */
   public boolean ReplaceCache()
   {
     //首先判断缓存大小是否超过了门限
     //如果超过了门限，则执行替换算法，返回true
     if(theCache.GetCacheSize()>=Configuration.MAX_SIZE)
     {
       System.out.println("缓存进行了一次替换ACR");
       //theCache.Print();
       WebObj headObj,NowObj;
       headObj = theCache.GetTheFirstObj();
       //NowObj = theCache.GetTheFirstObj();
       long TimeNow=System.currentTimeMillis();
       while(headObj!=null)
       {
         NowObj = headObj;
         //首先利用原始web对象转换图，建立最小耗费连通子图G'
         ObjChart theChart = theCache.SearchChartByName(headObj.GetSourceFileName());
         //G'的权重和
         int Wall = MTCC(theChart);
         //System.out.println(NowObj.GetCachedFileName());
         //System.out.println(Wall);
         //G"的权重和
         int WOj;
         //版本间缓存价值
         float PFMOj;
         //独立缓存价值
         float PFSOj;
         //生成该对象的向量权值
         int wj;
         //然后对每一个版本对象计算更新缓存价值
         while(NowObj!=null)
         {
           //建立没有这个版本对象时的最小耗费子图G"
           //计算这个对象的缓存价值
            WOjandPFS theWOjandPFS = MTCC(theChart,NowObj);
            WOj = theWOjandPFS.WOj;
            wj = theWOjandPFS.wj;
            //System.out.println(NowObj.GetCachedFileName());
            //System.out.print("WOj:"+WOj+" ");
            //System.out.println("wj:"+wj);
            //综合缓存价值
            float GPF = 0;
            //该对象版本的直接使用概率，利用滑动平均方法近似
            float ri = 0;
            if(NowObj.GetUsedCount()>=Configuration.K)
            {
              //long TimeNow=System.currentTimeMillis();
              //计算使用概率
              ri=  (float)Configuration.K/(TimeNow -
                                    NowObj.GetLastUsedTime(Configuration.K));
            }
            else
            {
              //long TimeNow=System.currentTimeMillis();
              //System.out.println("NowObj.GetUsedCount() "+NowObj.GetUsedCount());
              //System.out.println(TimeNow);
              //System.out.println(NowObj.GetLastUsedTime(NowObj.GetUsedCount()));
              //计算使用概率
              ri=  (float)NowObj.GetUsedCount()/(TimeNow -
                               NowObj.GetLastUsedTime(NowObj.GetUsedCount())+1);
              //System.out.println(ri);
            }
            //该对象版本的版本间使用概率，利用滑动平均方法近似
            float rim = 0;
            if(NowObj.GetMediaUsedCount()>=Configuration.K)
            {
              //long TimeNow=System.currentTimeMillis();
              //计算使用概率
              rim =  (float)Configuration.K/(TimeNow -
                             NowObj.GetLastMediaUsedTime(Configuration.K));
            }
            else if(NowObj.GetMediaUsedCount()!=0)
                  {
                    //long TimeNow=System.currentTimeMillis();
                    //计算使用概率
                    rim =  (float)NowObj.GetMediaUsedCount()/(TimeNow -
                    NowObj.GetLastMediaUsedTime(NowObj.GetMediaUsedCount()));
                  }
                  else
                  {
                    //计算使用概率
                    rim = 0;
                  }
            //计算版本间缓存价值
            PFMOj = rim*(WOj - (Wall-wj));
            //计算独立缓存价值
            PFSOj = ri*wj;
            //计算综合缓存价值
            GPF = 10000*(float)(PFMOj + PFSOj)/(float)NowObj.GetFileSize();
            //System.out.print(ri+" ");
            //System.out.print(rim+" ");
            //System.out.println(GPF+" ");
            NowObj.SetGPF(GPF);
            //System.out.println(NowObj.GetGPF());
           //转到下一个版本对象
            NowObj = NowObj.NextObjEdition;
         }
         //转到下一个版本对象群
         headObj = headObj.NextObj;
       }
       //theCache.Print();
       theCache.DeleteObj(theCache.GetMinGPFObj());
       String foldername="D:\\Tomcat40\\webapps\\adpro\\tempout\\"+theCache.GetMinGPFObj().GetCachedFileName().substring(8,33);
       System.out.println("删除文件夹名称:"+foldername);
       FileOperation.deletefolder(foldername);
       //同步删除文件
        /*File myfile = new File("e:\\cachefile");
        for(int c1=0;c1<delnum;c1++)
        {
          File file1=new File(myfile,delarray[c1]);
          System.out.println(file1.exists());
          //删除文件
          file1.delete();
          System.out.println(file1.exists());
        }*/
       //theCache.Print();
       return true;
     }
     else
     {
       //如果没有超过门限，则不执行替换算法，返回false
       return false;
     }
   }

   /**
   @roseuid 41941B450242
   */
   public ReplaceComputing(MemCacheInterface cache)
   {
     theCache = cache;
   }

   /**
   @roseuid 41982002037A
   */
   public boolean InsertNewObj(String[] RefArray, int ObjSize, int TimeCost,
                               String BeginPoint, boolean SourceOrMedia)
   {
     WebObj obj = new WebObj();
     obj.SetSourceFileName(RefArray[0]);
     obj.SetCachedFileName(RefArray[1]);
     obj.SetObjRef(RefArray);
     obj.SetCost(TimeCost);
     obj.SetFileSize(ObjSize);
     obj.SetEnterTime();
     theCache.InsertNewObj(obj);
     if(SourceOrMedia)
     {
       theCache.InsertNewVector(TimeCost,RefArray[0],RefArray[1],RefArray[0]);
     }
     else
     {
       WebObj MediaObj = theCache.GetCachedObj(RefArray[0],BeginPoint);
       MediaObj.AddMediaUsedCount();
       MediaObj.SetLastMediaUsedTime();
       theCache.InsertNewVector(TimeCost,BeginPoint,RefArray[1],RefArray[0]);
     }
     return true;
   }

   /**
   @roseuid 419B0E8E035B
   */
   public int MTCC(ObjChart theChart)
   {
     int w = 0;
     //找到图中第一个顶点
     ChartFirstVex NowVex = theChart.theFirstVex;
     while(NowVex!=null)
     {
       //初始化操作
       int min_wi;
       ChartEdge NowEdge = NowVex.firstout;
       if(NowEdge!=null)
       {
         min_wi = NowEdge.GetData();
       }
       else
         min_wi = 0;
       //对每个顶点，找出其最小权值的射入向量
       while(NowEdge!=null)
       {
         int wi = NowEdge.GetData();
         if(wi<min_wi)
         {
           min_wi = wi;
         }
         NowEdge = NowEdge.Rlink2;
       }
       w = w+min_wi;
       NowVex = NowVex.nextvex;
     }
     return w;
   }

   /**
   @roseuid 419B13BF03B9
   */
   public WOjandPFS MTCC(ObjChart theChart, WebObj theObj)
   {
     WOjandPFS theWOjandPFS = new WOjandPFS();
     int WOj = 0;
     int wj = 0;
     //用于算法中图不连通时的改进
     String objname = "";
     //找到图中第一个顶点
     ChartFirstVex NowVex = theChart.theFirstVex;
     while(NowVex!=null)
     {
       if(NowVex.GetData()!=theObj.GetCachedFileName())
       {
         //初始化操作
         int min_wi;
         ChartEdge NowEdge = NowVex.firstout;
         if((NowEdge!=null)&&(!((NowEdge.Gethead()).equals(theObj.GetCachedFileName()))))
         {
           min_wi = NowEdge.GetData();
         }
         else
           min_wi = 0;
         //对每个顶点，找出其最小权值的射入向量
         int mediacost = 0;
         while(NowEdge!=null)
         {
           if(!(NowEdge.Gethead()).equals(theObj.GetCachedFileName()))
           {
             int wi = NowEdge.GetData();
             if(wi<min_wi)
             {
               min_wi = wi;
             }
           }
           else
           {
             mediacost = NowEdge.GetData();
           }
           NowEdge = NowEdge.Rlink2;
         }
         //如果将此对象从图中去掉后，有的顶点不存在射入的向量时（除了头顶点），
                                                     //我们采取一些办法解决
         if((min_wi==0)&&(NowVex.GetData()!=theObj.GetSourceFileName()))
         {
           /*min_wi = (int)(mediacost*((float)Configuration.x/100))
                                             +mediacost;
           System.out.println("***********************************");
           System.out.println(min_wi);
           System.out.println(mediacost);
           System.out.println(((float)Configuration.x/100));
           System.out.println(min_wi);
           System.out.println("***********************************");*/
           int s2 = theObj.GetFileSize();
           int C2 = mediacost;
           int C3 = 0;
           int s3 = 0;
           WebObj headObj = theCache.GetCachedObj(theObj.GetSourceFileName(),objname);
           if(headObj!=null)
           {
             s3 = headObj.GetFileSize();
           }
           else
           {
             s3 = 2*s2;
           }
           C3 = (int)((float)C2*((float)s3/s2));
           /*System.out.println("***********************************");
           System.out.println(s2);
           System.out.println(C2);
           System.out.println(s3);
           System.out.println(C3);
           System.out.println("***********************************");*/
           min_wi = C3;
         }

         WOj = WOj+min_wi;
      }
       else/*计算wj，wj是以j为终点的向量中权重最小的那个向量，
                               也是最小耗费连通子图G’中指向j的唯一的那个向量的权重。*/
       {
         //初始化操作
         int min_wi;
         ChartEdge NowEdge = NowVex.firstout;
         if(NowEdge!=null)
         {
           min_wi = NowEdge.GetData();
           objname = NowEdge.Gethead();
         }
         else
           min_wi = 0;
         //对每个顶点，找出其最小权值的射入向量
         while(NowEdge!=null)
         {
             int wi = NowEdge.GetData();
             if(wi<min_wi)
             {
               min_wi = wi;
               objname = NowEdge.Gethead();
             }
           NowEdge = NowEdge.Rlink2;
         }
         wj = min_wi;
       }
       NowVex = NowVex.nextvex;
     }
     theWOjandPFS.wj = wj;
     theWOjandPFS.WOj = WOj;
     return theWOjandPFS;
   }
}