c# - Linq 快速相交查询 - 增强？

Question

我们公司有成千上万(!)辆汽车。每辆车都有一个 GPS 设备，它会定期 (cycle) 发送其位置。

所以每个Cycle包含:

• List<Cars> (发送位置的汽车 - 对应于 CycleNum )
• CycleNum这是周期数

CycleNum由服务器决定。

例如 CycleNum=1 , 4 辆车发送了它们的位置:

我使用的类(简化)

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);
    }
     
}

让我们填写一些数据:

   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);

可视化:

如你所见:

• 一辆新车可以进入循环
• 汽车也可以从自行车上驶出
• 汽车可以改变位置(很明显)

问题

我被要求:

对于特定的给定周期数 — 查找在上一个周期中也预期的所有汽车，其中:

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

然后从那个结果集中，找到所有汽车对，其中:

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

简而言之 - 我需要所有也为我提供上一个周期信息的汽车，而且它们离之前的位置不远，最后 - 从这些汽车 - 我需要知道哪些汽车彼此靠近.

非常重要:我不能只检查当前位置，因为我们还需要确保汽车没有离它们之前的位置太远。

所以根据图片:看cycleNum=2 :

同样在前一个周期 (1) 中预测的汽车是汽车:1,2,3,4。

从那个结果来看:没有离开他们之前位置很远的汽车:

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

是汽车:1,2,4。

根据该结果，我需要找到现在彼此距离不远的所有汽车对:

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

所以结果应该是 IEnumerable:(格式无关紧要)

• { Car1 , Car2 , distance=17}//这两辆车之间的距离<65
• { Car1 , Car4 , distance=33}//这两辆车之间的距离<65
• { Car2 , Car4 , distance=50}//这两辆车之间的距离<65

//我不介意所有排列( {car1 car2} , {car2 car1} )

我尝试了什么:

   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());

但我只得到当前周期的汽车，而不是前一个周期的汽车，另外 - 我需要引用当前周期和前一个周期的汽车(无需重申) - 用于计算。

此外，我认为我在使用 SelectMany 的错误路径上这应该是最快的(c#，plinq？)。我希望它可以在一个查询中。

有什么帮助吗？

Full code working online

nb，当然我可以分阶段进行，但重申或 ToList() 对我来说是不好的方法。我希望有一个 plinq 查询

编辑

发布的解决方案在逻辑上工作正常，但性能不佳。

2 个周期，每个周期有 10,000 辆汽车:> 9 分钟!!! :

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

我怎样才能改进它？(asparallel 没多大用)

Answer 1

嗯，就效率而言，

From that result I need to find all pairs of car who are now not far from each other :假设有很多这样的对，那对性能来说是非常致命的。天真的算法将运行 n^2至少。您希望使用 SQL 空间类型，这将使​​查询更加高效。

如果你不愿意这样做/不能，那么你可以做很多事情来提高性能，我愿意猜测。

这是将在 Cars 之间进行高效连接的下一个代码.重要的是 CarId被编入索引。在我们找到所有对 c.Distance <40 之后，我们将在客户的计算机上进行最终处理，因为这使我们能够以高效的方式自行处理分拣好的汽车。

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;
    }
}