Соедините 2 таблицы по приблизительной отметке времени

Question

Я использую EF, Linq, TSQL. У меня есть две таблицы:

Positions: 
Id [int] 
Location [geography, nullable] 
TimestampLocal [datetimeoffset(7)] 
VehicleId [int] 

Rawdata: 
Id [int] 
TimestampLocal [datetimeoffset(7)] 
Data1 [string] 
VehicleId [int] 

мне нужно присоединиться к информации из двух таблиц метки времени для конкретного VehicleId, с временными метками, которые близки, но не идентичны. Я использую MoreLinq для получения этих данных. Прямо сейчас я беру позиции в списке, затем Rawdata в другом списке, затем перебираю их, чтобы получить местоположение образца Rawdata, а затем сделайте что-нибудь с этой информацией (вычислите ближайшийPos.Location.Intersects (Polygon). ..).

var posList = entities.Positions.Where(z => (z.VehicleId == SearchedVehicleId && z.Location != null) 
&& z.TimestampLocal.Day == SearchedDay && z.TimestampLocal.Month == SearchedMonth && z.TimestampLocal.Year == SearchedYear).AsEnumerable().OrderBy(k => k.TimestampLocal); 

    var rawdatalist=entities.Rawdata.Where(k => (k.VehicleId == SearchedVehicleId) 
&& k.TimestampLocal.Day == SearchedDay && k.TimestampLocal.Month == SearchedMonth && k.TimestampLocal.Year == SearchedYear).OrderBy(k => k.TimestampLocal).ToList(); 


    foreach (Rawdata r in rawdatalist){ 
    var closestPos = posList.MinBy(t => Math.Abs((t.TimestampLocal- r.TimestampLocal).Ticks)); 
    //do something with the location 
    ComputeRawdataforLocation(closestPos, r); 
    } 

Получение данных из БД (даже с AsEnumerable(), ToList()) быстро. Проблема в том, что есть aprox 10k Positions и 100k значений Rawdata.

Как я могу ускорить процесс? Еще один способ в Линк? Может быть, TSQL-процедура, которую я могу назвать, присоединяется к значениям? Я даже не знаю, как это сделать в TSQL.

Answer 1

Получение данных из БД (даже с помощью AsEnumerable(), ToList()) выполняется быстро.

Хорошо, тогда вам нужно оптимизировать медленный поиск (MinBy - это сложность времени O (N)).

Забудьте о LINQ. Вы можете использовать тот факт, что ваш posList отсортирован, что означает, что линейный поиск может быть заменен гораздо более быстрым двоичным поиском O (log (N)).

Методы BCL BinarySearch не могут использоваться для такого сценария. Но это не так трудно написать метод с нуля, как это:

static Positions FindClosest(List<Positions> posList, DateTimeOffset value) 
{ 
    int lo = 0, hi = posList.Count - 1; 
    while (lo <= hi) 
    { 
     int pos = lo + (hi - lo)/2; 
     var item = posList[pos]; 
     int compare = value.CompareTo(item.TimestampLocal); 
     if (compare < 0) hi = pos - 1; 
     else if (compare > 0) lo = pos + 1; 
     else return item; 
    } 
    var next = lo < posList.Count ? posList[lo] : null; 
    var prev = lo > 0 ? posList[lo - 1] : null; 
    if (next == null) return prev; 
    if (prev == null) return next; 
    return (value - prev.TimestampLocal).Ticks <= (next.TimestampLocal - value).Ticks ? prev : next; 
} 

, а затем использовать его вместо MinBy:

foreach (Rawdata r in rawdatalist) 
{ 
    var closestPos = FindClosest(posList, r.TimestampLocal); 
    //do something with the location 
    ComputeRawdataforLocation(closestPos, r); 
}