Re: Difference Of Two Strings (in C)

[Fastolfe]

And lastly, since it's speed we're after, a C implementation can't hurt. This benchmarks orders of magnitude faster than anything seen yet. (Update: fixed memory leak)

use Inline C => <<'__EOC__';

SV *fast_c (char *original, char *chopped) {
        int counts[256] = {0};  /* each potential character */
        int ptr = 0;
        int buffer_size = 0;
        char *ret = NULL;
        int ret_ptr = 0;
        int error = 0;
        SV *retsv = &PL_sv_undef;

        while (original[ptr] != '\0') {
                counts[original[ptr++]]++;
                buffer_size++;
        }

        ptr = 0;

        while (!error && chopped[ptr] != '\0') {
                counts[chopped[ptr]]--;
                buffer_size--;
                if (counts[chopped[ptr++]] < 0) {
                        error++;
                }
        }

        if (!error) {
                ret = malloc(buffer_size + 1);
                for (ptr = 0; ptr <= 255; ptr++) {
                        while (counts[ptr]-- > 0) {
                                ret[ret_ptr++] = ptr;
                        }
                }
                ret[ret_ptr] = '\0';
                retsv = newSVpvn(ret, strlen(ret));
                free(ret);
        }

        return(retsv);
}

__EOC__

And then here's a C implementation of demerphq's "scanning" method, which doesn't rely on counting up letters. This one's even faster:

use Inline C => <<'__EOC__';

SV *scan_c (char *from, char *to) {
        int f = 0;
        int t = 0;

        int from_len = strlen(from);
        int to_len = strlen(to);
        int ret_ptr = 0;
        unsigned char fc, tc;
        int error = 0;
        SV *retsv;
        char *ret;

        if (!from_len || !to_len) return(&PL_sv_undef);
        ret = malloc(from_len > to_len ? from_len+1 : to_len+1);

        while(!error) {
                fc = from[f];
                tc = to[t];

                if (fc == tc) {
                        f++; t++;
                        if (to[t] && (to[t] != tc)) {
                                while (from[f] == fc) {
                                        f++;
                                        ret[ret_ptr++] = fc;
                                }
                        }
                        if (t == to_len) error = 1;
                } else if (!fc || (fc < tc)) {
                        ret[ret_ptr++] = fc;
                        f++;
                        if (f >= from_len) error = 2;
                } else {
                        error = 2;
                }
        }

        if (error < 2) {
                while(f <= from_len) {
                        ret[ret_ptr++] = from[f++];
                }
                retsv = newSVpvn(ret, strlen(ret));
        } else {
                retsv = &PL_sv_undef;
        }
        free(ret);
        return retsv;
}

__EOC__

[demerphq]

Thats really cool Fastolfe its neat to see my code converted to C. Im really going to have to bone up my skills in that area.

Thanks alot, it looks like you just provided me an excuse to learn something new...

Yves / DeMerphq
--
Have you registered your Name Space?

[Fastolfe]

"converted to C"... poorly. :)

I'm no XS or C wizard by any stretch, but it is fun to play with it in situations like this.