2
\$\begingroup\$

This is the original question: https://www.geeksforgeeks.org/run-length-encoding/

Given an input string, write a function that returns the Run Length Encoded string for the input string.
For example, if the input string is “wwwwaaadexxxxxx”, then the function should return “w4a3d1e1x6”.

the only change I did is that if the character appears once there is no need to print 1 after the letter.

Please review for perfomance

using System;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace StringQuestions
{
    /// <summary>
    /// https://www.geeksforgeeks.org/run-length-encoding/
    /// </summary>
    [TestClass]
    public class RunLengthEncoding
    {
        [TestMethod]
        public void RunLengthEncodingTest()
        {
            string str = "wwwwaaadexxxxxxywww";
            string expected = "w4a3dex6yw3";
            Assert.AreEqual(expected, RLE.Encode(str));
        }
    }

    public class RLE
    {
        public static string Encode(string str)
        {
            str = str.ToLower();
            StringBuilder stringBuilder = new StringBuilder();

            for (int i = 0; i < str.Length; i++)
            {
                int counter = 1;
                if (!char.IsLetter(str[i]))
                {
                    throw new ArgumentException("string should contains only letters");
                }

                while (i < str.Length - 1 && str[i] == str[i + 1])
                {
                    counter++;
                    i++;
                }

                if (counter == 1)
                {
                    stringBuilder.Append(str[i]);
                }
                else
                {
                    stringBuilder.Append(str[i]);
                    stringBuilder.Append(counter);
                }
            }

            return stringBuilder.ToString();
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ What is Test class and Test Method? \$\endgroup\$ – Shad Jul 4 at 15:55
  • \$\begingroup\$ @Shad this is ms test attribute for unit testing. Read about those if you do not know what they are \$\endgroup\$ – Gilad Jul 4 at 21:55
3
\$\begingroup\$

One thing I noticed. You're modifying the loop counter inside the loop to run another loop. This is one way in a large project to create unseen bugs. By keeping track of the previous character it is fairly easy to code this with only one loop.

Your trapping strings that have other characters besides letters, but you're neglecting empty strings and null.

Here's one way the revised code can look:

static string Encode(string input)
{
    if (input == null || input.Length == 0)
    {
        ArgErrHandler("String must have at least one letter.");
    }
    if (input.Any(x => !char.IsLetter(x)))
    {
        ArgErrHandler("String must have only letters.");
    }
    if (input.Length == 2 || input.Length == 1)
    {
        return (input.Length == 1 || input[0] != input[1]) ? input : $"{input[0]}{2}";
    }
    int limit = input.Length - 1;
    int counter = 1;
    StringBuilder sb = new StringBuilder();
    int i = 1;
    char prev = '\0';
    do
    {

        prev = input[i - 1];
        if (input[i] == prev)
        {
            ++counter;
        }
        else
        {
            if (counter > 1)
            {
                sb.Append($"{prev}{counter}");
            }
            else
            {
                sb.Append(prev);
            }
            prev = input[i];
            counter = 1;
        }
    } while (++i < limit);
    if (input[i] == prev)
    {
        ++counter;
        sb.Append($"{prev}{counter}");
    }
    else
    {
        if (counter > 1)
        {
            sb.Append($"{prev}{counter}{input[i]}");
        }
        else
        {
            sb.Append($"{prev}{input[i]}");
        }
    }
    return $"{sb}";
}
private static void ArgErrHandler(string message)
{
    throw new ArgumentException(message);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ It looks like this fails if there is a single character input - the do loop is always executed and input[1] gives an out of range exception - and for a two character input the post loop check looks for input[2] which gives an out of range exception. \$\endgroup\$ – AlanT Jul 4 at 9:12
  • \$\begingroup\$ Thanks you guys \$\endgroup\$ – Gilad Jul 4 at 12:51
  • \$\begingroup\$ @AlanT - It's fixed \$\endgroup\$ – tinstaafl Jul 4 at 22:44
2
\$\begingroup\$

Looking at the original question is seems that the input is constrained to be lower case letters. If this is so, then the str.Lower() is unneeded. Even if we decide that we do want to covert to lower, doing it upfront for the whole string means an extra traversal; it can be done as we process.

It is possible to do this in a single loop without the inner while and its checks if we append a sentinel onto the end of the input. I don't know that it saves much on performance but it does cut out a few checks

public string Encode(string input)
{
    if (input == null || input.Length == 0)
    {
        throw new ArgumentException("String must have at least one letter.");
    }

    int counter = 0;
    StringBuilder sb = new StringBuilder();
    char prev = char.ToLower(input[0]);

    foreach(var rawChar in input.Append('\0').Skip(1))
    {
        var ch = char.ToLower(rawChar);
        counter++;
        if (ch == prev) continue;

        if(!char.IsLetter(prev))
        { 
            throw new ArgumentException("string should contains only letters");
        }
        sb.Append($"{prev}{(counter > 1 ? counter.ToString() : "")}");
        counter = 0;
        prev = ch;
    }
    return sb.ToString();
}

Note: Enumerable.Append() is 4.7.1 and above.

EDIT
Revised linq-less version. Sill uses the sentinel but 'injects' it when we get to the end of the loop

public string Encode(string input)
{
    if (input == null || input.Length == 0)
    {
        throw new ArgumentException("String must have at least one letter.");
    }

    int counter = 0;
    StringBuilder sb = new StringBuilder();
    char prev = char.ToLower(input[0]);

    for(var index = 1; index <=input.Length; index++)
    {
        var ch = index == input.Length
                      ? '\0'
                      : char.ToLower(input[index]);
        counter++;
        if (ch == prev) continue;

        if (!char.IsLetter(prev))
        {
            throw new ArgumentException("string should contains only letters");
        }
        if (counter == 1)
        {
            sb.Append(prev);
        }
        else
        {
            sb.Append(prev);
            sb.Append(counter);
        }
        counter = 0;
        prev = ch;
    }

    return sb.ToString();

}

UPDATE

So I ran some numbers on this

The options were

  1. Sentinel or not
  2. Linq or not
  3. Append count separately or use string interpolation
  4. convert to lower up front or per character

I tried 3 different inputs

  • 1000 copies of the sample string (wwwwaaadexxxxxx)
  • 1000 copies of the sample string x 4 (wwwwaaadexxxxxxwwwwaaadexxxxxxwwwwaaadexxxxxxwwwwaaadexxxxxx)
  • 1000 random strings or lengths between 10 and 250

I ran each dataset 10 times and averaged the results (discarding the first each time as it was generally an outlier - startup costs?)

Results

1000 Copies of wwwwaaadexxxxxx

Original => 10,239 ticks
Original PerChar Lower => 20,725 ticks
Original String Interpolation => 22,309 ticks

Sentinel Linq PerChar Lower Interpolation => 19,409 ticks
Sentinel Linq PerChar Lower Append => 12,350 ticks
Sentinel Linq str Lower Append => 8,860 ticks

Sentinel NoLinq PerChar Lower Interpolation => 20,284 ticks
Sentinel NoLinq PerChar Lower Append => 8,702 ticks
Sentinel NoLinq Str Lower Append => 5,786 ticks

1000 Copies of wwwwaaadexxxxxxwwwwaaadexxxxxxwwwwaaadexxxxxxwwwwaaadexxxxxx

Original => 28,064 ticks
Original PerChar Lower => 53,718 ticks
Original String Interpolation => 44,618 ticks

Sentinel Linq PerChar Lower Interpolation => 80,699 ticks
Sentinel Linq PerChar Lower Append => 41,440 ticks
Sentinel Linq str Lower Append => 35,716 ticks

Sentinel NoLinq PerChar Lower Interpolation => 59,850 ticks
Sentinel NoLinq PerChar Lower Append => 35,956 ticks
Sentinel NoLinq Str Lower Append => 20,038 ticks

1000 random strings or lengths between 10 and 250

Original => 60,350 ticks
Original PerChar Lower => 146,490 ticks
Original String Interpolation => 170,631 ticks

Sentinel Linq PerChar Lower Interpolation => 221,283 ticks
Sentinel Linq PerChar Lower Append => 79,732 ticks
Sentinel Linq str Lower Append => 42,773 ticks

Sentinel NoLinq PerChar Lower Interpolation => 197,249 ticks
Sentinel NoLinq PerChar Lower Append => 64,996 ticks
Sentinel NoLinq Str Lower Append => 30,775 ticks

Interpretation

Firstly, string interpolation bad, it looks cute (a Matter of Personal Preference MOPP(tm)) but is not performant.

Secondly, and surprisingly to me, upfront conversion of the whole string ToLower() is better than character by character. For the original code this is not a surprise as there are a lot of repeated conversions needed but even in the Sentinel version where we only convert each character once, it is better to convert the string upfront and then process it.

Thirdly, linq performance varied. The sentinel version using linq was never better than the no linq version but sometimes it was better than the original code, sometimes it wasn't (this was not data related as I repeated the same dataset multiple times and sometimes it was faster, sometimes slower)

Bottomline

Pretty much everything in my original answer was wrong (well, except for the concept of the sentinel)
When answering performance questions it is important to run the numbers :)

public string Sentinel_NoLinqStrLowerAppend(string input)
{
    if (input == null || input.Length == 0)
    {
        throw new ArgumentException("String must have at least one letter.");
    }

    input = input.ToLower();

    int counter = 0;
    StringBuilder sb = new StringBuilder();
    char prev = input[0];

    for (var index = 1; index <= input.Length; index++)
    {
        var ch = index == input.Length
                      ? '\0'
                      : input[index];
        counter++;
        if (ch == prev) continue;

        if (!char.IsLetter(prev))
        {
            throw new ArgumentException("string should contains only letters");
        }
        if (counter == 1)
        {
            sb.Append(prev);
        }
        else
        {
            sb.Append(prev);
            sb.Append(counter);
        }
        counter = 0;
        prev = ch;
    }

    return sb.ToString();

}
\$\endgroup\$
  • \$\begingroup\$ Actually, Append, char.ToLower and $"{prev}{...}" each add some overhead, making this roughly 2-3 times slower. \$\endgroup\$ – Pieter Witvoet Jul 4 at 12:55
  • \$\begingroup\$ @Pieter Witvoet char.ToLower() per character is slower than str.ToLower() and then processing? Not disagreeing, I haven't run any performance tests, but just curious as to why. Is it cheaper to create a new lower case version of the string than to lowercase the characters individually? \$\endgroup\$ – AlanT Jul 4 at 13:15
  • \$\begingroup\$ I don't know, but I guess it's the additional checks that char.ToLower does, together with the repeated call overhead. \$\endgroup\$ – Pieter Witvoet Jul 4 at 21:01

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.