2
\$\begingroup\$

Well, I'm trying to generate the following:

Input:

Level1a/Level2a/Level3a/Level4a
Level1a/Level2a/Level3a/Level4b
Level1a/Level2a/Level3a/Level4c
Level1a/Level2a/Level3b/Level4a
Level1a/Level2a/Level3b/Level4b
Level1a/Level2a/Level3b/Level4c
Level1a/Level2a/Level3c/Level4a
Level1a/Level2a/Level3c/Level4b
Level1a/Level2a/Level3c/Level4c
Level1a/Level2b/Level3a/Level4a
Level1a/Level2b/Level3a/Level4b
Level1a/Level2b/Level3a/Level4c
Level1a/Level2b/Level3b/Level4a
Level1a/Level2b/Level3b/Level4b
Level1a/Level2b/Level3b/Level4c
Level1a/Level2b/Level3c/Level4a
Level1a/Level2b/Level3c/Level4b
Level1a/Level2b/Level3c/Level4c
Level1a/Level2c/Level3a/Level4a
Level1a/Level2c/Level3a/Level4b
Level1a/Level2c/Level3a/Level4c
Level1a/Level2c/Level3b/Level4a
Level1a/Level2c/Level3b/Level4b
Level1a/Level2c/Level3b/Level4c
Level1a/Level2c/Level3c/Level4a
Level1a/Level2c/Level3c/Level4b
Level1a/Level2c/Level3c/Level4c
Level1b/Level2a/Level3a/Level4a
Level1b/Level2a/Level3a/Level4b
Level1b/Level2a/Level3a/Level4c
Level1b/Level2a/Level3b/Level4a
Level1b/Level2a/Level3b/Level4b
Level1b/Level2a/Level3b/Level4c
Level1b/Level2a/Level3c/Level4a
Level1b/Level2a/Level3c/Level4b
Level1b/Level2a/Level3c/Level4c
Level1b/Level2b/Level3a/Level4a
Level1b/Level2b/Level3a/Level4b
Level1b/Level2b/Level3a/Level4c
Level1b/Level2b/Level3b/Level4a
Level1b/Level2b/Level3b/Level4b
Level1b/Level2b/Level3b/Level4c
Level1b/Level2b/Level3c/Level4a
Level1b/Level2b/Level3c/Level4b
Level1b/Level2b/Level3c/Level4c
Level1b/Level2c/Level3a/Level4a
Level1b/Level2c/Level3a/Level4b
Level1b/Level2c/Level3a/Level4c
Level1b/Level2c/Level3b/Level4a
Level1b/Level2c/Level3b/Level4b
Level1b/Level2c/Level3b/Level4c
Level1b/Level2c/Level3c/Level4a
Level1b/Level2c/Level3c/Level4b
Level1b/Level2c/Level3c/Level4c
Level1c/Level2a/Level3a/Level4a
Level1c/Level2a/Level3a/Level4b
Level1c/Level2a/Level3a/Level4c
Level1c/Level2a/Level3b/Level4a
Level1c/Level2a/Level3b/Level4b
Level1c/Level2a/Level3b/Level4c
Level1c/Level2a/Level3c/Level4a
Level1c/Level2a/Level3c/Level4b
Level1c/Level2a/Level3c/Level4c
Level1c/Level2b/Level3a/Level4a
Level1c/Level2b/Level3a/Level4b
Level1c/Level2b/Level3a/Level4c
Level1c/Level2b/Level3b/Level4a
Level1c/Level2b/Level3b/Level4b
Level1c/Level2b/Level3b/Level4c
Level1c/Level2b/Level3c/Level4a
Level1c/Level2b/Level3c/Level4b
Level1c/Level2b/Level3c/Level4c
Level1c/Level2c/Level3a/Level4a
Level1c/Level2c/Level3a/Level4b
Level1c/Level2c/Level3a/Level4c
Level1c/Level2c/Level3b/Level4a
Level1c/Level2c/Level3b/Level4b
Level1c/Level2c/Level3b/Level4c
Level1c/Level2c/Level3c/Level4a
Level1c/Level2c/Level3c/Level4b
Level1c/Level2c/Level3c/Level4c

Output:

public static class Level1a
{
    public static class Level2a
    {
        public static class Level3a
        {
            public static string Level4a = "1488761881";
            public static string Level4b = "193501299";
            public static string Level4c = "1176619638";    
        }

        public static class Level3b
        {
            public static string Level4a = "1399332350";
            public static string Level4b = "2052111229";
            public static string Level4c = "890332317";    
        }

