extendf6.c

关联规则中的频繁项集生成算法genmax

                 }
                 seconds(t40);
                 if (has_sup(tail_list, Y, I->itemsetsize())) delete tail_list;
                 else {

                       cptr = I -> itemset() ->head();
                       for (; cptr; cptr = cptr ->getnext())
                               tail_list -> add(cptr -> getdata());
                       
                       Y -> addatback(tail_list); 

		 } 
                 seconds(t50);
                 super_set_time += t50 - t40;
                 check_status = TRUE;
         }
         else {
         
           s = Xtem -> size();
           temptr = Xtem ->head();
           for (; temptr; temptr = temptr -> getnext()){

               if (Y -> size() > 0 && check_status == TRUE){

                     seconds(t40);
                     G = new Array(Xtem->size() + tail_list->size() + 1);
                     ptr = temptr;
                     while (ptr){

                         G ->add(ptr->getdata()->itemset()->head()->getdata());
                         ptr = ptr ->getnext();
	             }
                     for (int g=0; g < tail_list->size(); g++) 
                                           G -> add((*tail_list)[g]);

                     if (has_sup(G, Y, I->itemsetsize())){

                                          delete G;        
                                          break;

	             }
                     delete G;  
                     seconds(t50);
                     super_set_time += t50 - t40;
               }
               seconds(h1);
               j = temptr -> getdata()->itemset()-> head() -> getdata();
               cptr = I -> itemset() ->head();
               for (; cptr; cptr = cptr ->getnext())
                         temptr->getdata() -> add_item(cptr -> getdata());
         
               seconds(h2);
               copy_time += (h2 - h1);
               
               NewY = new List<Array *>;
               seconds(t40); 
               find_sets(NewY, Y, j);
               seconds(t50);
               find_time += (t50-t40);
               size_old = NewY->size();
               s = s-1;
               //NewX = new List<Itemset *>; 
               //xxptr = temptr -> getnext();
               //while(xxptr){
                 //     NewX -> addatback(xxptr  -> getdata());
                  //    xxptr = xxptr -> getnext(); 
               //}
               check_status = FALSE;

               //Extend (temptr->getdata(), NewX, NewY, tail_list, iter+1);
     Extend (temptr->getdata(), temptr->getnext(), NewY, tail_list, iter+1, s);
               ttptr = NewY->head();
               f = 1;
               while (ttptr){
                    if (f > size_old){
                                 Y -> addatback(ttptr -> getdata());
	            }
                    f +=1;
                    ttptr = ttptr -> getnext();
               }
               delete NewY; 
               //delete NewX;
           }
           delete tail_list;
         }
         if (Xtem->size() == 0) delete Xtem; 
         else clear_list_itemset(Xtem);
    
}



