2
\$\begingroup\$

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.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ Do you really need this ouput? source.Max() is a much simpler alternative. Because your algorithm seems to work only for functions with two arguments. \$\endgroup\$ Feb 12, 2016 at 15:12
  • \$\begingroup\$ I really need it becuase I'm writing my own implementation of Max() method which is now working ~10 times faster than origional one. But I want to reduce code generation time. \$\endgroup\$ Feb 12, 2016 at 16:05

1 Answer 1

3
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ I would consider using StringBuilder instead of multiple + concatenations to further help improve performance \$\endgroup\$
    – dreza
    Feb 12, 2016 at 18:22
  • \$\begingroup\$ @dreza Thanks for the suggestion. I was thinking it would be a little more trouble than what it really was. \$\endgroup\$ Feb 12, 2016 at 19:13
  • \$\begingroup\$ Yeah I guess it might be, but it performance is an issue it might shave a few more seconds. See stackoverflow.com/questions/73883/string-vs-stringbuilder \$\endgroup\$
    – dreza
    Feb 12, 2016 at 20:22
  • \$\begingroup\$ @dreza Don't get me wrong, I updated my answer according to it. \$\endgroup\$ Feb 12, 2016 at 20:26
  • \$\begingroup\$ Thanks for improvment, but I really think that string concatenation is not a primary issue here. Anyway, 50% is good anyway. But we know that exp(x) and 1/2exp(x) is the same, because constant is not applyed by O(N) notation, and exponential algorithm growing is the real problem here. \$\endgroup\$ Feb 12, 2016 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.