Arch Linux

tavianator

Member

From: Waterloo, ON, Canada

Registered: 2007-08-21

Posts: 859

Website

Re: [SOLVED] C programming help

Does this mean it would need 32 or 64 times the input length memory? *eek* But it's all on the stack, right?

Nothing quite that bad, just O(k) memory (for chars, k is 8).

Woo you guys are still going at it! Cdh, I think your algorithm is O(log n) though I forget exactly how to calculate it. Never totally understood big O crap... has something to do with best case being 1 and worst being n/2 or some such voodoo. Congrats!

Well it can't be O(log n) because you have to look at all the bytes to answer the question.  How can you count the repeated characters in "mississippi" if you only look at 3 characters?

Here is a version I wrote for kicks a few days ago. You memory-shy types might enjoy it. Obviously, I prefer tav's and SoleSoul's approach myself. Much simpler. This is just a perversion of this simple approach.

#include <stdio.h>
#include <stdint.h>

int main ()
{
    uint32_t seen, dups, mask;
    int count, i;
    char ch;

    seen = dups = 0;

    printf("word: ");
    while (1) {
        ch = getchar();
        if (ch == '\n' || ch == EOF) break;
        if (ch < 'a' || ch > 'z') continue;

        mask = 1 << (ch - 'a');
        if (dups & mask) continue;

        if (seen & mask) dups |= mask;
        else seen |= mask;
    }

    for (i=0; i<28; ++i) {
        if (dups & (1<<i)) count++;
    }

    printf("%d repeated characters.\n", count);

    return 0;
}

it's probably less efficient than just using a plain array and a little wacky in general.

Ooh, nice!  That's probably faster than mine, since the masks fit in registers, as opposed to the array on the stack.

newcomer

Member

Registered: 2011-06-22

Posts: 5

Re: [SOLVED] C programming help

If im not mistaken, in theory, theres an O(n) solution involving only 406 bits (42 for a-z) of storage, instead of 512 (52 for a-z). (Minimum integer n that satisfies 3^256 <= 2^n (26 for a-z), since theres only 3 states required; 'not seen', 'seen once', 'seen more than once')
It involves using <2 bits per possible character, using the fact that theres space lost (A char with the 'duplicate' flag implies it has been seen already).

But I guess the implementation would be too hard to write just for the small space advantage.

tavianator

Member

From: Waterloo, ON, Canada

Registered: 2007-08-21

Posts: 859

Website

Re: [SOLVED] C programming help

If im not mistaken, in theory, theres an O(n) solution involving only 406 bits (42 for a-z) of storage, instead of 512 (52 for a-z). (Minimum integer n that satisfies 3^256 <= 2^n (26 for a-z), since theres only 3 states required; 'not seen', 'seen once', 'seen more than once')
It involves using <2 bits per possible character, using the fact that theres space lost (A char with the 'duplicate' flag implies it has been seen already).

But I guess the implementation would be too hard to write just for the small space advantage.

This is true, but if you can write an implementation that's at most 106 bits (10 for a-z) larger than juster's/your solution, then you can have my job .  Remember, code size is memory too.

jac

Member

From: /home/jac

Registered: 2009-05-19

Posts: 431

Website

Re: [SOLVED] C programming help

You could do an in-place (any) sort. Then loop over it and count when there are duplicate characters. If the character is a duplicate skip characters until you get to a new one and perform the same check. Then you just need a counter for the number of duplicates (8 bits). So, you have the space for the input, then an 8 bit integer. Time complexity is the sort plus one run through the input. If you really want to be space efficient about it. If the input is larger than the number of characters in your alphabet, just use the count of how many times you've seen each character and don't store the input at all.

Please not I sort of trailed off watching a movie during the middle-ish of this thread, so this may have been said already

Last edited by jac (2011-07-12 22:29:58)