        public static class Level3c
        {
            public static string Level4a = "1532225081";
            public static string Level4b = "573356654";
            public static string Level4c = "2062588997";    
        }    
    }

    public static class Level2b
    {
        public static class Level3a
        {
            public static string Level4a = "1529741837";
            public static string Level4b = "222585494";
            public static string Level4c = "891285919";   
        }

        public static class Level3b
        {
            public static string Level4a = "390696166";
            public static string Level4b = "594192298";
            public static string Level4c = "1083220943";    
        }

        public static class Level3c
        {
            public static string Level4a = "702598359";
            public static string Level4b = "722402607";
            public static string Level4c = "1405833999";    
        }    
    }

    public static class Level2c
    {
        public static class Level3a
        {
            public static string Level4a = "2048595403";
            public static string Level4b = "58370073";
            public static string Level4c = "524601020";    
        }

        public static class Level3b
        {
            public static string Level4a = "980100293";
            public static string Level4b = "207581761";
            public static string Level4c = "1504264127";   
        }

        public static class Level3c
        {
            public static string Level4a = "1572666752";
            public static string Level4b = "643931200";
            public static string Level4c = "1591869757";    
        }    
    }  
}

public static class Level1b
{
    public static class Level2a
    {
        public static class Level3a
        {
            public static string Level4a = "347647206";
            public static string Level4b = "1229370062";
            public static string Level4c = "2009415733";    
        }

        public static class Level3b
        {
            public static string Level4a = "1676726159";
            public static string Level4b = "1215950520";
            public static string Level4c = "524327104";    
        }

        public static class Level3c
        {
            public static string Level4a = "1167245618";
            public static string Level4b = "1439144914";
            public static string Level4c = "132046132";    
        }       
    }

    public static class Level2b
    {
        public static class Level3a
        {
            public static string Level4a = "226999070";
            public static string Level4b = "1279391946";
            public static string Level4c = "192015774";    
        }

        public static class Level3b
        {
            public static string Level4a = "1312893735";
            public static string Level4b = "1056858701";
            public static string Level4c = "1619871324";    
        }

        public static class Level3c
        {
            public static string Level4a = "167695140";
            public static string Level4b = "1184979870";
            public static string Level4c = "802335777";    
        }   
    }

    public static class Level2c
    {
        public static class Level3a
        {
            public static string Level4a = "620553654";
            public static string Level4b = "539272091";
            public static string Level4c = "877305211";   
        }

        public static class Level3b
        {
            public static string Level4a = "868125815";
            public static string Level4b = "687971845";
            public static string Level4c = "1271690402";    
        }

        public static class Level3c
        {
            public static string Level4a = "2002666349";
            public static string Level4b = "543891764";
            public static string Level4c = "531171485";   
        }   
    }   
}

public static class Level1c
{
    public static class Level2a
    {
        public static class Level3a
        {
            public static string Level4a = "1037815829";
            public static string Level4b = "508661588";
            public static string Level4c = "2133403185";   
        }

        public static class Level3b
        {
            public static string Level4a = "1819839158";
            public static string Level4b = "1974149245";
            public static string Level4c = "1408180029";    
        }

        public static class Level3c
        {
            public static string Level4a = "1445946207";
            public static string Level4b = "1184577875";
            public static string Level4c = "1491470239";   
        }    
    }

    public static class Level2b
    {
        public static class Level3a
        {
            public static string Level4a = "53173264";
            public static string Level4b = "2000499325";
            public static string Level4c = "1154118621";   
        }

        public static class Level3b
        {
            public static string Level4a = "366958815";
            public static string Level4b = "1370934195";
            public static string Level4c = "1302531031";    
        }

        public static class Level3c
        {
            public static string Level4a = "951174811";
            public static string Level4b = "475599289";
            public static string Level4c = "1590494308";    
        }    
    }

    public static class Level2c
    {
        public static class Level3a
        {
            public static string Level4a = "1213818225";
            public static string Level4b = "735701668";
            public static string Level4c = "1148995019";    
        }

        public static class Level3b
        {
            public static string Level4a = "1052213343";
            public static string Level4b = "812405153";
            public static string Level4c = "1170085538";    
        }

        public static class Level3c
        {
            public static string Level4a = "701928350";
            public static string Level4b = "952113098";
            public static string Level4c = "104659109";    
        }        
    }        
}

Actually, it works (as the rules marks), but I need to optimize it.

I'm using the following fiddle: https://dotnetfiddle.net/zhtHbe

And to generate this actually uses almost 10Mb of RAM...

This is my code (you can use my Fiddle to experiment):

