Linq快速交叉查询 - 增强？

Question

在我们公司有成千上万(!)的汽车.每辆车都有一个定期发送(cycle)位置的GPS设备.

所以每个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)

从结果集中,找到所有车辆PAIRS:

(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？).我希望它可以在一个查询中.

有帮助吗？

完整的代码在线工作

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