Reducing code complexity with LINQ

Question

I have the following classes:

public class Shipment
{
 public int Id { get; set; }  
 public List<Line> Lines { get; set; }
}

public class Line
{
 public int Id { get; set; }  
 public List<Package> Packages { get; set; }
}

public class Package
{
 public int Id { get; set; }  
 public List<Event> Events { get; set; }
}

public class Event 
{
 //irrelevant properties
}

I also have a dictionary of Events and packageIds:

Dictionary<Event, int> packageEvents; //already populated

I want to match all the package events from the dictionary with their corresponding packages. The code I've written has 3 imbricated foreach statements and therefore the complexity of O(n^3). I would like to transform the code into a smaller statement using Linq and desirably also reduce the complexity.

foreach (var shipment in shipments)
{
    foreach (var line in shipment.Lines)
    {
        if (line.Packages.Any())
        {
            foreach (var package in line.Packages)
            {
                var eventsByPackage = packageEvents.Where(x => x.Value == package.Id).Select(x => x.Key);
                if (package.Events == null)
                {
                    package.Events = new List<Event>();
                }
                package.Events.AddRange(eventsByPackage);
            }
        }
    }
}

I would appreciate any suggestion. Thank you in advance.

if (line.Packages.Any()) is redundant and can be safely dropped — Dmitrii Bychenko
– Dmitrii Bychenko, Commented Jan 15, 2018 at 12:16
I think site codereview.stackexchange.com is more proper for this question. — BWA
– BWA, Commented Jan 15, 2018 at 12:16
3 nested loops are an indicator of O(n^3) (and the AddRange(eventsByPackage) would make it O(n^4)) but if the outer loops are just groupings of inner elements, then the real complexity can still be O(n) with n being the number of events to be processed. — grek40
– grek40, Commented Jan 15, 2018 at 12:28

Dmitrii Bychenko · Accepted Answer · 2018-01-15 12:40:09Z

4

If you want Linq solution I suggest using SelectMany twice in order to obtain flatten IEnumerable<Package>:

var packages = shipments
  .SelectMany(shipment => shipment.Lines)
  .SelectMany(line => line.Packages);

foreach(var package in packages) {
  if (package.Events == null)
    package.Events = new List<Event>();

  package.Events.AddRange(packageEvents
    .Where(x => x.Value == package.Id)
    .Select(x => x.Key));
}

However, willy-nilly you have to scan all packages and that's why you can't reduce O(n**3) time complexity; all you can obtain with a help of Linq is readability

edited Jan 15, 2018 at 12:40

answered Jan 15, 2018 at 12:22

Dmitrii Bychenko

188k20 gold badges178 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Dan Dohotaru · Accepted Answer · 2018-01-15 15:41:58Z

2

same as Dmitry's answer but having a slightly different syntax

var merge = new Func<Package, Package>(package =>
{
    var found = packageEvents
        .Where(p => p.Value == package.Id)
        .Select(p => p.Key);

    if (package.Events == null)
        package.Events = new List<Event>();
    package.Events.AddRange(found);
    return package;
});

var query = from shipment in shipments
            from line in shipment.Lines
            from package in line.Packages
            select merge(package);

answered Jan 15, 2018 at 15:41

Dan Dohotaru

3,1291 gold badge23 silver badges15 bronze badges

2 Comments

Ivan Stoev Over a year ago

It's strange to see this being accepted. This code does nothing. The query is just definition. In order to produce result, it has to be executed by foreaching it or calling ToList() etc. which is weird. Many people fail in that trap when trying to use LINQ for something it's not designed for (update in this case).

Dan Dohotaru Over a year ago

your're right, this is just the query definition, and as is the case with any query definition, it needs to be materialized like you mention as well, for example via ToList, i just did not include the obvious in my answer. check gist for the complete overview of the provided solution gist.github.com/dandohotaru/984c9cdee141cfc0c546398cf2e9adf4

Collectives™ on Stack Overflow

Reducing code complexity with LINQ

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related