Recursive function application

Question

I use a lot T4 templates and want to avoid extra code writing when it could be generated. Currently I have following class:

class Recursion
{
    private readonly string _function;
    private readonly Func<int, string> _appFunc;

    public Recursion(string function, Func<int, string> appFunc)
    {
        _function = function;
        _appFunc = appFunc;
    }

    public string Apply(int n)
    {
        return Apply(0, n);
    }

    private string Apply(int k, int n)
    {
        var diff = n - k;
        if (diff == 0)
            return "0";
        if (diff == 1)
            return _appFunc(k);
        if (diff == 2)
            return string.Format("{0}({1}, {2})", _function, _appFunc(k), _appFunc(k + 1));
        int half = (n + k) / 2;
        return string.Format("{0}({1}, {2})", _function, Apply(k, half), Apply(half, n));
    }
}

Example of usage:

var rec = new Recursion("Math.Max", i => string.Format("source[{0}]", i));
Console.WriteLine(rec.Apply(8));

output:

Math.Max(Math.Max(Math.Max(source[0], source[1]), Math.Max(source[2], source[3])), Math.Max(Math.Max(source[4], source[5]), Math.Max(source[6], source[7])))

It works fine but for large files generation takes a lot of time (even when N is small). I can't use it for larger N (now I'm using N = 4 and generation takes 5+ seconds, i expect that for 8 and more it would take hours).

I want to get this output, but with smaller cost, if possible, possibly with a different algorithm.

Answer 1

Consider using the string concatenation operator + instead. The reason why this works and is not bad is because behind the scenes the method String.Concat is being called.

While String.Format will have to do a lot of different things, such as parsing, getting the string after and before placeholders to be able to join them and so on.

This is important both on the callback and implementation.

private string Apply(int k, int n)
{
    var diff = n - k;
    if (diff == 0)
        return "0";
    if (diff == 1)
        return _appFunc(k);
    if (diff == 2)
        return _function + "(" + _appFunc(k) + ", " + _appFunc(k + 1) + ")";
    int half = (n + k) / 2;
    return _function + "(" + ApplyB(k, half) + ", " + ApplyB(half, n) + ")";
}

var rec = new Recursion("Math.Max", i => "source[" + i + "]");

By applying this changes I could measure a 0.5s difference on my machine over 60000 iterations calling apply with 8 which previously took 3s so it was a 17% improvement.

Going with StringBuilder

I was a bit reluctant going with a StringBuilder because it seemed an hard job but when we think two more times about it solutions come. My idea was to put a StringBuilder on a field, so I don't have to pass it has a parameter to the function, and make the method return void.

The StringBuilder is the ideal class to build large strings, it is efficient because it manages an array of characters. It's like having mutable strings.

    class Recursion
    {
        private readonly string _function;
        private readonly Func<int, string> _appFunc;
        private readonly StringBuilder _builder;
        public Recursion(string function, Func<int, string> appFunc)
        {
            _function = function;
            _appFunc = appFunc;
            _builder = new StringBuilder();
        }
        public string Apply(int n)
        {
            Apply(0, n);
            var result = _builder.ToString();
            _builder.Clear();
            return result;
        }

        private void Apply(int k, int n)
        {
            var diff = n - k;
            if (diff == 0)
            {
                _builder.Append("0");
                return;
            }
            if (diff == 1)
            {
                _builder.Append(_appFunc(k));
                return;
            }
            if (diff == 2)
            {
                _builder.Append(_function)
                .Append('(')
                .Append(_appFunc(k))
                .Append(", ")
                .Append(_appFunc(k + 1))
                .Append(')');
                return;
            }
            int half = (n + k) / 2;
            _builder.Append(_function).Append('(');
            Apply(k, half);
            _builder.Append(", ");
            Apply(half, n);
            _builder.Append(')');
        }
    }

This decreased execution 0.9s upon my previous attempt, on the same circumstances, giving it a total of 46% improvement.