4
\$\begingroup\$

I pursued an according algorithm with an absolute best performance, the following class embodies the solution.

Any comment is welcome.

class TextCompressor
{
    private const char Seperator = '\x20';

    private StringBuilder builder;

    public TextCompressor()
    {
        this.builder = new StringBuilder();
    }

    public string Compress(string str)
    {
        int offset = 0;
        int end = str.Length - 1;

        for (int i = 0; i < end; i++)
        {
            if (Char.IsWhiteSpace(str[i]))
            {
                if (i != offset)
                {
                    if (str[i] == Seperator)
                    {
                        if (!Char.IsWhiteSpace(str[i + 1]))
                        {
                            i++;

                            continue;
                        }

                        builder.Append(str, offset, (i - offset) + 1);
                    }
                    else
                    {
                        builder.Append(str, offset, i - offset);
                        builder.Append(Seperator);
                    }
                }

                offset = i + 1;
            }
        }

        if (offset != 0)
        {
            builder.Append(str, offset, str.Length - offset);

            return Char.IsWhiteSpace(str[end]) ? Release().TrimEnd() : Release();
        }

        return Trim(str);
    }

    private static string Trim(string s)
    {
        return (s.Length != 0 && (Char.IsWhiteSpace(s[0]) || Char.IsWhiteSpace(s[s.Length - 1]))) ? s.Trim() : s;
    }

    private string Release()
    {
        string s = builder.ToString();

        builder.Length = 0;

        return s;
    }
}

Compress vs. Regex.Replace

.. using \s{2,}

String: " The quick brown fox jumps over the lazy dog. "

  • 1.97017 * (10 times faster)
  • 19.333874

String: "The quick brown fox jumps over the lazy dog."

  • 0.485821 * (16 times faster)
  • 8.049062
\$\endgroup\$
  • 3
    \$\begingroup\$ You might want to take a look at some tips for posting a good question.. I believe the main problem here is not just that there is a lack of a "How can I improve this?"-question, but the lack of description about what your code does. Also, while there has been discussion in the past about how to deal with questions not asking a question, I recommend adding a note like "Any and all comments welcome". \$\endgroup\$ – Simon Forsberg Feb 2 '16 at 16:53
  • 3
    \$\begingroup\$ The purpose of the code, and therefore the point of the question, seems obvious enough from the title alone. I see no reason to downvote or close this question. \$\endgroup\$ – 200_success Feb 2 '16 at 17:27
7
\$\begingroup\$

The good stuff

Your code looks neat and is pretty fast.

Remarks

I would second that the name Separator isn't chosen well and would like to suggest SpaceChar which is more obvious.

Review

The biggest problem I see is the missing null check for the parameter of the public method Compress. Throwing an ArgumentNullException instead of getting a NullReferenceException is better.

The Trim(string s) method doesn't buy you much. Saving some Ticks this way is a optimization which comes with less readable code. Just a call to string.Trim() is sufficient.

Initializing the StringBuilder like @Shelby115 suggested in his answer won't save you a lot but it is a good habit to do so. If you know how big the buffer of the StringBuilder can increase you should use that knowledge. With the default constructor the StringBuilder's internal buffer has a size of 16 which is doubled each time it is reached.

Instead of having this method in the TextCompressor class which implies that it compresses some text I would suggest making this an extension method.

I would like to suggest using a char [] instead of a StringBuilder and change the arrow code to something like this:

public static class StringExtensions
{
    public static string ReplaceMultipleWhiteSpaceWithSpace(this string str)
    {
        return str.ReplaceMultipleWhiteSpaceWithSeparator('\x20');
    }

    public static string ReplaceMultipleWhiteSpaceWithSeparator(this string str, char separator)
    {
        if (str == null) { throw new ArgumentNullException(str); }
        if (str.Length == 0) { return str; }

        int end = str.Length;
        int destinationOffset = 0;
        bool foundWhiteSpace = true;
        char current = separator;
        char[] destination = new char[end];

        for (int i = 0; i < end; i++)
        {
            if (Char.IsWhiteSpace(str[i]))
            {
                if (foundWhiteSpace) { continue; }

                foundWhiteSpace = true;
                current = separator;
            }
            else
            {
                foundWhiteSpace = false;
                current = str[i];
            }
            destination[destinationOffset] = current;
            destinationOffset++;
        }


        int newSize = foundWhiteSpace
            ? IndexOfLastNonWhithSpaceChar(destination, destinationOffset)
            : destinationOffset;

        Array.Resize(ref destination, newSize);

        return new string(destination);

    }
    private static int IndexOfLastNonWhithSpaceChar(char[] values, int startIndex)
    {
        if (startIndex >= values.Length) { startIndex = values.Length - 1; }
        for (int i = startIndex; i >= 0; i--)
        {
            if (!Char.IsWhiteSpace(values[i]) && values[i]!='\0')
            {
                return i +1;
            }
        }
        return startIndex;
    }
}

