System.Linq<\/code> to the using statements:<\/p>\nvar result = labRats.First(d => d.TrackingId == N - 1);\r\n\r\nreturn (int)result.Color;<\/pre>\nBe sure to place this inside a benchmark method to verify what\u2019s happening. To the untrained eye, this may seem like a simple operation without dings in performance. But it is O(n) or linear time complexity. This is because Big-O assumes the worst-case scenario<\/em>, and this means looping through a whole dataset. In .NET, First<\/code> picks the first match that exists, but Big-O must assume worst-case. In a worst-case scenario, the first match goes at the end. This frees the programmer from analysis paralysis when studying algorithms. By assuming worst-case, there is less cognitive load when thinking about algorithmic complexity.<\/p>\nBenchmark results are as follows:<\/p>\n
![\"\"](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2020\/05\/Bigo.png\")
<\/p>\n
This runs on avg for 15 microseconds given a sample size of about a thousand. The key takeaway is how this executes in microseconds. Because Big-O is either exponentially<\/em> better or worse it will run in different time units. For this reason, I recommend executing one benchmark at a time for better results.<\/p>\nBig-O O(n2<\/sup>) Quadratic Time<\/h2>\nThis time I\u2019ll need a set of mazes, go back in the BigOBenchmarks<\/code> constructor and initialize maze data:<\/p>\nmazes = new List<Maze>(N \/ 3);\r\nfor (var i = 0; i < N \/ 3; i++)\r\n{\r\n mazes.Add(new Maze\r\n {\r\n MazeNumber = i,\r\n Difficulty = (Difficulty)(i % 3),\r\n LabRat1 = i,\r\n LabRat2 = i + N \/ 3,\r\n LabRat3 = i + N \/ 3 * 2\r\n });\r\n}<\/pre>\nMaze data is but a third of lab rat data in space complexity. As data input size approaches infinity, this difference becomes negligible<\/em>. This is because both datasets share similar time and space complexities.<\/p>\nSay, for example, I want to pluck a lab rat and check which maze difficulty it finished. A solution is:<\/p>\n
var result = 0;\r\n\r\nforeach (var maze in mazes)\r\n{\r\n var rat = labRats.First(r => r.TrackingId == N - 1);\r\n\r\n result = maze.LabRat3 == rat.TrackingId ? \r\n (int)maze.Difficulty : result;\r\n}\r\n\r\nreturn result;<\/pre>\nBe sure to put this in a benchmark, and one takeaway is the nested loops. Because of the product rule, this makes the complexity O(n2<\/sup>). The outer loop goes through each maze, and the inner loop plucks a lab rat via iteration. Conceptually, nested loops on input data size n have a multiplicative<\/em> effect. If the outer loop has n items, it permutates through all items in both loops. If, for example, there are 100 items, nested loops iterate 100×100 for a grand total of 10,000.<\/p>\nThese are the results:<\/p>\n
![\"\"](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2020\/05\/BigO1.png\")
<\/p>\n
This time results are in milliseconds. Remember the chart I showed earlier? It shows this same exponential degradation. As complexity grows in Big-O, there are performance implications to the algorithm.<\/p>\n
One way to tackle Big-O complexity is with a lookup table like IDictionary<><\/code>. Instead of having to iterate through lab rats, it is possible to pick one. A lookup table does a one-to-one mapping with a given key. Lookup mapping has a constant time complexity regardless of input data size. This reduces complexity back down to O(n).<\/p>\nAdd a lookup table with a .NET dictionary to the benchmark class as a private instance variable:<\/p>\n
private readonly IDictionary<int, LabRat> labRatLookup;<\/pre>\nBecause First<\/code> was doing matches against the id, the lookup table uses this as the key. Initialize the lookup dictionary in the class constructor:<\/p>\nlabRatLookup = labRats.ToDictionary(l => l.TrackingId);<\/pre>\nNow, run another benchmark with this algorithm:<\/p>\n
var result = 0;\r\n\r\nforeach (var maze in mazes)\r\n{\r\n var rat = labRatLookup[N - 1];\r\n\r\n result = maze.LabRat3 == rat.TrackingId ? \r\n (int)maze.Difficulty : result;\r\n}\r\n\r\nreturn result;<\/pre>\nBoth solutions are identical, minus the nested loop and complexity. The lookup table uses the same id First<\/code> once used. So, this does not affect the outcome of the algorithm.<\/p>\nBenchmark results are now:<\/p>\n
![\"\"](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2020\/05\/Bigo3.png\")
<\/p>\n
Big-O O(n3<\/sup>) Cubic Time<\/h2>\nWelcome to the fray, algorithms of this complexity tend to choke on modest size datasets. The time complexity is higher relative to the data input size.<\/p>\n
In the constructor, initialize rat race data:<\/p>\n
races = new List<Race>(N);\r\nfor (var i = 0; i < N; i++)\r\n{\r\n races.Add(new Race\r\n {\r\n MazeNumber = i % (N \/ 3),\r\n Participant = i,\r\n FinishTime = (FinishTime)(i % 3)\r\n });\r\n}<\/pre>\nThis time find race finish time by cross-referencing all other data points:<\/p>\n
var result = 0;\r\n\r\nforeach (var maze in mazes)\r\n{\r\n foreach (var rat in labRats)\r\n {\r\n var race = races.Where(r => r.MazeNumber == N \/ 3 - 1).ToArray();\r\n\r\n result = maze.MazeNumber == race[2].MazeNumber\r\n && rat.TrackingId == race[2].Participant\r\n ? (int)race[2].FinishTime : result;\r\n }\r\n}\r\n\r\nreturn result;<\/pre>\nIn .NET, Where<\/code> returns any items that match the predicate. This also means looping through the entire dataset. Given the product rule with three nested loops, this spikes complexity to O(n3<\/sup>).<\/p>\nBenchmarks results are as follows:<\/p>\n
![\"\"](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2020\/05\/Bigo4.png\")
<\/p>\n
Wow, this breaks the second barrier, execution times are dismal. Because customers don\u2019t like to wait, this gets into unacceptable levels. Note data input size is in the hundreds, which is not that big at all. As data input size increases, count on this getting exponentially slower.<\/p>\n
One way to tackle this much complexity in .NET is with ILookup<><\/code>. This Where<\/code> throws a kink because it can return any number of items. What\u2019s good is this returns arrays of constant size because lab rats go in groups of three. This makes the algorithm 3f(n), applying the coefficient rule, this brings it to constant time.<\/p>\nDeclare this lookup table as a private instance variable in the class:<\/p>\n
private readonly ILookup<int, Race> raceLookup;<\/pre>\nThen, initialize race lookup data in the constructor:<\/p>\n
raceLookup = races.ToLookup(r => r.MazeNumber, r => r);<\/pre>\nThis makes MazeNumber<\/code> the key from which we get the array with three items. This is the same predicate found in the where clause. By preserving the where clause in the key, it keeps the outcome the same. The lab rat lookup can go in here too to further optimize complexity. Now tweak the algorithm as follows:<\/p>\nvar result = 0;\r\n\r\nforeach (var maze in mazes)\r\n{\r\n var race = raceLookup[N \/ 3 - 1].ToArray();\r\n var rat = labRatLookup[race[2].Participant];\r\n\r\n result = maze.MazeNumber == race[2].MazeNumber\r\n && rat.TrackingId == race[2].Participant\r\n ? (int)race[2].FinishTime : result;\r\n}\r\n\r\nreturn result;<\/pre>\nNote there are two lookups side-by-side, one for races and one for rats. Because time and space complexities are similar, applying the sum rule, this gets a 2f(n). Big-O rules combine<\/em>, so, applying the coefficient rule keeps lookups at constant time. Because this loops through mazes, the complexity is O(n).<\/p>\nI want to hear a drumroll please, time to check benchmarks results:<\/p>\n
![\"\"](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2020\/05\/Bigo5.png\")
<\/p>\n
This brings execution time back down to microseconds and way within an acceptable range. Note the exponential gains from more than a second to tens of microseconds. Going from cubic time down to linear time does make an astronomical difference. For business apps, this kind of performance is \u201cgood enough.\u201d Any further optimization is likely too pedantic for the working programmer.<\/p>\n
Big-O O(1) Constant Time<\/h2>\n
The keen reader may notice lookup tables dominate complexity gains, so why not get rid of looping? Should be interesting to see how this stacks up given the theory. Lookup tables are constant time because of this one-to-one<\/em> relationship. The computer has an easier time with this because it knows where to find this in memory. When a lookup returns many items, the coefficient rule keeps complexity constant if the array is of constant size.<\/p>\nTo eliminate looping, what is missing is a maze lookup:<\/p>\n
private readonly IDictionary<int, Maze> mazeLookup;<\/pre>\nGo in the constructor and add:<\/p>\n
mazeLookup = mazes.ToDictionary(l => l.MazeNumber);<\/pre>\nThen, tweak the algorithm so it no longer loops:<\/p>\n
var race = raceLookup[N \/ 3 - 1].ToArray();\r\nvar rat = labRatLookup[race[2].Participant];\r\nvar maze = mazeLookup[race[2].MazeNumber];\r\n\r\nvar result = maze.MazeNumber == race[2].MazeNumber\r\n && rat.TrackingId == race[2].Participant\r\n ? (int)race[2].FinishTime : 0;\r\n\r\nreturn result;<\/pre>\nBelow are the results:<\/p>\n
![\"\"](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2020\/05\/Bigo6.png\")
<\/p>\n
Success, performance should remain the same regardless of data input size. This execution time breaks into the nanosecond range. This is exponentially faster than anything I\u2019ve shown before. This follows Big-O theory with good precision, so it is trustworthy.<\/p>\n
A similar feat is possible with caching but with some gotchas. Caching large chunks of data and then looping does nothing for performance. When the cache lives outside memory and over the network in another box, large datasets must be deserialized, which spike complexity. This is one reason why caching is not a performance silver bullet. It\u2019s only by caching a narrow slice with a one-to-one lookup that any real gains come in.<\/p>\n
Conclusion<\/h2>\n
Big-O notation has a nice way to encapsulate algorithmic complexity. As algorithm complexity grows performance exponentially degrades. Looping spikes complexity and nested loops exponentiate this complexity. .NET provides lookup tables to quell this complexity such as IDictionary<><\/code>, and ILookup<><\/code>. Reducing complexity to constant time is the best optimization possible.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
Every computer science student must learn about Big-O Notation, a way to conceptualize algorithm complexity that directly relates to performance of the algorithm. In this article, Camilo Reyes demonstrates how to apply Big-O algorithms to .NET Core applications.…<\/p>\n","protected":false},"author":274017,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143538],"tags":[95509],"coauthors":[41241],"class_list":["post-87199","post","type-post","status-publish","format-standard","hentry","category-dotnet-development","tag-standardize"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/87199","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/274017"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=87199"}],"version-history":[{"count":7,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/87199\/revisions"}],"predecessor-version":[{"id":87277,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/87199\/revisions\/87277"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=87199"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=87199"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=87199"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=87199"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2020\/05\/word-image-19.png\")
<\/p>\n