Поиск в коллекциях объектов

Представим себе ситуацию, что есть две коллекции Ember-объектов (с1 и с2). У каждого объекта в этих коллекциях есть поле с именем keyField, которое является массивом простых js-объектов (у каждого есть поле f). И стоит задача найти пары объектов (один из с1, а второй из с2), у которых совпадают значения keyField.@each.f (так же важно совпадение порядка элементов в них).

Немного кода, который поможет получить нужные данные:

function someRandomString() {
	return Math.random().toString(36).replace(/[^a-z]+/g, '');
}
 
function generateArray(count) {
	var objs = [];
	for (var i = 0; i < count; i++) {
		var newObj = Ember.Object.create({});
		newObj.set('keyField', [
				{f: someRandomString()},
				{f: someRandomString()},
				{f: someRandomString()}
			]);
		objs.push(newObj);
	}
	return objs;
}

Функция generateArray создает массив (размером count) объектов требуемой структуры. someRandomString просто возвращает случайную строку.

Первая коллекция объектов будет получена просто через вызов var c1 = generateArray(1000). Для создания второй коллекции будем использовать первую, но сделаем ее копию:

function copyArrayOfObjects(array) {
	return JSON.parse(JSON.stringify(array)).map(function(o) {
		return Ember.Object.create(o);
	});
}

Теперь вызов var c2 = copyArrayOfObjects(c1); создаст точную копию первой коллекции объектов. Неплохо было бы ее перемешать:

// http://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array-in-javascript
function shuffle(o) {
    for(var j, x, i = o.length; i; j = Math.floor(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
}

c2 = shuffle(c2); и исходные данные готовы.

Начальное решение задачи досталось мне в «наследство» и выглядит так:

function testing(c1, c2) {
	var linked = [];
	for (var i = 0; i < c1.length; i++) {
		var el1 = c1[i];
		var el2 = c2.find(function(item) {
			if (el1.get('keyField.length') !== item.get('keyField.length')) {
				return false;
			}
			for (var i = 0; i < item.get('keyField.length'); i++) {
				if (item.get('keyField')[i].f !== el1.get('keyField')[i].f) {
					return false;
				}
			}
			return true;
		});
		if (el2) {
			linked.push({
				el1: el1,
				el2: el2
			});
		}
	}
	return linked;
}

Внешний цикл идет по первой коллекции и внутри него через find делается проход по второй коллекции и выполняется сравнение keyField@each.f. Если совпадение найдено, то пара объектов записывается в результирующий массив.

Данное решение «работает». Оно правильно находит пары объектов, но делает это очень медленно, так как выполняет слишком много повторяющихся действий. Что если из второй коллекции сделать немного другую структуру данных:

function arrayToObj(a) {
	var obj = {};
	for (var i = 0; i < a.length; i++) {
		obj[a[i].get('keyField').mapBy('f').join(',')] = a;
	}
	return obj;
}

Что тут происходит? Из массива объектов делается один объект (o2), ключами которого становятся собранные в одну строку значения поля f каждого keyField, а значением берется элемент коллекции. Пример:

// было
var c = [
    Ember.Object.create({
        keyField: [
            {f: 1},
            {f: 2},
            {f: 3}
        ]
    });
];
 
// стало
{
    '1,2,3': Ember.Object.create({
        keyField: [
            {f: 1},
            {f: 2},
            {f: 3}
        ]
    })
}

Что получается? Теперь не надо перебирать через find все элементы второй коллекции и сравнивать в них поштучно значения f. Достаточно просто обратиться к o2 по ключу c1[i].get('keyField').mapBy('f').join(','). Если по такому ключу есть значение, то пара объектов найдена и идем дальше:

function testing2(c1, c2) {
	var linked = [];
	var o2 = arrayToObj(c2);
 
	for (var i = 0; i < c1.length; i++) {
		var el1 = c1[i];
		var el2 = o2[el1.get('keyField').mapBy('f').join(',')];
		if (el2) {
			linked.push({
				el1: el1,
				el2: el2
			})
		}
	}
	return linked;
}

Что бы понять, насколько эффективным является такой рефакторинг, был создан jsperf-тест (используются две коллекции по 1000 элементов каждая). В нем видно, что второй способ работает минимум в 400 раз быстрее.

, ,

Оставить комментарий

Top ↑ | Main page | Back