Need to make my recursive function work faster

Question

This is the code that is causing me "problems":

private string buildHTMLTree()
{
    Dictionary<string, string> parents = new Dictionary<string, string>();
    Dictionary<string, string> childs = new Dictionary<string, string>();
    ArrayList array = new ArrayList();
    array = simulateInput();

    string html = "";

    foreach (KeywordRows kwd in array)
    {
        if (kwd.root_keyword == kwd.keyword)
        {
            if (!parents.ContainsKey(kwd.keyword))
                parents.Add(kwd.keyword, kwd.root_keyword);
        }
        else
        {
            if (!childs.ContainsKey(kwd.keyword))
                childs.Add(kwd.keyword, kwd.root_keyword);
        }
    }

    html += "<ul id=\"parents\">";
    foreach (string parent in parents.Values)
    {
        html += "<li id=\"" + parent + "\">" + parent;

        if (childs.ContainsValue(parent))
        {
            html += "<ul id=\"parents\">";
            process(ref childs, ref html, parent);
            html += "</ul>";
        }

        html += "</li>";
    }
    html += "</ul>";

    return Properties.Resources.htmlTree_tmpl.Replace("{KEYWORDS}", html);
}

public void process(ref Dictionary<string, string> _childs, ref string _html, string parent)
{
    var getChilds =
    from o in _childs
    where (o.Value == parent)
    select o.Key;

    foreach (var tmp in getChilds)
    {
        string child = tmp.ToString();

        if (_childs.ContainsValue(child))
        {
            _html += "<li id=\"" + child + "\">" + child + "<ul id=\"" + child + "\">";
            process(ref _childs, ref _html, child);
            _html += "</ul></li>";
        }
        else
        {
            _html += "<li id=\"" + child + "\">" + child + "</li>";
        }
    }

    return;
}

public class KeywordRows
{
    private string _keyword;
    private string _root_keyword;

    public KeywordRows(string keyword, string root_keyword)
    {
        _keyword = keyword;
        _root_keyword = root_keyword;
    }

    public string keyword
    {
        get
        {
            return _keyword;
        }
        set
        {
            _keyword = value;
        }
    }

    public string root_keyword
    {
        get
        {
            return _root_keyword;
        }
        set
        {
            _root_keyword = value;
        }
    }
}

}

My problem is that I have this function I use to turn a 2 columns list of data to a nested html tree, the problem is that when this data contains a lot of "rows", the function takes forever to finish, I didn't got any exception but I let it ran with a 100k rows data as input for like 15 minutes and it didn't finished.

I've put together a small Visual Studio 2010 project to show the problem, it simulates an input of X size and executes the function.

Here's the project: http://www.fileden.com/files/2011/4/10/3112563//HTMLTreeTest.zip

What can I do to do my code (much) faster?

Don't use recursion. Anything that can be modeled recursively can be done with iteration. Recursion performance is almost universally poor in non-functional languages. — Rafe Kettler, Apr 10 '11 at 04:18
Sure, we can keep guessing all day at what the problem may be. Or, the OP can profile the app and be certain what the problem actually is. — Esteban Araya, Apr 10 '11 at 05:09
@Esteban: I would use the [pause technique](http://stackoverflow.com/questions/375913/what-can-i-use-to-profile-c-code-in-linux/378024#378024), as an alternative to profiling, but you're absolutely right. We are all only too willing to make educated guesses, which are still only guesses. — Mike Dunlavey, Apr 11 '11 at 16:44

Kobi · Accepted Answer · 2011-04-10T05:03:23.767

The posted code is likely to be slow due to string concatenation. Use a StringBuilder instead, or the more specialized HtmlTextWriter.
Here's your code with a StringBuilder, which works in saner time:
http://pastebin.com/0VrM6SLV

You may also consider writing directly to your StreamWriter - this avoids having the whole string in memory at once, which is a good idea for a very large string. The code is very similar to using the StringBuilder. We pass strWri, and use StreamWriter.Write:
http://pastebin.com/5afYdWHM
Note that I had to split your template string (the HTML wrapper) to make it work logically - we can't use String.Replace if we aren't dealing with a whole string.

Need to make my recursive function work faster

1 Answers1