Changeset 12076

Timestamp:

05/20/08 23:43:43 (5 years ago)

Author:

ayu

Message:

• splitted file(&class)
  

Location:

lang/cplusplus/misc/clustercpp

Files:

• include/ward.h (modified) (1 diff)
• include/wardupdator.h (added)
• src/Makefile (modified) (1 diff)
• src/ward.cpp (modified) (6 diffs)
• src/wardupdator.cpp (added)

lang/cplusplus/misc/clustercpp/include/ward.h

@@ -36 +36 @@
   class Ward{
     HISTORIES* hist;
-    MATRIX* mat;
-    CACHES* caches;
 
   public:
     Ward();
     ~Ward();
-    HISTORIES* cluster(MATRIX* mat, INDEX size);
-    MATRIX* create_matrix(VECTOR* vectors, INDEX vectorNum);
-  private:
-    void update_matrix(INDEX p, INDEX q, INDEX nextnodenum, std::set<INDEX>& kieta, MATRIXROW* objp, std::vector<INDEX>& sizes);
-    void initcache();
-    inline VALUE elm(INDEX i, INDEX j){ 
-      return (*((*mat)[i]))[j];}
-    inline void savecache(INDEX i, VALUE d, INDEX i1){
-      CacheP p = CacheP(new Cache);
-      p->distance=d;
-      p->index=i1;
-      (*caches)[i] = p;
-    }
-    inline CacheP getcache(INDEX i){return (*caches)[i];}
-    inline bool hascache(INDEX p){return caches->find(p) != caches->end();}
-    inline bool hasrow(INDEX p){return mat->find(p) != mat->end();}
-    inline bool hascol(INDEX p, INDEX q){return (*mat)[p]->find(q) != (*mat)[p]->end();}
+    HISTORIES* cluster(VECTOR* vectors, INDEX vectorNum);
   };
 }

lang/cplusplus/misc/clustercpp/src/Makefile

@@ -1 @@
-ward: ward.cpp
-        g++ -O3 -ffast-math -funroll-loops -Wall -fno-common -march=nocona -o ward -I../include ward.cpp
+CXXFLAGS=-O3 -ffast-math -funroll-loops -Wall -fno-common -march=nocona
+ward: ward.o wardupdator.o
+        g++ $(CXXFLAGS) -o ward -I../include ward.o wardupdator.o
+
+wardupdator.o: wardupdator.cpp
+        g++ $(CXXFLAGS) -c -I../include wardupdator.cpp
+
+ward.o: ward.cpp
+        g++ $(CXXFLAGS) -c -I../include ward.cpp
+
+
+
+clean:
+        rm *.o
+        rm ward

lang/cplusplus/misc/clustercpp/src/ward.cpp

@@ -9 +9 @@
 
 #include "ward.h"
