0
\$\begingroup\$

The original task was to find the first non-repetitive character in a string.

Every now and then I read questions here on Code Review and try answering them myself, and as such I stumbled upon this one.

Now, I have two solutions:

The first one:

struct ch {
    int num;
    char c;
} characters[127];

char find_first_non_repetitive(char *string)
{
    int i = 0;

    for(i = 0; i < strlen(string); i++) {
        characters[string[i]].num++;
        characters[string[i]].c = string[i];
    }

    int index = characters[string[0]].num;
    char c = characters[string[0]].c;

    for(i = 1; i < 127; i++)
    {
        if(characters[i].num != 0 && first > characters[i].num) 
        {
            first = characters[i].num;
            c = characters[i].c;
        }
    }

    return c;
}

About this one, if using C# instead of C, my idea was to replace struct with an ArrayList<int>.

The second one:

char find_first_non_repetitive(char *string)
{
    const int NUM_CHARACTERS = 127;

    int i = 0, cha[NUM_CHARACTERS];

    for(i = 0; i < NUM_CHARACTERS; i++) cha[i] = 0;

    for(i = 0; i < strlen(string); i++) cha[string[i]]++;

    int index = cha[string[0]];
    char c = string[0];

    for(i = 1; i < strlen(string); i++)
    {
        if(index > cha[string[i]]) 
        {   
            index = cha[string[i]];
            c = string[i];
        }
    }

    return c;
}

Which one is more efficient, and is there an even more efficient way?

\$\endgroup\$
  • \$\begingroup\$ Please put (your interpretation of) the problem these codes are trying to solve into this question. You should also consider summarizing the behavior of each implementation. \$\endgroup\$ – PellMel Oct 20 '16 at 19:22
  • \$\begingroup\$ Your first code contains a syntax error, and neither code appears as if it would work correctly, at least as I interpret the problem. Please confirm that your codes produce the results you expect, and if they do, then even more so describe your interpretation of the problem directly in this question. \$\endgroup\$ – PellMel Oct 20 '16 at 19:38
  • \$\begingroup\$ @PellMel Both of them produce the results I expect, and as for the first one, my compiler doesn't throw any error (GCC + VSCode on Ubuntu). \$\endgroup\$ – Wade Tyler Oct 21 '16 at 13:03
  • \$\begingroup\$ Evidently, then, what you are compiling is different from what you posted, which gives me first1.c:18: error: ‘tring’ undeclared (first use in this function). It seems obvious how to correct that particular error, but its presence undermines my confidence that you have posted the correct code. \$\endgroup\$ – PellMel Oct 21 '16 at 14:04
  • \$\begingroup\$ Also: first1.c:22: error: ‘first’ undeclared (first use in this function). \$\endgroup\$ – PellMel Oct 21 '16 at 14:09
2
\$\begingroup\$

Common characteristics

Asymptotic complexity

Both algorithms perform θ(n) operations for strings of length n. Since the task always requires examining every character of the input, there can be no alternative that provides better asymptotic complexity than these do. Additionally, each has memory overhead that does not vary with the input, which affords no asymptotically better implementation in that respect either. Of course, implementations with the same asymptotic complexity are not all equivalent by either measure.

See also below, however: your implementations of these algorithms are potentially flawed and less efficient.

Wrong range for char