Some numbers

You mentioned in your question that you have measured the performance and provided some numbers, which are unfortunately missing a unit. I couldn't compare them to my numbers so I just measured your method and my method.

For both scenarios each benchmarked method first does a warm-up phase for 5000 ms and then it is called 10000 times and returns the average of StopWatch.ElapsedTicks which is then converted to milliseconds.

  1. Passed in a string with Length of 7368 containing 4124 white space characters.

    Yours: 0,0289723431498079 ms
    Mine: 0,0308240396927017 ms
    Other: 0,110759507042254 ms

  2. Passed in a string with Length of 1591488 containing 890784 white space characters.

    Yours: 6,70626021126761 ms
    Mine: 7,66718351472471 ms
    Other: 42,3948242637644 ms

So, what is Other? It is only taking 42 ms for the second scenario which is IMO fast enough for such a task. It's very simple:

string.Join(" ", str.Split().Where(s => s.Length > 0));
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Your method has some notable properties: (1) It is 0.3 times faster for small words of ≈12 characters. (2) It is 0.6 times slower for words without consecutive whitespace. \$\endgroup\$ – Avenicci Feb 3 '16 at 16:55
  • \$\begingroup\$ That means: Your method is faster in cases where strings are purposely populated with consecutive whitespace, though there are very few real scenarios were such is necessary. \$\endgroup\$ – Avenicci Feb 3 '16 at 16:56
  • \$\begingroup\$ I insist that Seperator was among the best options because the name doesn't attempt to substitute its value, rather it offers a contextually-correct indication. Labels should not carry more significance than their context, that is bad design. \$\endgroup\$ – Avenicci Feb 3 '16 at 16:56
  • \$\begingroup\$ I forgot - IndexOfLastNonWhithSpaceChar throws exceptions upon certain cases of trailing whitespace. \$\endgroup\$ – Avenicci Feb 3 '16 at 17:27
  • \$\begingroup\$ Fixed the IndexOutOfRangeException. \$\endgroup\$ – Heslacher Feb 4 '16 at 6:43
5
\$\begingroup\$

In addition to greybeard's answer here are some tips to improve the design of your code.

  • Naming: Perhaps you should rename your class to specify that it compresses white-space and not all text. It may sound silly but these details can be important when you're pressed for time or are revisiting code 2 weeks to 2 years after you originally wrote it (This same philosophy applies the same to commenting your classes/functions).
  • StringBuilder: Perhaps you should delay the construction of the StringBuilder instance until you call Compress this way you can pass the constructor the length of the string potentially improving performance depending on how long the string is. (StringBuilder starts at a default capacity and simply doubles the capacity each time it is reached. By providing the capacity ahead of time you can prevent this from having to happen. The longer the string the more it will happen).
  • Boolean Variables: I find it extremely helpful to almost always place my boolean conditions into well-named variables. This way I can tell quickly at first glance what the condition is doing without having to read too much into it's specific implementation.

    var isSeparator = str[i] == Seperator;
    if (isSeparator)
    {
        ...
    }
    

For this scenario it's not really necessary but I think it gets my point across.

  • Casing: You seem a bit inconsistent with your casing at the class-level scope. Since you have Seperator capitalized I would suggest builder should also be for consistency. Classes and class-members pascal-cased and local variables should be camel-cased. This way you automatically know if something is restricted to the local-scope or if it's at a higher-scope.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Naming - The name TextCompressor is highly ambiguous, though it was the most sensical name I encountered. \$\endgroup\$ – Avenicci Feb 2 '16 at 18:40
  • \$\begingroup\$ StringBuilder - This benefit only applies for the first string, after that, Compress remains cluttered with a null check. It is better to use StringBuilder.EnsureCapacity, although the benefit is futile in practice. \$\endgroup\$ – Avenicci Feb 2 '16 at 18:40
  • 1
    \$\begingroup\$ Casing - Note that Seperator is a constant field, unlike builder. For constants, pascal case is the most conventional. \$\endgroup\$ – Avenicci Feb 2 '16 at 18:40
  • \$\begingroup\$ @Avenicci Ah, I was mistaken on your usage of Compress for the StringBuilder suggestion. Perhaps this points out how helpful comments can be. \$\endgroup\$ – Shelby115 Feb 2 '16 at 18:48
  • \$\begingroup\$ @Avenicci As for the Casing suggestion, I personally stand by making members Pascal. I looked it up and apparently Microsoft suggests camel-casing for Fields. The way I see it is a choice between more easily noticing the difference between a Property vs Field or more easily noticing Scope differences. In my experiences, the latter is more important to me. \$\endgroup\$ – Shelby115 Feb 2 '16 at 18:50
