我已经读取了文本中的单词，并建了一棵二叉树，然后将二叉树的结点都推入指针栈中，然后运用快速排序的算法，最后输出结果，代码如下：
跑一篇单词很大的英文小说
平均占用内存:288.376K 平均CPU时间:0.891S 平均墙钟时间:0.419S
请问怎么改动程序，使其跑得更快？
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#define MAX 50
struct tnode{
char word[MAX];
int count;
struct tnode *left,*right;
};
typedef struct sort{
int num;
char w[50];
}List;
List list[1000000];
struct tnode *arr[1000000];
int curr=0;
int cmp(const void *a,const void *b)
{
List *p1 = (List*)a;
List *p2 = (List*)b;
if(p1->num!=p2->num)
return p2->num-p1->num;
else
return strcmp(p1->w,p2->w);
}
struct tnode *treewords(struct tnode *,char *);
void treeprint(struct tnode *);
int main()
{
char word[MAX];
FILE *bfp;
FILE *out;
char c;
int i,k,n;
struct tnode *root;
root=NULL;
bfp=fopen("article.txt","r");
while((c=fgetc(bfp))!=EOF){
ungetc(c,bfp);
for(i=0;(c=fgetc(bfp))!=' '&&c!='\n'&&c!=EOF;i++){
if((c>='A'&&c<='Z')||(c>='a'&&c<='z')){
c=tolower(c);
word[i]=c;
}else
break;
}
word[i]='\0';
if(strlen(word)>0)
root=treewords(root,word);
}
treeprint(root);
for(i=0;i<curr;i++){
list[i].num=arr[i]->count;
strcpy(list[i].w,arr[i]->word);
}
n=curr;
qsort(list,n+1,sizeof(list[0]),cmp);
out=fopen("wordfreq.txt","w");
for(k=0;k<curr;k++){
fprintf(out,"%s %d\n",list[k].w,list[k].num);
}
for(k=0;k<100;k++){
printf("%s %d\n",list[k].w,list[k].num);
}
fclose(bfp);
fclose(out);
return 0;
}
struct tnode *treewords(struct tnode *p,char *w)
{
int cond;
if(p==NULL){
p=(struct tnode*)malloc(sizeof(struct tnode));
strcpy(p->word,w);
p->count=1;
p->left=p->right=NULL;
}
else if((cond=strcmp(w,p->word))==0){
p->count++;
}
else if(cond<0){
p->left=treewords(p->left,w);
}
else
p->right=treewords(p->right,w);
return (p);
}
void treeprint(struct tnode *p)
{
if(p!=NULL){
treeprint(p->left);
arr[curr++]=p;
treeprint(p->right);
}
}亮点在这里
List list[1000000];
struct tnode *arr[1000000];32位下，List根据内存对齐会有56个字节，1M个List，还有1M个指针…
可以着手从下面几个方面优化：
将
fgetc逐个读取字母的方式改为 先读取输入文件的一段内容到缓冲区然后处理缓冲区内的数据 的方式if(strlen(word)>0)这里可以用if (i > 0)来替代-
对排序用的数据结构和单词数据结构调整，方便拷贝
struct tnode{ char word[MAX]; int count; struct tnode *left,*right; }; typedef struct sort{ int num; char w[50]; }List; // 可以改为 struct tnode{ int count; char word[MAX]; struct tnode *left,*right; }; typedef struct sort{ int num; char w[50]; }List; // 然后排序之前的拷贝可以使用`memcpy`完成，高效 如果以后数据量很大，当前的树也可能成为瓶颈，可以考虑更复杂的
BST或者AVL