当前位置:网站首页>Daily sharing: some optimization experience sharing about time complexity and space complexity (c)

Daily sharing: some optimization experience sharing about time complexity and space complexity (c)

2021-01-23 18:31:04 _ AlexYIN

Preface

      Today, let's share the performance problems and solutions we encounter in our daily work , It's fragmented , It will be updated continuously in the future ( The operating environment is .net core 3.1)

      The cases shared this time are all from actual production , Simplified as an example

Part 1( As a simple data carrier class and struct Performance comparison of )

      About class and struct The difference between , Based on experience , In most scenarios of actual development , Will use class As a data type , But if it's as A huge collection of simple data The type of , And it doesn't involve copying 、 When transferring parameters and other operations , Consider using struct, Because relative to the reference type class Distributed on the heap , As a value type struct It's distributed on the stack , In this way, it has faster creation speed and saves pointer space , List 3000 The set of ten thousand elements is represented by class and struct As a type , Do the following test ( The test tool is vs Self contained Diagnostic Tools):

class Program {
    static void Main (string[] args) {
        var structs = new List<StructTest> ();
        var stopwatch1 = new Stopwatch ();
        stopwatch1.Start ();
        for (int i = 0; i < 30000000; i++) {
            structs.Add (new StructTest { Id = i, Value = i });
        }
        stopwatch1.Stop ();
        var structsTotalMemory = GC.GetTotalMemory (true);
        Console.WriteLine ($" Using structs consumes memory :{structsTotalMemory} byte , Time consuming :{stopwatch1.ElapsedMilliseconds} millisecond ");
        Console.ReadLine ();
    }

    public struct StructTest {
        public int Id { get; set; }
        public int Value { get; set; }
    }
}

class Program {
    static void Main (string[] args) {
        var classes = new List<ClassTest> ();
        var stopwatch2 = new Stopwatch ();
        stopwatch2.Start ();
        for (int i = 0; i < 30000000; i++) {
            classes.Add (new ClassTest { Id = i, Value = i });
        }
        stopwatch2.Stop ();
        var classesTotalMemory = GC.GetTotalMemory (true);
        Console.WriteLine ($" Using classes consumes memory :{classesTotalMemory} byte , Time consuming :{ stopwatch2.ElapsedMilliseconds} millisecond ");
        Console.ReadLine ();
    }

    public struct StructTest {
        public int Id { get; set; }
        public int Value { get; set; }
    }
}

By calculation ,struct The consumption of space includes : Each structure contains two integers stored on the stack , Each integer accounts for 4 Bytes , Each structure accounts for 8 byte , multiply 3000 Ten thousand elements occupy 240,000,000 byte , It is consistent with the actual measurement ;

and class The consumption of space is more complicated , Contains : Each class contains two integers that exist on the heap , Each integer accounts for 4 byte , Two pointers on the stack , the reason being that 64 Bit computer, so each pointer takes 8 byte , Plus a pointer to the class itself 8 byte , Per class 24 byte (4+4+8+8+8), multiply 3000 Ten thousand elements occupy 960,000,000 byte , It is consistent with the actual measurement . In terms of time consumption class Because of the memory allocation , Time consuming 5 About seconds , Far greater than struct Of 1.5 second .

Based on this test ,

More about class and struct Please go to the official Microsoft document    https://docs.microsoft.com/en-us/dotnet/standard/design-guidelines/choosing-between-class-and-struct

Part 2( Optimization of nested traversal of sets )

    About nested set traversal , We iterate through it in two levels of nested sets , Each collection holds 10000 An unordered integer , Then count the number of elements that have two sets at the same time , From top to bottom in regular nested loops , Use HashSet type , Reference resources PostgreSQL Of MergeJoin For example :

class Program {
    static void Main (string[] args) {
        var l1s = new List<int> ();
        var l2s = new List<int> ();
        var rd = new Random ();
        for (int i = 0; i < 10000; i++) {
            l1s.Add (rd.Next (1, 10000));
            l2s.Add (rd.Next (1, 10000));
        }

        var sw = new Stopwatch ();
        sw.Start ();
        var r = new HashSet<int> ();
        foreach (var l1 in l1s) {
            foreach (var l2 in l2s) {
                if (l1 == l2) {
                    r.Add (l1);
                }
            }
        }
        sw.Stop ();
        Console.WriteLine ($" Total found {r.Count} Two elements exist at the same time l1s and l2s, It took time {sw.ElapsedMilliseconds} millisecond ");
        Console.ReadLine ();
    }

class Program {
    static void Main (string[] args) {
        var l1s = new HashSet<int> ();
        var l2s = new HashSet<int> ();
        var rd = new Random ();
        while (l1s.Count < 10000)
            l1s.Add (rd.Next (1, 100000));
        while (l2s.Count < 10000)
            l2s.Add (rd.Next (1, 100000));

        var sw = new Stopwatch ();
        sw.Start ();
        var r = new List<int> ();
        foreach (var l1 in l1s) {
            if (l2s.Contains (l1)) {
                r.Add (l1);
            }
        }
        sw.Stop ();
        Console.WriteLine ($" Total found {r.Count} Two elements exist at the same time l1s and l2s, It took time {sw.ElapsedMilliseconds} millisecond ");
        Console.ReadLine ();
    }

class Program {
    static void Main (string[] args) {
        var l1s = new List<int> ();
        var l2s = new List<int> ();
        var rd = new Random ();
        for (int i = 0; i < 10000; i++) {
            l1s.Add (rd.Next (1, 10000));
            l2s.Add (rd.Next (1, 10000));
        }

        var sw = new Stopwatch ();
        sw.Start ();
        var r = new List<int> ();
        l1s = l1s.OrderBy (x => x).ToList ();
        l2s = l2s.OrderBy (x => x).ToList ();
        var l1index = 0;
        var l2index = 0;
        for (int i = 0; i < 10000; i++) {
            var l1v = l1s[l1index];
            var l2v = l2s[l2index];
            if (l1v == l2v) {
                r.Add (l1v);
                l1index++;
                l2index++;
            }
            if (l1v > l2v && l2index < 10000)
                l2index++;
            if (l1v < l2v && l1index < 10000)
                l1index++;

            if (l1index == 9999 && l2index == 9999)
                break;
        }
        sw.Stop ();
        Console.WriteLine ($" Total found {r.Count} Two elements exist at the same time l1 and l2s, It took time {sw.ElapsedMilliseconds} millisecond ");
        Console.ReadLine ();
    }

The result shows that , Regular nested traversal takes time 1 second , The time complexity is O(n2); Use HashSet Time consuming 3 millisecond ,HashSet The bottom layer uses hash table , By looping the outer set , The inner set is directly hash lookup , The time complexity is O(n); Reference resources PostgreSQL Of MergeJoin Thinking takes time 19 millisecond , The idea is to sort the set first , Then mark the current displacement , Using the property that array can subscript directly , The time complexity is O(n). thus it can be seen , For large data sets , We should pay special attention to nested loops .

More about merge join Please move the design idea of PostgreSQL Official documents of   https://www.postgresql.org/docs/12/planner-optimizer.html

It should be noted that , Whether it's hashing or sorting , Will introduce additional losses , After all, in the world of computers , Either to Time for space , Either to Space for time , If you want to optimize time or space at the same time, can you do it ? It's also possible in some scenarios , You can refer to my previous blog , adopt Memory mapped files Combined with what we're talking about today , You can try it .

 

If there are any questions , You are welcome to correct at any time , Sharing and trial and error is also a learning process , Thank you. ~

 

版权声明
本文为[_ AlexYIN]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/01/20210123182902500k.html

随机推荐