huffman coding, greedy algorithm.

std::priority_queue, std::partition,

when i use the three commented lines, excution time increase to 15ms from 0ms, due to worse locality?

thanks to

http://acm.hdu.edu.cn/discuss/problem/post/reply.php?action=support&postid=5699&messageid=2&deep=1

for the provided test case. below is an excerpt,

input

AAAAABCD

THE_CAT_IN_THE_HAT

A

ABCD

AAAAA

ABCDEFGH

END

output

64 13 4.9

144 51 2.8

8 1 8.0

32 8 4.0

40 5 8.0

64 24 2.7

#include <cstdio>

#include <queue>

#include <algorithm>

#include <functional>

int main() {

    //freopen("input.txt","r",stdin);

    const int MAXSIZE=256;

    char line[MAXSIZE], *q;

    //int times[MAXSIZE]={0}, i,tmp,len, sum,res, *p,*pu=times+1,*pn=times+(2-'0'),*pc=times+(12-'A');

    int times[MAXSIZE]={0}, i,tmp,len, sum,res, *p,*pu=times+1,*pn=times+2,*pc=times+12;

    std::priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap;

    while(scanf("%256s",line)==1 && strcmp(line,"END")!=0) {

        for(q=line;tmp=*q;++q) {

            //if(tmp>='A' && tmp<='Z') ++pc[tmp];

            //else if(tmp>='0' && tmp<='9') ++pn[tmp];

            if(tmp>='A' && tmp<='Z') ++pc[tmp-'A'];

            else if(tmp>='0' && tmp<='9') ++pn[tmp-'0'];

            else ++*pu;

        }

        p=std::partition(pu,pu+37,[](int i) { return i>0; });

        len=p-pu;

        if(len<2) { res=strlen(line); }

        else {

            while(--p!=times) my_min_heap.push(*p);

            for(res=0,i=1;i<len;++i) {

                sum=my_min_heap.top(); my_min_heap.pop();

                sum+=my_min_heap.top(); my_min_heap.pop();

                my_min_heap.push(sum);

                res+=sum;

            }

            my_min_heap.pop();

        }

        std::fill(pu,pu+len,0);

        len=strlen(line)<<3;

        printf("%d %d %.1f\n",len,res,(double)len/res);

    }

    return 0;

}

版权声明：本文为博主原创文章，未经博主允许不得转载。// p.s. If in any way improment can be achieved, better performance or whatever, it will be well-appreciated to let me know, thanks in advance.