+#include "wardupdator.h"
 
 namespace clustercpp{
-  void printmat(MATRIX* mat){
-    for(MATRIX::iterator i=mat->begin(); i != mat->end(); i++){
-      for(MATRIXROW::iterator j=i->second->begin(); j != i->second->end(); j++){
-        std::cout << "(" << i->first << "," << j->first << ")=" << j->second << ",";
-      }
-      std::cout << std::endl;
-    }
-    std::cout << "--------------------" << std::endl;
-  }
-
-  Ward::Ward(){
+  Ward::Ward() {
     hist = new HISTORIES;
-    caches = new CACHES;
-    mat = new MATRIX;
   }
 
   Ward::~Ward(){
-    delete mat;
-    delete caches;
     delete hist;
   }
-
-  //行列作成
-  MATRIX* Ward::create_matrix(VECTOR* vectors, INDEX vectorNum){
-    for(INDEX i=1; i<vectorNum; i++){
-      VECTOR& v = vectors[i];
-      MATRIXROWP p = MATRIXROWP(new MATRIXROW);
-      mat->insert(MATRIX::value_type(i, p));
-      for(INDEX j=0; j<i; j++){
-        VECTOR& u = vectors[j]; 
-        //ベクトル間のユークリッド距離を計算
-        double pp = 0.0;
-        INDEX k = 0;
-        VECTOR::iterator e = u.end();
-        for(VECTOR::iterator it=u.begin();it!=e;it++){
-          VALUE x = v[k]-(*it);
-          pp += x*x;
-          k++;
-        }
-        (*p)[j] = std::sqrt(pp);
-      }
-    }
-    return mat;
-  }
-
-  struct compmatrow : public std::binary_function<MATRIXROWPAIR, MATRIXROWPAIR, bool> {
-    bool operator ()(const MATRIXROWPAIR &x, const MATRIXROWPAIR &y) const { return x.second < y.second; }
-  };
-  struct compcache : public std::binary_function<CACHEPAIR, CACHEPAIR, bool> {
-    bool operator ()(const CACHEPAIR &x, const CACHEPAIR &y) const { return (x.second)->distance < (y.second)->distance; }
-  };
   
-  void Ward::initcache(){
-    for(MATRIX::iterator i=mat->begin();i!=mat->end();i++){
-      MATRIXROW::iterator it = std::min_element(i->second->begin(), i->second->end(), compmatrow());
-      if(it != i->second->end()){
-        savecache(i->first, it->second, it->first);
-      }
-    }
-  }
-
   void printcache(CACHES* caches){
     std::cout << "Caches ";
@@ -80 +28 @@
   }
 
-  HISTORIES* Ward::cluster(MATRIX* mat, INDEX size){
-    initcache();
-    //printmat(mat);
-    std::vector<INDEX> sizes(size, 1);
+  HISTORIES* Ward::cluster(VECTOR* vectors, INDEX vectorNum){
+
+    WardUpdator updator;
+    History h = updator.create_matrix(vectors, vectorNum);
+    INDEX size = updator.size();
+
     hist->clear();
-    std::set<INDEX> kieta;
     INDEX nextnodenum;
     nextnodenum=size;
+
     while(hist->size()<size-1){
       //最小キャッシュを選択
       //printcache(caches);
-      if(caches->size()==0) break;
-      CACHES::iterator i=std::min_element(caches->begin(), caches->end(), compcache());
 
-      VALUE distance = (i->second)->distance;
-      INDEX p = (i->second)->index;
-      INDEX q = i->first;
+      INDEX p = h.index1;
+      INDEX q = h.index2;
       if(p>q){
         INDEX tmp = p;
@@ -102 +49 @@
         q=tmp;
       }
-      ///std::cout << "joining " << distance << " ,q " << q << " ,p " << p << " => " << nextnodenum << std::endl;
-
-      //消えたもの集合を更新
-      kieta.insert(p);
-      kieta.insert(q);
-      //キャッシュから、今回消えるものをあらかじめ排除
-      caches->erase(p);
-      caches->erase(q);
-      //std::cout << "erased" << std::endl;
-
-      MATRIXROW* objp = new MATRIXROW;
-      if(objp==0) std::cout << "POINTER ERROR" << std::endl;
-      mat->insert(MATRIX::value_type(nextnodenum, MATRIXROWP(objp)));      
-      update_matrix(p, q, nextnodenum, kieta, objp, sizes);
-
-      //std::cout << "len(cache) " << caches->size() << std::endl;
-      mat->erase(p);
-      mat->erase(q);
-      sizes.push_back(sizes[q]+sizes[p]);
-      History h;
-      h.distance = distance;
+      //結果の格納
       h.index1 = q;
       h.index2 = p;
       hist->push_back(h);
-      //printmat(mat);
+
+      //行列の更新
+      h = updator.update_matrix(p, q, nextnodenum);
+
       nextnodenum++;
     }
@@ -132 +62 @@
   }
 
-  void Ward::update_matrix(INDEX p, INDEX q, INDEX nextnodenum, std::set<INDEX>& kieta, MATRIXROW* objp, std::vector<INDEX>& sizes){
-    VALUE mqp = elm(q,p);
-    INDEX sp = sizes[p];
-    INDEX sq = sizes[q];
-    INDEX sqp = sp+sq;
-    double mindist=-1.0;
-    INDEX minj =0;
-    std::set<INDEX>::iterator kietaend = kieta.end();
-    for(INDEX j=0;j<nextnodenum; j++){
-
-      if(kieta.find(j) != kietaend){
-        continue; //すでに消えてるなら何もしない
-      }
-      double tmpdist;
-      if(j < p){
-        tmpdist = (*objp)[j] = ((sp+sizes[j])*elm(p,j)+(sq+sizes[j])*elm(q,j)-sizes[j]*mqp)/(sqp+sizes[j]);
-      }else if(p<j && j<q){
-        tmpdist = (*objp)[j] = ((sp+sizes[j])*elm(j,p)+(sq+sizes[j])*elm(q,j)-sizes[j]*mqp)/(sqp+sizes[j]);
-        (*mat)[j]->erase(p);  //今後使わなくなる成分の消去
-      }else{
-        tmpdist = (*objp)[j] =((sp+sizes[j])*elm(j,p)+(sq+sizes[j])*elm(j,q)-sizes[j]*mqp)/(sqp+sizes[j]);        
-        (*mat)[j]->erase(p); //今後使わなくなる成分の消去
-        (*mat)[j]->erase(q); //今後使わなくなる成分の消去
-      }         
-      if(tmpdist<mindist or mindist<0.0){
-        mindist=tmpdist;
-        minj=j;
-      }
-      if(hasrow(j)){ //Q. この判定必要？ A. 必要。まだ合体させられてないのに、matの行自体は消えていることがあるよ。
-        if((*mat)[j]->size()==0){           
-          caches->erase(j);
-          mat->erase(j);
-          //一見ここでkieta.insert(j)したくなるが、そうしてはいけない！
-          //kietaにinsertするのは、真にその点が消えた時=他の点と合体させられた時のみである。
-          //そうでないのにここでinsertしてしまうと、まだ消滅していないのに、未来永劫計算対象からはずされてしまうのだっ！！
-        }else{
-          CacheP c = getcache(j);
-          if(c->index==p || c->index==q){
-            MATRIXROW::iterator it = std::min_element((*mat)[j]->begin(), (*mat)[j]->end(), compmatrow());
-            savecache(j, it->second, it->first);
-          }
-        }
-      } 
-    }
-    //新ノードからの距離をキャッシュに記録
-    if(mindist>=0.0){
-      savecache(nextnodenum, mindist, minj);
-    }
-  }
 }
 
@@ -200 +81 @@
 
   while(line!=""){
-    //std::cout << line << std::endl;
     std::vector<std::string> data;
     split(line, "\t", data);
@@ -218 +98 @@
   std::clock_t t1,t2,t3;
   t1 = std::clock();
-  MATRIX* mat = ward.create_matrix(&(*vectors)[0], vecsize);
   t2 = std::clock();
   //clustercpp::printmat(mat);
-  HISTORIES* hist = ward.cluster(mat, vecsize);
+  HISTORIES* hist = ward.cluster(&(*vectors)[0], vecsize);
   t3 = std::clock();
   for(HISTORIES::iterator it=hist->begin(); it!=hist->end(); it++){
     idlabel.push_back("("+idlabel[it->index1]+"+"+idlabel[it->index2]+")");
-    std::cout << "dist "<< it->distance <<std::endl;//<< "  " << idlabel[idlabel.size()-1] << std::endl;
+    std::cout << "dist "<< it->index1 << "+" << it->index2 << " / " << it->distance << std::endl; // ")  " << idlabel[idlabel.size()-1] << std::endl;
   }
   double T1 = static_cast<double>(t2-t1) / CLOCKS_PER_SEC;