demo_c.c

一个讲文本排序的算法论文,附带源码.

int hsearch(char *s)
{   Hptr p;
    for (p = hashtab[hashfunc(s)]; p; p = p->next)
        if (scmp(s, p->str) == 0)
            return 1;
    return 0;
}

int hsearch2(char *ins)
{   Hptr p;
    char *s, *t;
    for (p = hashtab[hashfunc(ins)]; p; p = p->next) {
        // if (scmp(ins, p->str) == 0)
        //     return 1;
        for (s = ins, t = p->str; *s == *t; s++, t++)
            if (*s == 0)
                return 1;
    }
    return 0;
}

int hsearch3(char *s)
{   Hptr p;
    for (p = hashtab[hashfunc(s)]; p; p = p->next)
        if (strcmp(s, p->str) == 0)
            return 1;
    return 0;
}

// Radix Sort -- McIlroy, Bostic and McIlroy

#define SIZE 510
#define THRESHOLD 16

typedef char *string;
typedef struct { string *sa; int sn, si; } rstack_t;

#define rswap(p, q, r)    r = p, p = q, q = r

void simplesort(string *a, int n, int b)    /* insertion sort */
{     string *ak, *ai, s, t;

    for (ak = a+1; --n >= 1; ak++) {
        for (ai = ak; ai > a; ai--) {
            for (s = ai[0]+b, t = ai[-1]+b; *s; s++, t++)
                if (*s != *t)
                    break;
            if (*s >= *t)
                break;
            rswap(ai[0], ai[-1], s);
        }
    }
}

#define push(a, n, i)    sp->sa = a, sp->sn = n, (sp++)->si = i
#define pop(a, n, i)    a = (--sp)->sa, n = sp->sn, i = sp->si
#define stackempty()    (sp <= stack)

void rsorta(string *a, int n, int b)
{   rstack_t        stack[SIZE], stmp, *oldsp, *bigsp, *sp = stack;
    string        *pile[256], *ak, *an, r, t;
    static int    count[256], cmin, nc;
    int        c, *cp;

    push(a, n, b);
    while (!stackempty()) {
        pop(a, n, b);
        if(n < THRESHOLD) {        // divert
            simplesort(a, n, b);
            continue;
        }
        an = a + n;
        if(nc == 0) {            // nonrecursive?
            cmin = 255;        // tally
            for (ak = a; ak < an; ) {
                c = (*ak++)[b];
                if(++count[c] == 1 && c) {
                    if(c < cmin) cmin = c;
                    nc++;
            }    }
            if(sp+nc > stack+SIZE) { // stack overflow
                rsorta(a, n, b);
                continue;
        }    }
        oldsp = bigsp = sp, c = 2;    // logarithmic stack
        pile[0] = ak = a + count[0];    // find places
        for(cp = count+cmin; nc > 0; cp++, nc--) {
            while(*cp == 0) cp++;
            if(*cp > 1) {
                if(*cp > c) c = *cp, bigsp = sp;
                push(ak, *cp, b+1);
            }
            pile[cp-count] = ak += *cp;
        }
        rswap(*oldsp, *bigsp, stmp);
                        // permute home
        for(ak = a; ak < an; ak += count[c], count[c] = 0) {
            r = *ak;
            while(--pile[c = r[b]] > ak)
                rswap(*pile[c], r, t);
            *ak = r;
        }        // here nc = count[...] = 0
}    }

void rsort(string *a, int n) { rsorta(a, n, 0); }



// TIMING

// Sort support functions

void scramble(char *x[], int n)
{   int i;
    for ( ; n > 0; n--) {
        i = rand() % (n+1);
        swap(n, i);
    }
}

int qscomp(const void *p, const void *q )
{   return strcmp(* (char**) p, * (char**) q );
}
#define DOQSORT qsort((void *) a, (size_t) n, sizeof(char *), qscomp)


// Insertion support functions

int instype;