const bool debug = false;
private static IEnumerable<RecursiveNode> RecursiveSplitting(IEnumerable<string> arrs, string currentParent = "", string splitChar = "/", bool nestedDebug = false)
{
    if(!string.IsNullOrEmpty(Separator))
        splitChar = Separator;

    UsedSeparator = splitChar;

    var _arrs = debug && !nestedDebug ? arrs.Where(a => a.Contains("Comix/")) : arrs;

    if(debug)
        nestedDebug = true;

    // bool wasFirstIteration = false;
    /*if(firstIteration) {
        wasFirstIteration = true;
        firstIteration = false;
    }*/

    string lastHandle = "";
    foreach (var item in _arrs)
    {
        if (string.IsNullOrEmpty(item))
            // yield break;
            continue;

        string parent = string.IsNullOrEmpty(currentParent) && item.Contains(splitChar) ? item.Substring(0, item.LastIndexOf(splitChar)) : currentParent;

        if(!item.Contains(splitChar)) {
            yield return new RecursiveNode(item, parent);
            // yield break;
            continue;

            // throw new Exception("Nothing to split!");
        }

        var splitted = item.Split(splitChar.ToCharArray());

        if (lastHandle == splitted[0])
            // yield break;
            continue;

        lastHandle = splitted[0];

        var node = new RecursiveNode(lastHandle, parent);

        var subItems = arrs.Where(i => i.StartsWith(splitted[0] + splitChar) && i.Contains(splitChar))
                           .Select(i => i.Replace(splitted[0] + splitChar, string.Empty));

        // if(debug)
            Console.WriteLine("[Item={0}, SubItem Count={1}]", item, subItems.Count());

        // if(subItems.Count() == 0)
        //  continue;

        // Console.WriteLine(subItems.Count());

        if (splitted.Length == 1)
        {
            yield return new RecursiveNode(splitted[0], parent);
            // yield break;
            continue;
        }

        var subNodes = RecursiveSplitting(subItems, parent, splitChar, nestedDebug);
        node.Childs.AddRange(subNodes);

        yield return node;
    }
}

private static string OutputRecursiveNode(IEnumerable<RecursiveNode> nodes, Func<string, string> getFieldValue, int count = -1)
{
    var sb = new StringBuilder();

    ++count;

    foreach (var node in nodes)
    {
        string indenter = new string('\t', count);

        var @class = indenter + GenerateClass(node.Value).Replace(Environment.NewLine, Environment.NewLine + indenter);

        if (node.Childs.Count > 0)
        {
            sb.AppendLine(@class);
            sb.AppendLine(OutputRecursiveNode(node.Childs, getFieldValue, count));

            if (!string.IsNullOrEmpty(@class))
                sb.AppendLine(indenter + "}");

            sb.AppendLine();
        }
        else
        {
            string field = GenerateField(node.Value, getFieldValue(node.CurrentParent + UsedSeparator + node.Value));
            sb.AppendLine(indenter + field);
        }
    }

    return sb.ToString();
}

private static string GenerateClass(string name)
{
    if (string.IsNullOrEmpty(name))
        return string.Empty;

    return string.Format("public static class {0}{1}{{", name, Environment.NewLine);
    // return $@"public static class {name}{Environment.NewLine}{{";
}

private static string GenerateField(string name, string fieldValue) // , Func<string> str)
{
    if (string.IsNullOrEmpty(name))
        return string.Empty;

    return string.Format(@"public static string {0} = ""{1}"";", name, fieldValue);
}

Please, to experiment with the fiddle change the following part:

Console.WriteLine(LevelTest.CreateLevelsOneLine());
Console.WriteLine(DebugClasses());

// Console.WriteLine(MapClasses(nameMapping));

To:

// Console.WriteLine(LevelTest.CreateLevelsOneLine());
// Console.WriteLine(DebugClasses());

Console.WriteLine(MapClasses(nameMapping));

This is my model class:

public class RecursiveNode
{
    public string Value { get; set; }
    public string CurrentParent { get; set; }
    public List<RecursiveNode> Childs { get; set; }

    private RecursiveNode()
    {
        Childs = new List<RecursiveNode>();
    }

    public RecursiveNode(string value, string parent)
        : this()
    {
        Value = value;
        CurrentParent = parent;
    }
}

And I still don't know where can be my memory leak, because I don't materialize any of the IEnumerables... Until I reach the StringBuilder part where I build the final string... (But if you test the other part, the Fiddle just stops due to a timeout and the last memory report is about 1.50Gb)

Note: The only part that I materialize everything is in node.Childs.AddRange(subNodes); but is this causing the issue?

Note2: I would like that any nice person that answer this question helps me guiding me with possible refactors to this methods... (As my last && first question)

Any help is welcome!

