Linq crosses query fast - improvement?

Question

Our company has thousands (!) Of cars. Each car has a GPS device that periodically sends ( cycle ) its location.

So, each cycle contains:

• List<Cars> (cars that sent a location matching CycleNum )
• CycleNum which is the cycle number

CycleNum is server CycleNum .

So, for example, in CycleNum=1 , 4 cars sent their location:

Used classes (simplification)

 static int TotalCycles=0; class Car { public int CarId; public int Location ; } class Cycle { public int CycleNum; public List<Car> Cars; public Cycle () { CycleNum=(++TotalCycles); } } 

Let me fill in some data:

  List<Cycle> LstCyclces = new List<Cycle>(); Cycle cycle =null; cycle = new Cycle();//cycle 1 cycle.Cars = new List<Car>(); cycle.Cars.Add(new Car {CarId=1 , Location=40}); cycle.Cars.Add(new Car {CarId=2 , Location=21}); cycle.Cars.Add(new Car {CarId=3 , Location=5}); cycle.Cars.Add(new Car {CarId=4 , Location=15}); LstCyclces.Add(cycle); cycle = new Cycle();//cycle2 cycle.Cars = new List<Car>(); cycle.Cars.Add(new Car {CarId=1 , Location=40}); //same location cycle.Cars.Add(new Car {CarId=2 , Location=57});//changed location cycle.Cars.Add(new Car {CarId=3 , Location=100});//changed location cycle.Cars.Add(new Car {CarId=4 , Location=7});//changed location cycle.Cars.Add(new Car {CarId=7 , Location=2});//new attended ( vs previous cycle) LstCyclces.Add(cycle); cycle = new Cycle();//cycle3 cycle.Cars = new List<Car>(); cycle.Cars.Add(new Car {CarId=1 , Location=40}); //same cycle.Cars.Add(new Car {CarId=2 , Location=5});//changed Location cycle.Cars.Add(new Car {CarId=4 , Location=1});//changed Location cycle.Cars.Add(new Car {CarId=9 , Location=7});//new attended ( vs previous cycle) LstCyclces.Add(cycle); 

Visualization:

As you can see:

• New car may enter the cycle
• The car may also exit the cycle.
• The car may change location (obviously)

Question

I was asked to:

For a specific given Number cycle - find all the cars that were also expected in the previous cycle, where:

("new Location" - "previous Location") < abs(40)

And from this result set, find all PAIRS cars where:

(Car_A.Location - Car_B.Location) < abs(65)

In short - I need all the cars that gave me information for the previous cycle, as well as they are far from their previous place and, finally, from these cars - I need to know which cars are next to each other.

Very important: I can’t only check the current location, because we also need to make sure that the cars are not very far from their previous location.

So, according to the image: looking at cycleNum=2 :

The cars that were also expected in the previous cycle (1) were Cars: 1,2,3,4.

From this result: cars that did not go very far from their previous place:

("new Location" - "previous Location") < abs(40)

There were cars: 1,2,4.

From this result I need to find all the pairs of cars that are now close to each other:

(Car_A.Location - Car_B.Location) < abs(65) :

So the result should be IEnumerable: (format doesn't matter)

• { Car1 , Car2 , distance=17} // distance between the two cars, 65
• { Car1 , Car4 , distance=33} // distance between the two cars, 65
• { Car2 , Car4 , distance=50} // distance between the two cars, 65

// I don't mean all permutations ( {car1 car2} , {car2 car1} )

What I tried:

  var cycleToCheck=2; //get all cars from desired cycle var requestedCycleCars = LstCyclces.Where(c=>c.CycleNum==cycleToCheck).SelectMany(c=>c.Cars); //get all cars from previous cycle var previousCycleCars = LstCyclces.Where(c=>c.CycleNum==cycleToCheck-1).SelectMany(c=>c.Cars); //intersec between those var MyWrongIntersect =requestedCycleCars.Intersect(previousCycleCars,new MyEqualityComparer()); 

But I only get cars from the current cycle, and not from the previous cycle. I also need a link to both cars from the current cycle and the previous cycle (without repeating) - for calculations.

Also I think I'm wrong using SelectMany , and this should be the fastest of them (C #, plinq?). I would like this to be in one request.

Any help?

Full code works online

nb, of course, I can do it in stages, but I repeat, or ToList () is a bad approach for me. I was hoping for one plinq request

Edit

The submitted solution works normally logically, but does not work.

2 cycles, each of which has 10,000 cars:> 9min !!!:

http://i.stack.imgur.com/mjLvG.jpg

How can I improve it? (asparallel did not work a lot)

Answer 1

Well, how much more effective

From that result I need to find all pairs of car who are now not far from each other : - this is one that is quite a killer for performance, assuming there are a lot of such pairs. A naive algorithm would do n^2 at least. You want to use a spatial SQL type that will make the query much more efficient.

If you do not want to do this / cannot, you cannot do to improve performance, I am ready to guess.

Here is the following code that will effectively connect between Cars . It is important that CarId indexed. After we find all the pairs c.Distance <40 , we will perform the final processing on the client computer, as this allows us to efficiently process the sorted cars.

 var cycleNum = 2; var curCycleCars = LstCyclces[cycleNum - 1].Cars; var prevCycleCars = LstCyclces[cycleNum - 2].Cars; var cars = curCycleCars.Join(prevCycleCars, p => p.CarId, y => y.CarId, (f1, f2) => new { Car = f1, Distance = f1.Location - f2.Location }) .Where(c => c.Distance < 40) .Select(c => c.Car) .OrderBy(car => car.Location) .ToList(); var carPairs = new CarPairList[cars.Count()]; for(var i = 0; i < cars.Count; i++) { var curCar = cars[i]; var curStartIndex = i + 1; if(i > 0) { var previousCarPair = carPairs[i - 1]; if(previousCarPair!=null) { curStartIndex = previousCarPair.EndIndex; } } int j; for(j = curStartIndex; j < cars.Count; j++) { var dis = cars[j].Location - curCar.Location; if(dis >= 65) break; } var startIndex = i + 1; var endIndex = j - 1; if(endIndex >= startIndex) { carPairs[i] = new CarPairList(curCar, startIndex, endIndex); } } foreach(var carPair in carPairs.Where(x => x!=null)){ Console.WriteLine("Car " + carPair.Car.CarId); Console.WriteLine("Cars near the distance: "); for(var i = carPair.StartIndex; i <= carPair.EndIndex; i++){ Console.WriteLine("\t - {0}, distance {1}", cars[i].CarId, cars[i].Location - carPair.Car.Location); } Console.WriteLine(); } class CarPairList { public readonly Car Car; public readonly int StartIndex; public readonly int EndIndex; public CarPairList(Car car, int startIndex, int endIndex){ Car = car; StartIndex = startIndex; EndIndex = endIndex; } } 

Answer 2

Tty this code

  var cycleToCheck = 2; var query = LstCyclces.FirstOrDefault(c => c.CycleNum == cycleToCheck).Cars .Where(c => LstCyclces.FirstOrDefault(p => p.CycleNum == cycleToCheck - 1).Cars .Any(ca => ca.CarId == c.CarId && Math.Abs(c.Location - ca.Location) < 40)); var result = query.SelectMany(t1 => query.Select(t2 => Tuple.Create(t1, t2))) .Where(x => Math.Abs(x.Item1.Location - x.Item2.Location) < 65 && x.Item1.CarId < x.Item2.CarId); foreach (var r in result) { Console.WriteLine("{0} - {1}", r.Item1.CarId, r.Item2.CarId); } 

Sample works here

Edited