我在millions of rows中有一個有點大的數據集，它由時間戳形式的start time和end time組成。如何高效地計算時間範圍的交集？
我需要找出最有效率或相當有效的方法來計算這些時間範圍相交的次數。開始時間按升序排列，但結束時間可能不是，也可能不是。
E.g.
1 - Start: 1484725031, End: 1484725045
2 - Start: 1484725033, End: 1484725039
3 - Start: 1484725040, End: 1484725049
在這裏，我們必須記錄1 & 2相交和記錄1和3相交。
目前，我只是通過所有的時間範圍內循環，然後比較，針對這實在是太慢了整個列表...
，我怎麼能改善這個有什麼建議？
比較每個可能的匹配，如果兩個都沒有在另一個開始之前結束，則它們相交。
var times = [{
start: 1484725031,
end: 1484725045
}, {
start: 1484725033,
end: 1484725039
}, {
start: 1484725040,
end: 1484725049
}];
function findIntersections(times) {
var newtimes = times.map(function(a, b) {
//Generate list to track intersections
var intersections = [];
a["intersections"] = intersections;
//Generate a unique id, i use index in array
a["id"] = b;
return a;
});
//Loop 1
for (var timeIndexA = 0; timeIndexA < newtimes.length; timeIndexA++) {
var timeA = newtimes[timeIndexA];
//Loop 2, notice how we start from Loop 1 + 1. That way we only check each matchup once
for (var timeIndexB = timeIndexA + 1; timeIndexB < newtimes.length; timeIndexB++) {
var timeB = newtimes[timeIndexB];
if (
//If none end before the other start, they must intersect
(timeA.end < timeB.start || timeB.end < timeA.start) == false) {
//Save intersections by index parameter
timeA.intersections.push(timeB.id);
timeB.intersections.push(timeA.id);
}
}
}
//Return result
console.log(newtimes);
}
//Find indexes
var indexed = findIntersections(times);
//log indexes
console.log(indexed);，你直覺，你需要降低你做比較的數量。通常的路線是剛剛比不上我和J，如果你已經比較J和I.是與下面的僞代碼很容易做到：
for i over all values{
for j over 0 to i -1 // alternatively over i+1 to end
//compare here
}
}
那滴你從N²比較數N（N-1）/ 2（你仍然在O（n²）領域，但它更好）。
幸運的時間跨度的陣列自帶上排序的開始時間，這樣你就可以走一步：
for i over all values{
for j over i +1 to end of array
if(intersects){
//do your thing
}else{
// break the looping over j,
// as no new value will start before times[j]
break;
}
}
}
這應該大大降低了計算時間，但在不可預測的方式，因爲它是數據 - 依賴。
let timeIntervals = [(start: TimeInterval, end: TimeInterval)]()
var count = 0
for x in 0..<timeIntervals.count {
for y in x+1..<timeIntervals.count {
if timeIntervals[x].end >= timeIntervals[y].start {
count += 1
} else {
break
}
}
}
您可以使用一個對象來計算迭代只有整個數組和內部，直到更大的起始值。
此提案使用非重疊的開始和結束時間，因此例如start = 5和end = 5不重疊。
1111111111 overlapping --- 1 ------ 3 ----- 2 ------ 3 --- 2 ----- 1 ----- 0
結果對象讀取如下
{ "0|2": { // 1 intersection "0|5": true }, "0|5": { // { start: 0, end: 5 } intersects with 3 objects "0|2": true, // { start: 0, end: 2 } and "3|7": true, // { start: 3, end: 7 } and "4|9": true // { start: 4, end: 9 } }, "3|7": { "0|5": true, "4|9": true }, "4|9": { "0|5": true, "3|7": true, "8|10": true }, "8|10": { "4|9": true, "9|13": true }, "9|13": { "8|10": true }, "15|19": {} // no intersection }
var data = [{ start: 0, end: 5 }, { start: 3, end: 7 }, { start: 4, end: 9 }, { start: 8, end: 10 }, { start: 9, end: 13 }, { start: 15, end: 19 }],
intersections = {};
data.forEach(function (a, i, aa) {
var j = i + 1,
keyA = a.start + '|' + a.end,
keyB;
intersections[keyA] = intersections[keyA] || {};
while (j < aa.length && aa[j].start < a.end) { \t \t \t \t
keyB = aa[j].start + '|' + aa[j].end;
intersections[keyA][keyB] = true;
intersections[keyB] = intersections[keyB] || {};
intersections[keyB][keyA] = true;
j++;
}
});
console.log(intersections);.as-console-wrapper { max-height: 100% !important; top: 0; }
按開始時間排序他們。那麼至少你知道你不必尋找早期的範圍，並且一旦找到第一個與當前範圍不相交的第一個範圍，就可以停止。 –
其實你正在使用哪種語言？請注意刪除不必要的標籤 –
我在PHP中執行此操作，但我也可以使用JavaScript。道歉，我刪除了額外的標籤。 – FirstLegion