void read_files(List<int> *F1)
{

   int i,j,a,b;
   double te,ts;
   seconds(ts);
   
   maxitemsup = make_l1_pass(F1);
   
   seconds(te);
   
   iterstat *is = new iterstat(DBASE_MAXITEM, 0, te-ts);
   stats.add(is);
   
   ts = te;
   
   cout << "maxitemsup: " << maxitemsup <<endl;
   item1 = new Itemset(maxitemsup);
   item2 = new Itemset(maxitemsup);
 
   int l2cnt = make_l2_pass(ext_l2_pass, it2f);
   seconds(te);
   L2TIME = te-ts;
   cout << "\nL2TIME = " << te-ts << endl;
   
   is = new iterstat(DBASE_MAXITEM*(DBASE_MAXITEM-1)/2,0,te-ts);
   stats.add(is);
   
   ts = te;
 
   eqgraph2 = new List<int> *[DBASE_MAXITEM];
   bzero((char *)eqgraph2, DBASE_MAXITEM*sizeof(List<int> *));  

   for (i=0; i < DBASE_MAXITEM; i++){
      eqgraph2[i]= new List<int>;
   }

   cout << " MINSUPPORT is : " <<  MINSUPPORT;

   int idx;   
   int it1, it2;   
   int lcnt;   
   GrNode *grn;   
   for (i=0; i < Graph::numF1; i++){
      //cout << "\nITEM " << i;
      grn = (*F2Graph)[i];      
      it1 = grn->item();
      lcnt = grn->size();       
      if (lcnt > 0){
         for (j=0; j < grn->size(); j++){
            it2 = (*F2Graph)[(*grn)[j]->adj()]->item();            
            eqgraph2[it1]->addatback(it2);
            eqgraph2[it2]->addatback(it1);
         }
      }
   }
   //delete offsets;

   // To fill in the list F1 by comblnth(i) values for each i in F1 
   // and delete the items which have  
   // comblist values equal to 0, these items are maximal itemsets. 
   // Also compute the maximum and minimum levels required for the sorting 
   // routine.

   Listnode<int> *ptr = F1 ->head();
   Listnode<int> *temptr = NULL;
   min1 = F1 ->size();
   max1 = 0;
   while (ptr){
       a = ptr -> getdata();
       b = eqgraph2[a]->size();
       if (b > 0){
                  ptr -> set_comblnth(b);
                  if (b < min1)   min1 = b;
                  if (b > max1)   max1 = b;
                  temptr = ptr;
       }
       else {
             if (!temptr)  F1 -> set_head(ptr->getnext());
             else  temptr ->set_next(ptr -> getnext());
       }
       ptr = ptr ->getnext();
   }
   seconds(te);

   cout << "\nConstruction time for the combine lists = " << te-ts << endl;

    //cout << "The combine Lists before sorting are: " << endl;
   //for (i=0; i < DBASE_MAXITEM; i++){   
     //  if (eqgraph2[i]->size()>0) cout <<"Combine list of item ("<<i<<") is "
       //                     <<*eqgraph2[i]<< endl;
   //} 
}

