Двойной за проблемы производительности цикла
Извиняюсь за расплывчатые названия, не был уверен, как еще описать проблему.
Недавно я столкнулся со случаем, когда мне нужно пройтись по массиву объектов для сравнения нескольких значений, я решил использовать цикл for в цикле for для сравнения каждого объекта с любым другим объектом.
Хотя это хорошо работает с небольшими массивами, как только мой массив становится немного больше (скажем, 10000 объектов), производительность становится большой проблемой.
Этот массив содержит такие объекты:
[{ char: '_', from: 0, to: 2, chrLength: 2 },
{ char: '_', from: 0, to: 7, chrLength: 7 },
{ char: 'a', from: 1, to: 3, chrLength: 2 },
{ char: 'a', from: 1, to: 6, chrLength: 5 },
{ char: '_', from: 2, to: 7, chrLength: 5 },
{ char: 'a', from: 3, to: 6, chrLength: 3 }]
Идея в том, что я могу выбрать только те объекты, где from а также to не пересекаются с любым другим объектом. (from а также to индексы в другом массиве)
Таким образом, для примера массива возможные результаты будут:
[{ char: '_', from: 0, to: 2, chrLength: 2 },
{ char: 'a', from: 1, to: 3, chrLength: 2 },
{ char: 'a', from: 1, to: 6, chrLength: 5 },
{ char: 'a', from: 3, to: 6, chrLength: 3 }]
То, как я справился с этим, было следующим:
var canUse = true,
posibilities = [];
for(i = 0; i < l; i++) {
canUse = true;
for(var j = 0; j < l; j++) {
if((results[i].from < results[j].from && results[i].to > results[j].to)) {
canUse = false;
break;
}
}
if(canUse) posibilities.push(results[i]);
}
Видя производительность довольно ужасно с большими массивами, мне интересно, есть ли лучшее решение для этого?
3 ответа
Вот идея ( Демо):
- Вам нужно что-то вроде самобалансирующегося дерева, поддерживающего операции вставки и удаления O(log n) Для простоты я использовал красно-черное дерево.
- Вы должны использовать середину вашего интервала в качестве ключа, т.е.
(from + to)/2, - Предположим, вы уже "вставили"
kэлементы в вашем дереве и собираются вставитьk+1, Ваши шаги: - Если
k+1прикрывает корень - игнорируй - Если
k+1прикрывается корнем - удалите корень из дерева и сделайте еще одну попытку. - Иначе продолжайте влево или вправо поддерево, сравнивая
k+1Середина корня. - Когда все вставлено, пройдитесь по результирующему дереву, собирая каждый узел.
- Прибыль... Я использовал ваш массив в 4 раза, констатировав его сам с собой. Результат на моей машине под Chrome составляет 116 мс (холодный старт) и 64 мс (после прогрева).
Код
function process() {
console.log('Processing results of length: ' + l);
console.time('Processing');
var comparator = function(a, b) { //Comparator to build a tree
return a.mid - b.mid;
},
isAinB = function(a, b) { //util function to check if a is inside b
return b.from < a.from && b.to > a.to;
},
rbtree = new RBTree(comparator), //Build an empty tree
i = results.length - 1, item, posibilities = [];
function check(root, x) { //Recursive checker
var data;
if(!root) { //Either tree is empty or we've reached a leaf
rbtree.insert(x);
return;
}
data = root.data;
if(isAinB(data, x)) { //4
return;
}
if(isAinB(x, data)) { //5
rbtree.remove(data);
check(rbtree._root, x);
return;
}
check(root[comparator(data, x) > 0 ? 'left' : 'right'], x); //6
}
for(; i >= 0; i--) {
item = results[i];
item.mid = (item.from + item.to)/2; //2
check(rbtree._root, item); //3
}
rbtree.each(function(item) { //7
posibilities.push(item);
});
console.timeEnd('Processing');
console.log(posibilities.length);
}
Кстати, я использовал эту реализацию RBTree. Не уверен, что это лучший:)
Начните с сортировки объектов на chrLength имущество. Когда вы ищете объекты, которые препятствуют включению объекта, вам нужно только проверить объекты, которые как минимум на два символа короче.
results.sort(function(x, y){ return x.chrLength - y.chrLength; });
var posibilities = [];
for (var i = 0; i < l; i++) {
var canUse = true, len = results[i].chrLength - 2;
for (var j = 0; results[j].chrLength <= len; j++) {
if((results[i].from < results[j].from && results[i].to > results[j].to)) {
canUse = false;
break;
}
}
if(canUse) posibilities.push(results[i]);
}
С вашими примерами это уменьшает количество проверок с 36 в исходном коде до 8.
Сравнение: http://jsfiddle.net/Guffa/5jsSb/
Редактировать:
Вы можете сделать массив, где каждый элемент представляет собой массив объектов с одинаковыми chrLength, а затем сортировать каждый массив на from имущество. Таким образом, вы можете легко перейти к точке, в которой объекты начинают перекрываться, и прекращать сравнение, как только они больше не перекрываются:
var map = [];
for (var i = 0; i < l; i++) {
var ch = results[i].chrLength;
while (map.length <= ch) map.push([]);
map[ch].push(results[i]);
}
for (var i = 1; i < map.length; i++) {
map[i].sort(function(x, y){ return x.from - y.from; });
}
var posibilities = [];
for (var i = 0; i < l; i++) {
var canUse = true, len = results[i].chrLength - 2, from = results[i].from, to = results[i].to;
for (var j = 1; canUse && j <= len; j++) {
if (map[j][map[j].length - 1].from > from) {
var k;
for (k = 0; map[j][k].from <= from; k++);
for (;k < map[j].length && map[j][k].from < to; k++) {
if (map[j][k].to < to) {
canUse = false;
break;
}
}
}
}
if(canUse) posibilities.push(results[i]);
}
Это разбивает чеки на from и to свойства в два этапа, поэтому количество полных проверок (где map[j][k].to < to оценивается) на самом деле меньше, чем общее количество объектов.
Отказ от ответственности: Естественно, вам необходимо убедиться, что код работает правильно. Я проверил, что результат имеет одинаковое количество элементов, но я не сравнивал каждый элемент.
Хорошо для начала, один раз canUse является false вам не нужно продолжать внутренний цикл.
Вы можете добавить break; или измените второй цикл for на:
for (var j = 0; canUse && (j < l); j++)
и вы, вероятно, увидите полезное ускорение.