void rinsall(char **a, int n)
{   int m;
    if (n < 1) return;
    m = n/2;
    switch (instype) {
    case 1: root = insert1(root,a[m]); break;
    case 2: insert2(a[m]); break;
    case 9: break;
    }
    rinsall(a, m);
    rinsall(a + m+1, n-m-1);
}

void insall(char **a, int n)
{   switch (instype) {
    case 1: root = 0; rinsall(a, n); break;
    case 2: root = 0; bufn = freen = 0; rinsall(a, n); break;
    case 9: rinsall(a, n); break;
    }
}

// Search support functions

int searchtype;

void searchall(char **a, int n)
{   int i, j;
    char s[100]; 
    for (i = 0; i < n; i++) {
        strcpy(s, a[i]);
        // s[0]++;  // Uncomment for unsuccessful searches
        switch(searchtype) {
        case 1: j = search1(s); break;
        case 2: j = search2(s); break;
        case 3: srchtop = 0; pmsearch(root, s); j = srchtop; break;
        case 4: srchtop = 0; nearsearch(root, s, 0); j = srchtop; break;
        case 5: j = sbsearch(s, a, n); break;
        case 6: j = hsearch(s); break;
        case 7: j = hsearch2(s); break;
        case 8: j = hsearch3(s); break;
        case 9: j = 1; break;
        }
        if (j != 1)  // Comment for unsuccessful searches
           printf("search bug at %d, val %d\n", i, j);
    }    
}


// Main timing

int    n = 0, starttime,  rptctr;

#define TASK(s)    printf("%s", s);
#define CIN        starttime = clock();
#define COUT    printf("\t%d", clock()-starttime);
#define NL    printf("\n")
#define REPEAT(s)    for (rptctr=0; rptctr<5; rptctr++) { s }; NL;

char space[1000000], *a[100000];

void timeall()
{   TASK("System Qsort")
        REPEAT(scramble(a, n); CIN; DOQSORT; COUT;)
    TASK("Simple MKQSort");
        REPEAT(scramble(a, n); CIN; ssort1main(a, n); COUT;)
    TASK("Faster MKQSort");
        REPEAT(scramble(a, n); CIN; ssort2main(a, n); COUT;)
    TASK("Radix Sort");
        REPEAT(scramble(a, n); CIN; rsort(a, n); COUT;)
    TASK("Null Insert");
        instype = 9;
        REPEAT(CIN; insall(a, n); COUT;)
    TASK("Simp TST Insert");
        instype = 1;
        REPEAT(CIN; insall(a, n); COUT; cleanup1(root);)
    TASK("Fast TST Insert");
        instype = 2;
        REPEAT(CIN; insall(a, n); COUT; cleanup2();)
    TASK("Null Search");
        searchtype = 9;
        REPEAT(CIN; searchall(a, n); COUT;)
instype = 2; insall(a, n);    // Build TST for searching
    TASK("Simp TST Search");
        searchtype = 1;
        REPEAT(CIN; searchall(a, n); COUT;)
    TASK("Fast TST Search");
        searchtype = 2;
        REPEAT(CIN; searchall(a, n); COUT;)
    TASK("PM TST Search");
        searchtype = 3;
        REPEAT(CIN; searchall(a, n); COUT;)
    TASK("Near TST Search");
        searchtype = 4;
        REPEAT(CIN; searchall(a, n); COUT;)
cleanup2();                   // Remove TST
    TASK("Binary Search");
        searchtype = 5;
        REPEAT(CIN; searchall(a, n); COUT;)
    TASK("Build Hash");
        CIN;
        hbuild(a, n); // Build once -- no cleanup
        COUT; NL;
    TASK("Hash Search");
        searchtype = 6;
        REPEAT(CIN; searchall(a, n); COUT;)
    TASK("Hash, Inln Cmp");
        searchtype = 7;
        REPEAT(CIN; searchall(a, n); COUT;)
    TASK("Hash, Sys Cmp");
        searchtype = 8;
        REPEAT(CIN; searchall(a, n); COUT;)
// Hash table is still using space
}

