Expanding a string to a certain length

Question

I wrote a function for repeating a string to a certain length.

For example:

ExpandString("Test", 11); 
// output: "TestTestTes"

Are there any optimizations or fixes that can be done to this function?

private string ExpandString(string str, int length)
{
 if (length <= str.Length) return str.Substring(0, length);
 var result = str;
 for (var i = str.Length; i < length; i++)
 {
 result += str[i % str.Length];
 }
 return result;
}

• Franck: Can be sone by simply expanding on enumerable 1 step further and taking a substring for the amount needed like so : return string.IsNullOrEmpty(str) ? "".PadLeft(length,' ') : string.Join("", Enumerable.Repeat(str, (int)Math.Ceiling((double)length / (double)str.Length)).ToArray()).Substring(0, length);
• KeyBored: @Franck Thanks, but the performance won't be better than any of the suggested answers. it'll be good only for one-liner functions fans. (btw, I'm one of them sometimes :))
• Nimesh: what would you do if you want to expand string to longer than Int type. say Long type? e.g. ExpandString(string str, long length)
• Simon Forsberg: @Nimesh The maximum of an int is 2147483647. i.e. 2.1 billion characters. Should be enough for everyone. If you have that big strings with repeating characters, then you should likely refactor the code to use input/output streams instead.

Answer 1

Instead of adding a character at a time, double the string as long as you can without making it too long, then just add the rest of the characters:

private static string ExpandString(string str, int length) {
 if (length <= str.Length) return str.Substring(0, length);
 while (str.Length * 2 <= length) {
 str += str;
 }
 if (str.Length < length) {
 str += str.Substring(0, length - str.Length);
 }
 return str;
}

You don't need a StringBuilder for this. This method is actually almost twice as fast as using a StringBuilder.

Here is the result for a test run of calling ExpandString("Test", 100) 100000 times each, for the orginal method, the method suggested by cHao, and the method suggested above:

Original: 00:00:00.5795951
StringBuilder: 00:00:00.0372573
This: 00:00:00.0204482

• KeyBored: I can see that your function is slightly faster than cHao's. But how come I don't need a StringBuilder here? At least the StringBuilder will reserve the required memory space beforehand which your code doesn't.. Would you elaborate, please
• Guffa: @KeyBored: You don't need a StringBuilder because doubling the string makes it grow very quickly. The StringBuilder is slower because it still does a lot of appends, it needs 25 appends to create a 100 character string from a 4 character string. Doubling the string only needs to do 5 string concatenations. Even if the StringBuilder.Append and String.Concat calls the same method to copy the characters (wstrcpy), the overhead before it gets to that call costs just as much, so the number of calls makes the difference. With longer strings the difference is even bigger.
• cHao: Spiffy. :) If you do this in the real world, though, i'd definitely suggest a comment or two explaining the idea.
• KeyBored: @Guffa Expanding the string exponentially is a clever trick, but can I also allocate the required memory in advance as suggested in the other answers? I've tried using a StringBuilder with your code (means Append function will be called 4 times only for ExpandString("Test", 100)) but it is still slower than your function. Also allocating the memory using a new char[length] as suggested by @Bjørn works perfectly with your code and gives the best performance yet, but I'm not sure if this is the best way to go.
• KeyBored: see the functions and test results here: ideone.com/KanNgz

Answer 2

OK, first, for the most straightforward optimization. Use a StringBuilder.

The way your code currently works, it creates length - str.Length intermediate strings. Besides creating lots of unnecessary garbage, you're copying longer and longer strings over and over again to add one character each time.

If you use a StringBuilder instead, you can avoid most of those copies. You could try something like...

using System.Text;
...
private string ExpandString(string str, int length)
{
 if (length <= str.Length) return str.Substring(0, length);
 var result = new StringBuilder(str);
 for (var i = str.Length; i < length; i++)
 {
 result.Append(str[i % str.Length]);
 }
 return result.ToString();
}

(I don't particularly like the StringBuilder starting with a copy of str already in it. I'm literally just replacing the String.)

But you're also copying one character at a time. While this isn't as big an issue as the concatenation, you can do better by inserting as many whole copies of str as you can.

private string ExpandString(string str, int length)
{
 // BTW, you already know how big the result should be, so just
 // tell the StringBuilder its capacity to prevent unneeded resizes.
 // Side benefit: if the result is too long, you'll find out fairly quickly.
 var result = new StringBuilder(length, length);
 var wholeCopies = length / str.Length;
 for (var i = 0; i < wholeCopies; ++i)
 {
 result.Append(str);
 }
 // now append the last chunk, a possibly-zero-length prefix of `str`
 result.Append(str, 0, length % str.Length);
 return result.ToString();
}

Note that the short-string optimization has been removed. You can add it back in if you really really want to micro-optimize, but at this point, it's not gaining you nearly as much as it was.

• 200_success: I wouldn't bother with the str.Substring() special cases anymore.
• cHao: @200_success: Agreed. I still might get rid of it. But i did want to make sure its benefit (or rather, relative lack thereof) was addressed, rather than having someone think i just forgot it. :)

Answer 3

I will not repeat what's been said in cHao's review, but I would like to share an alternative approach.

First, we know the length of the return string, so we create a char array which we'll pass to the (Char[]) string constructor in the return statement.

var chars = new Char[length];

Next, populate the array by using the modulus operator to "translate" the chars index (the length variable in the example below) to correct str index.

while (length > 0)
{
 length--;
 chars[length] = str[(length % str.Length)];
}

Finally, return a new string.

return new String(chars);

---

Here's how the method should look like if placed in an extension class:

public static String Expand(this String value, Int32 length)
{
 if (value == null)
 {
 throw new ArgumentNullException("value");
 }
 else if (length < 0)
 {
 throw new ArgumentOutOfRangeException("length");
 }
 var chars = new Char[length];
 for (Int32 index = 0; (index < length); index++)
 {
 chars[index] = value[(index % value.Length)];
 }
 return new String(chars);
}

• KeyBored: Thanks alot.. but cHao answer gives better performance as it copies the string in chunks and avoids the letter-by-letter index calc
• Rick Davin: @KeyBored How do you know this was slower than StringBuilder? Did you try it with performance tests? Although generally its up to the person offering the answer to provide such timings as a way to bolster support for their answer.