void Max_itset_algo()
{
    double t1,t2;
    int i, j, f, m, zsize_old, ysize_old, s;
    Listnode <Array *> *ttptr;
    Array *H, *tail_list, *cp;
    Listnode<int> *temptr, *temptr1;
    Itemset *I, *it1;
    List<Itemset *> *X1, *X2;
   List <int> *cp2;
    Listnode <Itemset *> *xptr, *ptr1, *xxptr;
    List <Array *> *M, *Z, *Y;

    M = new List<Array *>;
    temptr = F1 -> head();
    for (; temptr; temptr = temptr -> getnext()){

       i = temptr -> getdata();

       Memman::read_from_disk(item1,i); 
       X1 = new List<Itemset *>; 
             
       cp = new Array ( eqgraph2[i] -> size()+1);
       cp -> add(i);
       temptr1 = eqgraph2[i] -> head();
       for (;temptr1;temptr1=temptr1->getnext()) cp->add(temptr1->getdata());
       if (!has_sup(cp, M, 0)){

             Z= new List<Array *>;
             seconds(t40);
             find_sets(Z, M, i);
             seconds(t50);
             find_time += (t50-t40);
             zsize_old = Z->size();             
              //cout << "high before reading" << endl;
             seconds(t5);
             cp2 = new List<int>;
             temptr1 = eqgraph2[i] -> head();
             for (; temptr1; temptr1 = temptr1 -> getnext()){
                     m = temptr1 -> getdata();
                     Memman::read_from_disk(item2, m);
                     if (use_diff_f2){
                        it1 = new Itemset(item1 -> support());
                        Diff1(it1, item1, item2);
                        if (it1->tidsize()== 0){
                                  cp2 -> addatback(m);
                                   delete it1; 
                        }
                        else{  X1-> sorted_ascend(it1, it1->support());
                              it1 -> add_item(m);
                        }
                     }                     
                     else if (diff_input){
                        Diff2(it1, item2, item1);
                        it1 = new Itemset(
                                          min(item1->support()-MINSUPPORT+1,
                                              item2 -> tidsize()));
                       //if (it1->tidsize()== 0){
                         //         cp2 -> addatback(m);
                          //         delete it1; 
                        //}
                     }                     
                     else{
                        it1 = new Itemset(min(item1->support(),
                                              item2->support()));    
                        get_intersect(it1, item1, item2);
                        if (it1->tidsize() == item1->tidsize()){
                                   cp2 -> addatback(m);
                                   delete it1; 
                        }
                        else{  X1-> sorted_ascend(it1, it1->tidsize());
                              it1 -> add_item(m);
                        }
                     }                     
                     //stats.incrcand(item1->itemsetsize());
                   //cout << it1 << endl;
                   //if (it1){ 
                     // //cout << it1 << endl;
                     //it1 -> add_item(m);
                      //cout << it1 << endl;
                     ////cout << "TT " << i << " "<< m << " " << *it1 << endl;
                     //if (use_diff_f2 || diff_input) 
                       // X1-> sorted_ascend(it1, it1->support());
                     //else X1-> sorted_ascend(it1, it1->tidsize());
                     ////X1-> sorted_descend(it1, it1->tidsize());
                    ////cout <<  it1->tidsize() << " ";
                   //}
                   //cout << it1 << endl;
                     
             }
             //cout << "high after reading" << endl;
             seconds(t6);
             read_dbase_time += t6 - t5;

             //Z= new List<Array *>;
             //seconds(t40);
             //find_sets(Z, M, i);
             //seconds(t50);
             //find_time += (t50-t40);
             //zsize_old = Z->size();
       tail_list = new Array (cp2 -> size()+1);
       temptr1 =cp2 -> head();
       for (;temptr1;temptr1=temptr1->getnext()) tail_list->add(temptr1->getdata());
       delete cp2;
         if (X1 ->size()< 2){ 

                  if (X1 ->size()== 1){   
                          tail_list ->add(X1 ->head()->getdata()->itemset()->head()->getdata());
                 }
                 //seconds(t40);
                 if (has_sup(tail_list, Z, 1)) delete tail_list;
                 else {
                          tail_list -> add(i);
                       
                          Z -> addatback(tail_list); 

		 } 
                 //seconds(t50);
                 //super_set_time += t50 - t40;
                 //check_status = TRUE;
         }
         else {
             s = X1 -> size();
             xptr = X1 -> head();
             for (; xptr; xptr = xptr -> getnext()){
              
                 if ( Z -> size() > 0){

                       seconds(t40);
                       H = new Array(X1->size());
                       ptr1 = xptr;
                       while (ptr1){

                            H ->add(ptr1->getdata()->itemset()->head()->getdata());
                            ptr1 = ptr1 ->getnext();

	               }
                       if (has_sup(H, Z, 1)){ 
                              delete H;        
                              break;               
	               }
                       delete H; 
                       seconds(t50);
                       super_set_time += t50 - t40;

	         }

                 seconds(a1);
                 j = xptr -> getdata()->itemset()->head()->getdata();
                 xptr -> getdata() -> add_item(i);
                 seconds(a2);
                 copy_time += (a2-a1);
                  //cout << " high" << endl;
                  Y = new List<Array *>;
                  //cout << " high befor extend" << endl;
                  seconds(t40); 
                  find_sets(Y, Z, j);
                  seconds(t50);
                  find_time += (t50-t40);
                  ysize_old = Y->size();

                  //tail_list = new Array(1);
                  s = s-1;
                  //X2 = new List<Itemset *>; 
                  //xxptr = xptr -> getnext();
                  //while(xxptr){
                    //  X2 -> addatback(xxptr  -> getdata());
                     // xxptr = xxptr -> getnext();
	          //}

                  check_status = FALSE;
                  seconds(t1); 
                  //Extend (xptr->getdata(), X2, Y, tail_list, 2);
                 Extend (xptr->getdata(), xptr->getnext(), Y, tail_list, 2, s);
                  seconds(t2); 
                  extend_time += (t2-t1);

                  //cout << "\nY after extend contains:" << endl;
                  ttptr = Y->head();
                  f = 1;
                  while (ttptr){
                        //cout <<*(ttptr->getdata()) << endl;
                        if (f >ysize_old){
                                 Z -> addatback(ttptr -> getdata());
			}
                        f +=1;
                        ttptr = ttptr -> getnext();
	          }
                  delete Y; 
                  //delete X2;
                  //delete tail_list;
	     }
             delete tail_list;
         }
             Listnode <Array *> *zptr = Z -> head();
             f = 1;
             while (zptr){

                     if (f > zsize_old) M -> addatback(zptr -> getdata());
                     f += 1;
                     zptr = zptr -> getnext();
             }
             delete Z;
             if (X1->size() == 0) delete X1; 
             else clear_list_itemset(X1);
       }
    }
 
    ttptr = M->head();
    if (print_output) cout << "\nM contains:" << endl;
    while (ttptr){
       if (print_output) cout <<*(ttptr->getdata()) << endl;
       //Listnode <int> *mptr = ttptr->getdata()->head();
       //int mcnt=0;
       //while (mptr){
       //   mcnt++;
       //   mptr = mptr->getnext();
       //}
       int mcnt = ttptr->getdata()->size();       
       stats.incrlarge(mcnt-1);       
       ttptr = ttptr -> getnext();       
    }
    
    cout <<";Number of maximal frequent itemsets : "<< M->size()<< endl;  
}