void buildptrtree()
{   TASK("Building TST");
        CIN;
        storestring = 1;    // Sleazy hack: store strings in eqkid
        ssort2main(a, n);
        instype = 2;
        insall(a, n);
        COUT; NL;
}

void trysearch()
{   char s[100];
    int i, d;

    buildptrtree();
    printf("Enter searches: <nndistance> <word>  (dist=-1 for pm search)\n");
    while (scanf("%d %s", &d, s) != EOF) {
        srchtop = 0;
        nodecnt = 0;
        CIN;
        if (d < 0)
            pmsearch(root, s);
        else
            nearsearch(root, s, d);
        printf(" matches=%d nodes=%d clicks=", srchtop, nodecnt);
        COUT; NL;
        for (i = 0; i < min(srchtop, 40); i++)
            printf(" %s", srcharr[i]);
        NL;
    }
}

void nncost()
{   int i, d, mincost, minind, maxcost, maxind; 
 	double sum;
    buildptrtree();
    for (d = 0; d <= 4; d++) {
        CIN;
        mincost = 999999; maxcost = -1; sum = 0.0;
        for (i = 0; i < n; i++) {
            srchtop = 0; nodecnt = 0;
            nearsearch(root, a[i], d);
			sum += nodecnt;
            if (nodecnt <= mincost) { mincost = nodecnt; minind = i; }
            if (nodecnt >= maxcost) { maxcost = nodecnt; maxind = i; }
        }
        printf("Dist %d\t%d %s\t%d %s\t%g", d,
            mincost, a[minind],
            maxcost, a[maxind],
			sum/n);
        COUT; NL;
    }    
}

void pmcost()
{   int i, j, l, u, mincost, minind, maxcost, maxind;
	double sum;
	char buf[100]; 
    buildptrtree();
    printf("Enter l, u pair\n");
	while (scanf("%d %d", &l, &u) != EOF) {
        CIN;
        mincost = 999999; maxcost = -1; sum = 0.0;
        for (i = 0; i < n; i++) {
            strcpy(buf, a[i]);
            for (j = l; j <= u; j++)
				buf[j] = '.';
            srchtop = 0; nodecnt = 0;
            pmsearch(root, buf);
			sum += nodecnt;
            if (nodecnt <= mincost) { mincost = nodecnt; minind = i; }
            if (nodecnt >= maxcost) { maxcost = nodecnt; maxind = i; }
        }
        printf("Range: %d,%d\t%d %s\t%d %s\t%g", l, u,
            mincost, a[minind],
            maxcost, a[maxind],
			sum/n);
        COUT; NL;
	}
}


int main(int argc, char *argv[])
{   int    i, globalstarttime;
    char *s = space, *t, *fname;
    FILE *fp;

    if (argc == 1) // no args
        fname = "/usr/dict/words";
    else // one arg: file name
        fname = argv[1];
    setbuf(stdout, 0);
    if ((fp = fopen(fname, "r")) == NULL) {
        fprintf(stderr, "  Can't open file\n");
        exit(1);
    }
    globalstarttime = clock();
    TASK("Big Malloc");
        CIN;
        t = (char *) malloc(8000000*sizeof(char));
        free(t);
        COUT; NL;
    TASK("Reading Input");
        CIN;
        a[0] = s;
        while ((i = getc(fp)) != EOF) {
            if (i == '\n') {
                *s++ = 0;
                a[++n] = s;
            } else
                *s++ = i;
        }
        COUT; NL;
    if (argc < 3) { // one arg: file name
        timeall();
    } else {
        if (strcmp(argv[2], "trysearch") == 0) {
            trysearch();
        } else if (strcmp(argv[2], "nncost") == 0) {
            nncost();
        } else if (strcmp(argv[2], "pmcost") == 0) {
			pmcost();
		} else
            printf("Unrecognized option\n");
    }
    i = clock() - globalstarttime;
    printf("Total clicks\t%d\nTotal secs\t%4.3f\n",
        i, (double) i / CLOCKS_PER_SEC);
    return 0;
}