C语言 词频统计，怎么让程序跑的更快，还可以优化哪些？

问题描述

问 题

我已经读取了文本中的单词，并建了一棵二叉树，然后将二叉树的结点都推入指针栈中，然后运用快速排序的算法，最后输出结果，代码如下：
跑一篇单词很大的英文小说
平均占用内存: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);    
    }
}

解决方案

可以着手从下面几个方面优化：

• 将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

这篇关于C语言 词频统计，怎么让程序跑的更快，还可以优化哪些？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！