Быстрый поиск интервалов в массиве
Всем привет!
Подскажите пожалуйста быстрый, по возможности не сложный, алгоритм решения такой задачи. У меня есть отсортированный большой массив с интервалами "beg" и "end". И есть некий отрезок, например: [30, 60]. Нужно найти все пересечения этого отрезка с интервалами в массиве. Самое простое это линейный поиск:
var intervals = [
{beg: 8, end: 16},
{beg: 24, end: 32},
{beg: 40, end: 48},
{beg: 56, end: 64},
{beg: 72, end: 80},
{beg: 88, end: 96}
];
var range = [30, 60];
var overlap = [];
for(i = 0; i < intervals.length; i++)
{
var A = intervals[i].beg;
var B = intervals[i].end;
if(range[0] <= B && range[1] >= A)
{
overlap.push( intervals[i] );
}
}
console.log(overlap);
Все работает, и в результате мы получим массив интервалов с которым полностью или частично пересекается наш диапазон:
{beg: 24, end: 32}
{beg: 40, end: 48}
{beg: 56, end: 64}
Но в этой реализации слишком много лишних итераций.Первое что пришло в голову по оптимизации это бинарный поиск первого левого пересечения и добивка линейным поиском. И тут проблема. Я могу найти элемент в массиве "intervals" только если есть точное совпадение например "beg" с началом отрезка. А как найти элемент между двумя значениями не могу придумать. |
HJ90,
буду приятно удивлён, если кто-то предложит лучше вариант, чем у вас. |
Цитата:
Лучше может быть оптимизация линейного поиска. Например прерывать цикл, если слева мы непрерывно что-то нашли, а после этого уже нет перекрытия - тогда искать до конца массива уже нет смысла. Но это незначительная оптимизация. Прирост производительности будет только если искомие элементы находятся вначале массива. |
Разумеется, тут можно применить поиск делением пополам. Если отрезки массива не пересекаются между собой, то всё довольно просто.
|
Alexandroppolus, а можете хотя бы в двух словах описать как бинарным поиском найти элемент в котором есть диапазон значений от 40 до 48?
Отрезки не пересекаются между собой. Но вот че-то я туплю уже второй день. Например если за основу взять такую функцию бинарного поиска, то мы найдем элемент с индексом 2:
var intervals = [
{beg: 8, end: 16},
{beg: 24, end: 32},
{beg: 40, end: 48},
{beg: 56, end: 64},
{beg: 72, end: 80},
{beg: 88, end: 96}
];
function bin_search(arr, val)
{
var min = 0;
var max = arr.length - 1;
while (min < max)
{
var mid = Math.floor((min + max) / 2);
if(arr[mid].beg < val) {min = mid + 1}
else max = mid;
}
if(arr[min].beg == val)
{
return {index:min};
}
return -1;
}
console.log( bin_search(intervals, 40) );
|
Цитата:
Цитата:
Предложу такой вариант. - Берем элемент "посередине" массива. - Узнаем как его "положение" корелирует с нашим отрезком. Т.е. мы ниже, выше, или внутри предполагаемого подмассива. - Если внутри, значит идем ниже, пока есть пересечение. А потом выше, пока не кончится пересечение. - Если ниже, делим нижнюю часть пополам и опять проверяем наше местоположение. - Если выше, делим верхнюю часть пополам и опять проверяем наше местоположение. Но это довольно сложный алгоритм и смысл в нем есть если массив тот реально здоровенный! :D А отрезок мал... |
HJ90,
А массив данных, который присутствует в коде от балды заполнен или это действительно используемые данные? |
Цитата:
|
ksa, спасибо за Ваше предложение! Буду пробовать реализовывать.
Nexus, массив заполнен от балды. А в реале значения какие угодно могут быть, всегда по возрастанию и не пересекаются. |
Цитата:
|
Цитата:
|
Цитата:
|
Пока вот так - возвращает первый слева элемент который пересекается с входным диапазоном.
Осталось найти все интервалы когда входной диапазон большой.
<html>
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="8" oninput="test()" /> и
<input type="number" value="" disabled="true" /> пересекается с
<input id="result" disabled="true" />
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
var intervals = [
{beg: 8, end: 16},
{beg: 24, end: 32},
{beg: 40, end: 48},
{beg: 56, end: 64},
{beg: 72, end: 80},
{beg: 88, end: 96}
];
function test(value)
{
var A = +document.querySelectorAll("input")[0].value;
var B = A + 2;
document.querySelectorAll("input")[1].value = B;
function bin_search_range(arr, A)
{
var min = 0;
var max = arr.length - 1;
while (min < max)
{
var mid = Math.floor((min + max) / 2);
if(arr[mid].end < A)
{
min = mid + 1;
}
else max = mid;
}
if(arr[min].beg <= B && arr[min].end >= A)
{
return arr[min].beg + "-" + arr[min].end;
}
return "...";
}
document.querySelector("#result").value = bin_search_range(intervals, A);
}
</script>
</html>
|
Если диапазон большой и охватывает много интервалов, то лучше всего найти индексы первого и последнего интервалов (оба поиска - бинарные). Возможно, копировать все интервалы между ними в отдельный массив необязательно.
|
оптимизация: цикл только по "нужным" элементам, после найденного первого. (проще конечно for и break)
можно вводить в диапазон оба параметра
<html><meta charset="utf-8">
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="8" oninput="test()" /> и
<input type="number" value="28" oninput="test()" /> пересекается с
<input id="result" disabled="true" style="width: 500px;font-size:12px; "/>
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
var intervals = [
{beg: 8, end: 16},
{beg: 24, end: 32},
{beg: 40, end: 48},
{beg: 56, end: 64},
{beg: 72, end: 80},
{beg: 88, end: 96}
];
function test(value) {
var A = +document.querySelectorAll("input")[0].value;
var B = +document.querySelectorAll("input")[1].value;
function bin_search_range(arr, A) {
var min = 0;
var max = arr.length - 1;
var temp = [];
while (min < max) {
var mid = Math.floor((min + max) / 2);
if (arr[mid].end < A) min = mid + 1;
else max = mid
}
if (arr[min].beg <= B && arr[min].end >= A) {
arr.slice(min).some(function(el) {
return !(el.beg <= B && el.end >= A && temp.push(el))
});
return JSON.stringify(temp)
}
return "..."
}
document.querySelector("#result").value = bin_search_range(intervals,A)
};
</script>
</html>
|
Цитата:
<html><meta charset="utf-8">
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="78" oninput="test()" /> и
<input type="number" value="90" oninput="test()" /> пересекается с
<input id="result" disabled="true" style="width: 500px;font-size:12px; "/>
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
var intervals = [
{beg: 8, end: 16},
{beg: 24, end: 32},
{beg: 40, end: 48},
{beg: 56, end: 64},
{beg: 72, end: 80},
{beg: 88, end: 96}
];
function test(value) {
var A = +document.querySelectorAll("input")[0].value;
var B = +document.querySelectorAll("input")[1].value;
function bin_search_range(arr) {
var min = 0;
var max = arr.length - 1;
var temp;
while (min < max) {
var mid = Math.floor((min + max) / 2);
if (arr[mid].end < A) min = mid + 1;
else max = mid
}
max = arr.length - 1;
temp = min
while (min < max) {
var mid = Math.floor((min + max) / 2);
if (arr[mid].beg < B) min = mid + 1;
else max = mid
}
if (arr[temp].beg <= B && arr[temp].end >= A) {
if (arr[min].beg <= B && arr[min].end >= A) ++min;
return JSON.stringify(arr.slice(temp,min))
}
return "..."
}
document.querySelector("#result").value = bin_search_range(intervals)
};
</script>
</html>
|
рони, то что нужно!) Всем больше спасибо за помощь!
|
HJ90,
<html><meta charset="utf-8">
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="18" oninput="test()" /> и
<input type="number" value="59" oninput="test()" /> пересекается с
<input id="result" disabled="true" style="width: 500px;font-size:12px; "/>
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
var intervals = [
{beg: 8, end: 16},
{beg: 24, end: 32},
{beg: 40, end: 48},
{beg: 56, end: 64},
{beg: 72, end: 80},
{beg: 88, end: 96}
];
function test(value) {
var A = +document.querySelectorAll("input")[0].value;
var B = +document.querySelectorAll("input")[1].value;
function bin_search_range(arr) {
for (;arr.length; ) {
if (arr[0].beg <= B && arr[0].end >= A) {
break;
}
arr = arr.slice(1);
}
var i=arr.length;
for (; i-- ;) {
if (arr[i].beg <= B && arr[i].end >= A) {
arr = arr.slice(0,++i); break;
}
}
if (arr.length) {
return JSON.stringify(arr)
}
return "..."
}
document.querySelector("#result").value = bin_search_range(intervals)
};
</script>
</html>
|
HJ90,
<html><meta charset="utf-8">
<span> [8-16] [24-32] [40-48] [56-64] [72-80] [88-96] </span>
<br>
<input type="number" value="18" oninput="test()" /> и
<input type="number" value="59" oninput="test()" /> пересекается с
<input id="result" disabled="true" style="width: 500px;font-size:12px; "/>
<style>
body {text-align:center}
span {display:inline-block; padding:15px; font-size:18px; font-family:consolas}
input {width:100px; height:50px; font-size:35px; text-align:center}
</style>
<script>
window.onload = test;
var intervals = [
{beg: 8, end: 16},
{beg: 24, end: 32},
{beg: 40, end: 48},
{beg: 56, end: 64},
{beg: 72, end: 80},
{beg: 88, end: 96}
];
function test(value) {
var A = +document.querySelectorAll("input")[0].value;
var B = +document.querySelectorAll("input")[1].value;
function bin_search_range(arr) {
for (;arr.length; ) {
if (arr[0].beg <= B && arr[0].end >= A) {
break;
}
arr = arr.slice(1);
}
for (var i=0; i<arr.length; i++) {
if (arr[i].beg <= B && arr[i].end >= A) continue;
else {arr = arr.slice(0,i); break;}
}
if (arr.length) {
return JSON.stringify(arr)
}
return "..."
}
document.querySelector("#result").value = bin_search_range(intervals)
};
</script>
</html>
|
рони, круто! Правда с бинарным поиском меньше итераций получается.
|
| Часовой пояс GMT +3, время: 16:06. |