\$\endgroup\$
6
\$\begingroup\$

Lazy versus eager

I don't materialize any of the IEnumerables

Perhaps you should, because you're enumerating them many times, throwing away work again and again:

  • In Main, that nameMapping.Count() debug output enumerates nameMapping, calling GetName(node.Texture.Source) for every item.
  • In MapClasses, there's a materializing ToArray call.
  • In GetFieldValue, mapping.FirstOrDefault has to enumerate mapping until it finds the first match. Because mapping is that same lazy nameMapping sequence, this too ends up calling GetName(node.Texture.Source) many times. It doesn't help that GetFieldValue gets called a lot - very likely resulting in \$O(n^2)\$ performance.
  • In RecursiveSplitting, you're enumerating the given sequence with a foreach loop. There's also a debug Count() call there, and you're appending several Where and Select calls to the given sequence, resulting in more work for deeper recursive calls.

Or, in other words:

var lazy = items.Select(DoExpensiveWork);   // Returns a select wrapper, cheap.
lazy.Count();                               // Enumerates, doing expensive work.
lazy.FirstOrDefault(AlwaysFalse);           // Enumerates again, repeating expensive work.
// DoExpensiveWork has been called twice for every item, but all the results have been thrown away.
// Enumerating 'lazy' will repeat that work.

// versus:

var eager = items.Select(DoExpensiveWork).ToArray();    // Materializes immediately, expensive.
eager.Count();                                          // No enumeration required, cheap.
eager.FirstOrDefault(AlwaysFalse);                      // Enumerates materialized results, cheap.
// DoExpensiveWork has been called once for every item, and the results are stored.
// Enumerating 'eager' simply returns those results without repeating any work.

Use the right data structure

Repeated FirstOrDefault calls, where the selector just compares a single property, are an indication that you should be using a lookup table or dictionary instead - those offer \$O(1)\$ lookup instead of \$O(n)\$. Linq's ToLookup and ToDictionary methods are useful here. Originally, your code took about 17 seconds on my system. With an ILookup, that got cut down to about 0.3 second. Memory consumption got similarly reduced.

\$\endgroup\$
2
\$\begingroup\$

OutputRecursiveNode()

  • You are sometimes using var where the concrete type it isn't quite obvious from the right-hand-side of the assignment. Sometimes you use the concrete type where the type is obvious from the right-hand-side of the assignment (string indenter = new string('\t', count);)
  • Appending a concatenated string to a StringBuilder should better be done by using multiple Append()'s.
  • the var @class is created for each node but is only needed if node.Childs.Count > 0.
  • the indenteris created for each iteration of the loop which should be done outside of the loop.
  • The StringBuilder's ApendXx() methods provide a fluent implementation, meaning these methods are returning a StringBuilder which could be used as well.
  • The GenerateClass() method adds a Environment.NewLine which is then replaced by Environment.NewLine + indenter. By simply returning "public static class " + name from that method we can then Append() new line, the indenter and the opening brace.
  • The condition !string.IsNullOrEmpty(@class) can't never evaluate to false.

Implementing these points will lead to

private static string OutputRecursiveNode(IEnumerable<RecursiveNode> nodes, Func<string, string> getFieldValue, int count = -1)
{
    var sb = new StringBuilder();

    ++count;

    var indenter = new string('\t', count);
    foreach (var node in nodes)
    {

        if (node.Childs.Count > 0)
        {
            sb.Append(indenter)
                .AppendLine(GenerateClass(node.Value))
                .Append(indenter)
                .Append("{")
                .AppendLine(indenter)
                .Append(OutputRecursiveNode(node.Childs, getFieldValue, count))
                .Append(indenter)
                .AppendLine("}");
        }
        else
        {
            sb.Append(indenter)
                .Append(GenerateField(node.Value, getFieldValue(node.CurrentParent + UsedSeparator + node.Value)));
        }
        sb.AppendLine();
    }

    return sb.ToString();
}  

and the changed GenerateClass() would look like so

private static string GenerateClass(string name)
{
    if (string.IsNullOrEmpty(name))
    {
        return string.Empty;
    }
    return "public static class " + name;
}  

which leads to the next problem. If the name of the class is either null or Empty returning string.Empty wouldn't produce correct code. It would be better to either throw an tException (in the OutputRecursiveNode() method) or omitting classes which names are null or Empty but because the same applies to the GenerateField() method you should throw an Exception.

Just placing

if (nodes.Any(n => string.IsNullOrEmpty(n.Value))) { throw new YourDesiredtException(); }  

at the top of the OutputRecursiveNode() method will do the trick.

\$\endgroup\$

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.