📄 parallelapriori.cpp
字号:
{
printf(" %c",fullSet[i][j]);
}
printf("\n");
}
p=(struct tItem*)malloc(sizeof(struct tItem));
p=frequence;
while(p!=NULL)
{
printf(" %c",p->itemset[p->tag]);
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}
printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");*/
//for(k=2;frequence!=NULL;k++)
//while(candidate!=NULL)
//{
//printf("++++++++++++++++++++++++++++++++++++++++++++\n");
candidate=apriori_gen(frequence);
if(candidate!=NULL)
{
candidate=Compute_candidateItem_Num(candidate,recordNum,colNum,fullSet);
destRank=1;
stag=1;
p=candidate;
p1=candidate;
while(p!=NULL)
{
count++;
p=p->next;
}
//printf(" #%d#\n",count);
//MPI_Barrier(MPI_COMM_WORLD);
for(i=1;i<=rankNum-1;i++) //向其他进程发送局部候选k项集
{
p=candidate;
if(i!=rank)
{
MPI_Send(&count,1,MPI_INT,destRank,24,MPI_COMM_WORLD);
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
MPI_Send(&p->itemset[j],1,MPI_CHAR,destRank,25,MPI_COMM_WORLD);
}
MPI_Send(&p->count,1,MPI_INT,destRank,26,MPI_COMM_WORLD);
MPI_Send(&p->tag,1,MPI_INT,destRank,27,MPI_COMM_WORLD);
p=p->next;
}
}
destRank++;
stag++;
}
//MPI_Barrier(MPI_COMM_WORLD);
int reRank=1,reTag=1,itemNum;
int rCount,rTag,s;
char rItemset;
tItem *r;
r=(struct tItem*)malloc(sizeof(struct tItem));
for(j=1;j<=rankNum-1;j++) //接收其他进程发送来的局部候选k项集
{
if(j!=rank)
{
s=0;
MPI_Recv(&itemNum,1,MPI_INT,reRank,24,MPI_COMM_WORLD,&status);
while(s<itemNum)
{
for(m=0;m<=p1->tag;m++)
{
MPI_Recv(&r->itemset[m],1,MPI_CHAR,reRank,25,MPI_COMM_WORLD,&status);
//printf(" %c",r->itemset[m]);
}
MPI_Recv(&r->count,1,MPI_INT,reRank,26,MPI_COMM_WORLD,&status);
MPI_Recv(&r->tag,1,MPI_INT,reRank,27,MPI_COMM_WORLD,&status);
candidate=Combine_candidate_k_itemsets(candidate,r);
//printf(" %c",rItemset);
//printf(" %d",r->count);
//printf(" %d",r->tag);
//printf("\n");
s++;
}
//printf("\n");
//printf("&&&&&&&&&&&&&&&&&&&&&\n");
}
reRank++;
reTag++;
}
//MPI_Barrier(MPI_COMM_WORLD);
/*cp=candidate;
count=0;
printf("--------The candidate %d_itemsets--------\n",cp->tag+1);
while(cp!=NULL)
{
for(j=0;j<=cp->tag;j++)
{
printf(" %c",cp->itemset[j]);
}
printf(" %d",cp->count);
printf(" %d",cp->tag);
printf("\n");
count++;
cp=cp->next;
}
printf("\n");
printf("The total number is: %d\n",count);
printf("\n");*/
//MPI_Barrier(MPI_COMM_WORLD);
frequence=candidate;
fpb=(struct tItem*)malloc(sizeof(struct tItem));
fp=(struct tItem*)malloc(sizeof(struct tItem));
fpb=frequence;
fp=fpb->next;
//int minNum=(int)((recordNum*minSup)+1);
//printf("########## %d\n",minNum);
while(fp!=NULL) //删除后选项集中支持度小于最小支持度的项目，生成频繁项集
{
if(fpb->count<minNum)
{
frequence=fp;
fpb=fp;
fp=fp->next;
}
if(fp->count<minNum)
{
fp=fp->next;
fpb->next=fp;
}
else
{
fp=fp->next;
fpb=fpb->next;
}
}
/*fp=frequence;
count=0;
printf("--------The frequence %d_itemsets--------\n",fp->tag+1);
while(fp!=NULL)
{
//MPI_Barrier(MPI_COMM_WORLD);
for(j=0;j<=fp->tag;j++)
{
printf(" %c",fp->itemset[j]);
}
printf(" %d",fp->count);
printf(" %d",fp->tag);
printf("\n");
count++;
fp=fp->next;
}
printf("\n");
printf("The total number is: %d\n",count);
printf("\n");*/
//MPI_Barrier(MPI_COMM_WORLD);
}
else
{
//return (NULL);
//break;
frequence=NULL;
}
//printf("++++++++++++++++++++++++++++++++++++++++++++\n");
//MPI_Barrier(MPI_COMM_WORLD);
//}
return (frequence);
}
struct tItem *Gen_frequence1(tItem *frequence, int recordNum, int colNum, int minNum, char **fullSet) //生成频繁项集
{
tItem *candidate,*cp,*fp,*fpb,*p,*p1;
int i,j,k,m,count=0,rank,rankNum,destRank,stag;
//int i,m,n;
//char *buffer;
MPI_Status status;
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
MPI_Comm_size(MPI_COMM_WORLD,&rankNum);
//printf("*******************************************\n");
/*printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");
printf("##### %d\n",recordNum);
printf("##### %d\n",colNum);
printf("##### %d\n",minNum);
printf("##### %d\n",rank);
for(i=0;i<recordNum;i++)
{
for(j=0;j<colNum;j++)
{
printf(" %c",fullSet[i][j]);
}
printf("\n");
}
p=(struct tItem*)malloc(sizeof(struct tItem));
p=frequence;
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
printf(" %c",p->itemset[j]);
}
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}
printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$\n");*/
//for(k=2;frequence!=NULL;k++)
//while(candidate!=NULL)
//{
printf("++++++++++++++++++++++++++++++++++++++++++++\n");
candidate=apriori_gen(frequence);
/*p=candidate;
int t=0;
printf("测试结果\n");
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
printf(" %c",p->itemset[j]);
}
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
t++;
p=p->next;
}
printf("一共有 %d\n",t);
printf("结束测试\n");*/
/*if(rank==2)
{
printf("!!!!!!\n");
p=candidate;
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
printf(" %c",p->itemset[j]);
}
printf(" %d",p->count);
printf(" %d",p->tag);
printf("\n");
p=p->next;
}
}
printf("!!!!!!\n");*/
if(candidate!=NULL)
{
//printf("!!!!!!\n");
candidate=Compute_candidateItem_Num(candidate,recordNum,colNum,fullSet);
destRank=1;
stag=1;
p=candidate;
p1=candidate;
while(p!=NULL)
{
count++;
p=p->next;
}
//printf(" #%d#\n",count);
//printf("进行到这里\n");
//MPI_Barrier(MPI_COMM_WORLD);
for(i=1;i<=rankNum-1;i++) //向其他进程发送局部候选k项集
{
p=candidate;
if(i!=rank)
{
MPI_Send(&count,1,MPI_INT,destRank,54,MPI_COMM_WORLD);
//printf("### %d ###\n",count);
while(p!=NULL)
{
for(j=0;j<=p->tag;j++)
{
MPI_Send(&p->itemset[j],1,MPI_CHAR,destRank,55,MPI_COMM_WORLD);
//printf(" %c",p->itemset[j]);
}
MPI_Send(&p->count,1,MPI_INT,destRank,56,MPI_COMM_WORLD);
MPI_Send(&p->tag,1,MPI_INT,destRank,57,MPI_COMM_WORLD);
//printf(" %d",p->count);
//printf(" %d",p->tag);
//printf("\n");
p=p->next;
}
}
destRank++;
stag++;
}
//MPI_Barrier(MPI_COMM_WORLD);
int reRank=1,reTag=1,itemNum;
int rCount,rTag,s;
char rItemset;
tItem *r;
r=(struct tItem*)malloc(sizeof(struct tItem));
for(j=1;j<=rankNum-1;j++) //接收其他进程发送来的局部候选k项集
{
if(j!=rank)
{
s=0;
MPI_Recv(&itemNum,1,MPI_INT,reRank,54,MPI_COMM_WORLD,&status);
while(s<itemNum)
{
for(m=0;m<=p1->tag;m++)
{
MPI_Recv(&r->itemset[m],1,MPI_CHAR,reRank,55,MPI_COMM_WORLD,&status);
//printf(" %c",r->itemset[m]);
}
MPI_Recv(&r->count,1,MPI_INT,reRank,56,MPI_COMM_WORLD,&status);
MPI_Recv(&r->tag,1,MPI_INT,reRank,57,MPI_COMM_WORLD,&status);
candidate=Combine_candidate_k_itemsets(candidate,r);
//printf(" %c",rItemset);
//printf(" %d",r->count);
//printf(" %d",r->tag);
//printf("\n");
s++;
}
//printf("\n");
printf("&&&&&&&&&&&&&&&&&&&&&\n");
}
reRank++;
reTag++;
}
//MPI_Barrier(MPI_COMM_WORLD);
cp=candidate;
count=0;
printf("--------The candidate %d_itemsets--------\n",cp->tag+1);
while(cp!=NULL)
{
for(j=0;j<=cp->tag;j++)
{
printf(" %c",cp->itemset[j]);
}
printf(" %d",cp->count);
printf(" %d",cp->tag);
printf("\n");
count++;
cp=cp->next;
}
printf("\n");
printf("The total number is: %d\n",count);
printf("\n");
//MPI_Barrier(MPI_COMM_WORLD);
frequence=candidate;
fpb=(struct tItem*)malloc(sizeof(struct tItem));
fp=(struct tItem*)malloc(sizeof(struct tItem));
fpb=frequence;
fp=fpb->next;
//int minNum=(int)((recordNum*minSup)+1);
//printf("########## %d\n",minNum);
while(fp!=NULL) //删除后选项集中支持度小于最小支持度的项目，生成频繁项集
{
if(fpb->count<minNum)
{
frequence=fp;
fpb=fp;
fp=fp->next;
}
if(fp->count<minNum)
{
fp=fp->next;
fpb->next=fp;
}
else
{
fp=fp->next;
fpb=fpb->next;
}
}
fp=frequence;
count=0;
printf("--------The frequence %d_itemsets--------\n",fp->tag+1);
while(fp!=NULL)
{
//MPI_Barrier(MPI_COMM_WORLD);
for(j=0;j<=fp->tag;j++)
{
printf(" %c",fp->itemset[j]);
}
printf(" %d",fp->count);
printf(" %d",fp->tag);
printf("\n");
count++;
fp=fp->next;
}
printf("\n");
printf("The total number is: %d\n",count);
printf("\n");
//MPI_Barrier(MPI_COMM_WORLD);
}
else
{
//return (NULL);
//break;
//frequence=NULL;
}
//printf("++++++++++++++++++++++++++++++++++++++++++++\n");
//MPI_Barrier(MPI_COMM_WORLD);
//}
return (frequence);
}
bool Has_infrequence_subset(tItem *pp, tItem *f) //判断候选k项集的子集是否在频繁k-1项集中
{
tItem *p,*fp; //储存*pp中的k-1项子集
int i=0,j,m=0;
bool flag;
while(i<=pp->tag)
{
p=(struct tItem*)malloc(sizeof(struct tItem));
for(j=0;j<pp->tag;j++)
{
if(j==i)
{
j++;
}
else
{
p->itemset[j]=pp->itemset[j];
}
}
fp=f;
while(fp!=NULL)
{
while(m<=fp->tag)
{
if(p->itemset[m]==fp->itemset[m])
{
m++;
}
else
{
flag=false;
m++;
}
}
flag=true;
fp=fp->next;
}
i++;
}
return (flag);
}
struct tItem *Gen_candidate_itemset(tItem *cp,tItem *cp1,tItem *cp2) //生成后选项
{
int i=0;
while(i<=cp1->tag)
{
cp->itemset[i]=cp1->itemset[i];
//cp->tag=cp1->tag+1;
i++;
}
cp->tag=cp1->tag+1;
cp->itemset[i]=cp2->itemset[i-1];
cp->count=0;
cp->next=NULL;
return (cp);
}
bool Is_before_equal(tItem *pp1, tItem *pp2) //判断两个项目集的前k-1项是否相同
{
int i=0;
bool flag;
while(i<pp1->tag)
{
if(pp1->itemset[i]==pp2->itemset[i])
{
flag=true;
}
else
{
flag=false;
break;
}
i++;
}
return (flag);
}
struct tItem *Compute_candidateItem_Num(tItem *c,int recordNum, int colNum, char **fullSet) //计算候选项集中每一项的最小支持数
{
tItem *cp;
int i,j,m,n;
char *buffer;
cp=c;
while(cp!=NULL) //统计每个候选项集的计数
{
for(i=0;i<recordNum;i++)
{
bool flag=true;
buffer=(char*)malloc(colNum*sizeof(char*));
for(j=0;j<colNum;j++)
{
buffer[j]=fullSet[i][j];
}
m=0;
while(m<=cp->tag)
{
bool flag1=false;
for(n=0;n<colNum;n++)
{
if(cp->itemset[m]==buffer[n])
{
flag1=true;
break;
}
flag1=false;
}
if(flag1==false)
{
flag=false;
}
m++;
}
if(flag==true)
{
cp->count++;
}
}
cp=cp->next;
}
return (c);
}
struct tItem *apriori_gen(tItem *freq) //生成候选项集
{
tItem *p1,*p2,*head,*cHead,*p,*pTail;
int tag,i=0;
//bool flag;
if(freq->next!=NULL)
{
head=freq;
p1=head;
p2=head;
p2=p2->next;
p=(struct tItem*)malloc(sizeof(struct tItem));
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -