当前位置:网站首页>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 23:24:19 itread01

Preface

      Today, I'd like to share some performance problems and solutions in my daily work , It's fragmented , It will be updated continuously ( The execution 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 The effectiveness 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 a type of a large collection of simple data , 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, we have faster establishment speed and save the space of indicators , 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 structures 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 indicators on the stack , Because it's 64 Bit computer, so each index accounts for 8 Byte , Plus the index of 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 there is a 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 document of Microsoft    https://docs.microsoft.com/en-us/dotnet/standard/design-guidelines/choosing-between-class-and-struct

Part 2( Optimization of nest traversal of sets )

    On nest set traversal , We're going through it as a two-tier set nest , Each collection holds 10000 An unordered integer , Then count the number of elements that have two sets at the same time , From the top to the bottom, they are in the form of regular nests , Use HashSet Type , Refer to 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, The total time is {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, The total time is {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, The total time is {sw.ElapsedMilliseconds} millisecond ");        Console.ReadLine ();    }

It can be seen from the results that , Time consuming of regular nest traversal 1 second , Time complexity is O(n2); Use HashSet Time consuming 3 millisecond ,HashSet The bottom layer uses hash tables , By looping around the outer layers , The inner set is directly hash Inquire about , Time complexity is O(n); Refer to PostgreSQL Of MergeJoin It takes time to realize the idea 19 millisecond , The method is to sort the collection first , Then mark the current displacement , Using the characteristics that the array can subscript directly, we can compare the values , Time complexity is O(n). It can be seen that , For large data sets , We should pay more attention to the nested gyrus .

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 using hash tables or sorting , Will introduce additional losses , After all, in the world of computers , Time for space , How to trade 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 , Through the memory mapping file, combined with today's content , Try it in combination with specific business scenarios .

 

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

&n

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

随机推荐