Consecutive whitespace reduction

Question

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

Answer 1

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));

Answer 2

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.

Answer 3

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.

Answer 4

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();

Answer 5

This looks like a bug:

    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]))

That str[i+1] can be out of range, on the last iteration of the loop.