5
\$\begingroup\$

You present uncommented code: don't expect many to be willing to read it carefully.

Reading absolute best performance, I expected open coded array handling. (I would have been pleased with a model of performance, including assumptions about inputs.)

In Compress(string), there is a for loop - with the loop control variable modified four nesting levels down.

With no tangible specification, to use of both TextCompressor.Seperator and Char.IsWhiteSpace() is confusing.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The loop should rarely enter beyond the first condition. Could you elaborate on 'open coded array handling', does that imply unsafe code? I wouldn't mind leaving that out. \$\endgroup\$ – Avenicci Feb 2 '16 at 16:07
  • \$\begingroup\$ I expected filling a char[] with characters wanted and constructing a string from it (new string(chars, offset, length)), maybe even a str.ToCharArray() to use array indexing instead of "string indexing". \$\endgroup\$ – greybeard Feb 2 '16 at 16:37
  • \$\begingroup\$ Constructing a new string is only necessary upon consecutive whitespace characters, this algorithm behaves accordingly. Iterating char[] is faster than string, but the initial requirement to copy the string disables the benefit. \$\endgroup\$ – Avenicci Feb 2 '16 at 16:48
  • \$\begingroup\$ The first paragraph of the answer should be moved to a comment \$\endgroup\$ – Caridorc Feb 2 '16 at 18:53
  • \$\begingroup\$ The Compress method has no notable assumptions, it doesn't even compulsively optimize the StringBuilder according to the string's length. However, there is one premise: Every encountered sequence of whitespace character must ultimately deem equal to Seperator. Besides, it performs a Trim operation, even if trailing whitespace does not exceed a single instance. \$\endgroup\$ – Avenicci Feb 2 '16 at 19:19
3
\$\begingroup\$

Your Separator constant - this:

private const char Separator = '\x20';

Is really just an obfuscated way of doing this:

private const char WhiteSpace = ' ';

And since the only usage of this Separator is here:

if (str[i] == Seperator)

You could very well replace it with this:

if (Char.IsWhiteSpace(str[i]))

And do away with it completely, and have clearer code.


You're using this to qualify builder. Fine. But please, be consistent about it; the Compress method isn't qualifying it, and builder looks just like any other local variable, but it's a field.

Either you qualify fields with this, or you don't.

And if you don't, then name your fields so that it's impossible to mistake them for a local:

private readonly StringBuilder _builder;

public TextCompressor()
{
    _builder = new StringBuilder();
}

Because the _builder/builder reference isn't reassigned anywhere, it's not clear whether that's the intent. Making the field readonly removes all ambiguity and tells everyone reading the code that this reference lives and dies with the class instance.

You could also initialize it inline, and get rid of the default/parameterless constructor altogether:

private readonly StringBuilder _builder = new StringBuilder();
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You should never assign concrete names to constants. Would you approve a declaration like const A = 'A'? I know, whitespace is a category instead of a unit, but what if you need another whitespace-involving constant in the future? In that case, you could narrow Whitespace to Space, but there lies the mentioned pitfall. \$\endgroup\$ – Avenicci Feb 2 '16 at 18:58
  • \$\begingroup\$ Why do you need that constant at all? - To ensure that the output has consistent breaks (spaces or linebreaks). \$\endgroup\$ – Avenicci Feb 2 '16 at 18:58
  • \$\begingroup\$ this.builder - In overall, I use this consistently, but the embedded code does not contain evidence. I only use this in constructors to ensure that all set operations are well-aligned. It is not uncommon for parameters and fields to share names. \$\endgroup\$ – Avenicci Feb 2 '16 at 18:58
  • \$\begingroup\$ Consistently wrong then. The reason for using this as a qualifier is to improve readability by disambiguating fields from locals and parameters. That said you don't need the constant, as I demonstrated. \$\endgroup\$ – Mathieu Guindon Feb 2 '16 at 19:02
  • \$\begingroup\$ Do you think that alignment does not enhance readability? I cannot argue with that. And yes, if consistent line breaks are desirable, than an extra field is necessary, be it constant or static. \$\endgroup\$ – Avenicci Feb 2 '16 at 19:06

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.