int main(int argc, char **argv)
{

  double t20,t30, Sorting_time, h3, h4, procces_comblists_time;

  F1 = new List<int>;

  seconds(ts);

  parse_args(argc, argv);
  partition_alloc(dataf, idxf);
  read_files(F1);

  //cout << "F1 before sorting is : " << *F1 << endl;
  seconds(t20);
  sorting(F1);
  seconds(t30);
  Sorting_time = t30 -t20;

  cout << "F1 Size is : " << F1->size() << endl;

  //cout << "F1 after sorting is : " << *F1 << endl;
  //Listnode<int> *lptr = F1->head();
  //while (lptr){
            //cout << "sup("<< lptr->getdata() << ") = "<< lptr->sup()<<" ";
            //lptr = lptr->getnext();
  //}
  //cout << "F1 Sorting time is  : " << Sorting_time << endl;

  seconds(h3);
  procces_comblists(F1);
  seconds(h4);
  procces_comblists_time =(h4 - h3);

  //cout << "The combine Lists are: " << endl;
  //Listnode<int> *fptr= F1 -> head();
  //for (;fptr; fptr = fptr->getnext()){    
   //    int b = fptr ->getdata(); 
     //  if (eqgraph2[b]->size()>0) cout <<"combine set of item ("<<b<<") is "
       //                     << *eqgraph2[b]<<endl;
   //} 

  Max_itset_algo();
   
  //close(it2_fd);
  //munmap((char *)it2_cnt, it2flen);
  
  partition_dealloc();
  
  summary << "GENMAX ";
  if (diff_input) summary << "DIFFIN ";
  else if (use_diff_f2) summary << "DIFF2 ";
  else if (use_diff) summary << "DIFF ";
  summary << dataf << " " << MINSUP_PER << " "
          << DBASE_NUM_TRANS << " " << MINSUPPORT << " ";  

   seconds(te);

   cout << ";Time used for extend: " << extend_time << endl;
   cout << ";Copy Time: " << copy_time << endl;
   cout << ";Procces_comblists_time: " <<  procces_comblists_time << endl;
   cout << ";Time used for find operation: " << find_time << endl;
   cout << ";Time used for Differences: " << tid_difference_time 
        << endl;
   cout << ";Time used for supper set checking in extend:  "<< super_set_time 
        <<endl;
   cout << ";Time used for reading external data base and" << endl 
        << "          Computing lower level Diferences:   " << read_dbase_time 
        << endl;
   cout << ";Total elapsed time " << te-ts 
        << "; NumIntersect " << num_intersect <<"\n";

   stats.tottime = te-ts;
   summary << stats << " " << num_intersect;
   struct rusage ruse;   
   getrusage(RUSAGE_SELF,&ruse);   
   summary << " " << getsec(ruse.ru_utime) << " "
           << getsec(ruse.ru_stime) << endl;  
   
  exit(0);
}