Your codes assume that the string elements all have numeric value between 1 and 126, inclusive, but char can be a signed type, and whether signed or unsigned it can have more than 7 value bits. Also, (char) 127 is always a valid char (from C's perspective). As a result, on any conforming C implementation there are valid C strings which, if provided as input to either of your functions, will cause that function to exhibit undefined behavior.

To solve this problem I suggest declaring your arrays with dimension UCHAR_MAX + 1, and casting input chars to type unsigned char before using them as indexes.

Failure behavior

Each function exhibits somewhat surprising behavior for non-empty inputs that contain no unrepeated characters. They return that character among those with the minimum number of repeats whose first appearance is earliest in the string. It's unclear what the function is supposed to do in that case, but the the actual behavior is potentially misleading. It would be better to return an error code.

You could use 0 as an error code, as it is the only char value that cannot appear inside a string. Your functions will already return 0 when presented with an empty string as input, though I'm uncertain whether that's by design. Alternatively, the functions could return type int, with the result being -1 when there is no unrepeated character, else the first non-repeated one cast to unsigned char. This is the scheme the getchar() function uses.

Loop termination conditions

Both codes contain loops with i < strlen(string) for their termination condition. The compiler can lift the evaluation of strlen() out of the loop only if it makes several assumptions about that function. Inasmuch as that's a standard library function, it is conceivable that that would happen, but by no means certain. If it doesn't happen then your implementations become θ(n2) instead of θ(n); I therefore recommend lifting the strlen() call out of the loop manually.

Alternatively, consider avoiding strlen() altogether -- since you need to iterate through the whole string anyway, just break the iteration when you reach the terminator. That should be more efficient.

Using type int for character counters

Each code uses objects of type int as character counters, but

  • that's a signed type, even though character counts should never be negative, and
  • its maximum value can be as low as 32767, which is a relatively low limit

I would suggest size_t instead, which should be sufficient for any representable string, but if you prefer something that may be a bit smaller (at the cost of restricting its range) then you could go with uint_least32_t (from stdint.h) for the smallest an unsigned integer type with at least 32 value bits, or uint_fast32_t for the fastest unsigned integer type with at least 32 value bits (these might or might not be the same type).

First implementation

Use of a file-scope variable

This version of the function relies on file-scope variable characters. Being declared a file scope gets it free initialization, but relying on that makes your function a one-shot. Even if you reset the contents of this array on each function call, relying on it makes your function non-thread-safe.

I recommend switching to a local (array) variable inside the function. If (and only if) you continue to use a file-scope variable then at least declare it static to give it internal linkage.

Questionable data structure

The struct ch type on which this version of the function relies seems a bit of a miss to me, for, as it is used, the value of member c is completely determined by the index of a given instance within array characters. This member is therefore redundant.

See also my previous comments about using type int for your character counters.

Second implementation

Make use of initialization

You declare array cha without an initializer, and then manually loop to set its initial contents. Given the data type and the initial values you want to set, it would be clearer and potentially more efficient to instead declare it with an initializer:

int cha[NUM_CHARACTERS] = { 0 };

... and skip the initialization loop. (Elements not explicitly designated in the initializer get initialized to 0.)

Comparative efficiency

It's hard to be sure what to compare here. The two codes comprise slightly-different versions of the same underlying algorithm. Implementing fixes for the various shortcomings I discussed would bring them to pretty much the same place, which would look more like the second code than the first.

There are a number of possible variations on this approach, some of which may run slightly faster than others, but I don't see room for anything substantially more efficient.

\$\endgroup\$
  • \$\begingroup\$ In your opinion, which one would you consider better? I believe that the second is not only easier to read and maintain, but also better memory-wise (I may be wrong), my first idea was to have an ArrayList like in C# or std::vector in C++, but as far as I know C doesn't have anything like it. \$\endgroup\$ – Wade Tyler Oct 21 '16 at 19:51
  • \$\begingroup\$ @WadeTyler, no, C does not have any dynamically-adjustable list data type in its standard library, nor indeed does its standard library focus on data types at all. In any case, supporting dynamic resizing is comparatively expensive. If speed is your primary concern, then an ordinary array is by far a better choice, including in C++ and C#. \$\endgroup\$ – PellMel Oct 21 '16 at 20:57
  • \$\begingroup\$ @WadeTyler, I believe I already said that fixing all the various shortcomings in your first code would (at least should) bring it much closer to the second code. You may interpret that as me endorsing the second as better, if you wish. The flaws specific to the first code are primarily about the key differences between it and the second. The two codes have a lot in common, however, including many of the same flaws. \$\endgroup\$ – PellMel Oct 21 '16 at 21:02
1
\$\begingroup\$

Simplification

In the first program, there are a couple of things that can be simplified:

  1. There is no need for the c member of the struct. characters[i].c always just equals i, so there's no reason to track it.

  2. Once you remove c, you don't need the struct any more, just an array of integers.

  3. You can move that global variable into the function.

Here is a sample rewrite of the first function:

char find_first_non_repetitive(const char *string)
{
    size_t i = 0;
    size_t characters[127] = {0};
    size_t len = strlen(string);

    for(i = 0; i < len; i++) {
        characters[string[i]]++;
    }

    size_t lowest = characters[string[0]];
    char c = string[0];

    for (i = 0; i < 127; i++) {
        if (characters[i].num != 0 && characters[i].num < lowest) {
            lowest = characters[i];
            c = i;
        }
    }

    return c;
}

Comparison

Both functions are similar. The first function loops a maximum of 127 times in the second loop, whereas the second function loops through the string again in the second loop. So depending on if the string is longer or shorter than 127 bytes, one function or the other will be faster. But since both functions need to traverse the string at least one full time, they have the same asymptotic complexity of \$O(n)\$, where \$n\$ is the length of the string.

Theoretical third implementation

Theoretically, there is a way to only have the one loop and then determine the answer in \$O(1)\$ time after that. The way to do it would be to create a doubly linked list of characters seen, ordered by the order in which they appear in the string (you create this list as you traverse the string, in addition to keeping a map of character -> node in a separate array). Whenever you encounter a repeat of a character, you remove that character from the doubly linked list. What remains at the end is a doubly linked list of non-repeated characters, of which you simply return the character at the head of the list.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer, I actually thought about the third implementation as a doubly linked list but for a big string I thought it would be too much. \$\endgroup\$ – Wade Tyler Oct 23 '16 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.