#javascript #algorithm #search #optimization #data-structures
#javascript #алгоритм #Поиск #оптимизация #структуры данных
Вопрос:
Я написал универсальный метод расширения, который вернет элемент, соответствующий всем заданным критериям поиска (lookUpArray). Вот демонстрационный вариант.
/***************************Extension Method****************************/
var utils = {};
// Could create a utility function to do this
utils.searchInArray = function (lookUpArray, caseSensitiveSearch) {
if (!lookUpArray || lookUpArray.length <= 0)
return null;
caseSensitiveSearch = caseSensitiveSearch || false;
var self = this;
var item = null;
for (var index = 0; index < self.length; index ) {
item = self[index];
var exist = true;
for (var i = 0; i < lookUpArray.length; i ) {
if (item[lookUpArray[i].key] === lookUpArray[i].value) {
exist = exist * true;
} else { exist = exist * false; }
}
if (exist)
return item;
};
return exist ? item : null;
};
// or we could create a function on the Array prototype indirectly
Array.prototype.excSearchObjArrayForKeyValue = utils.searchInArray;
/***************************Extension Method****************************/
var inputObjectArray= [
{ emailType: 'primary', id: 1, username: 'saurabh', email: 'test@gmail.com', phone: '123' },
{ emailType: 'additional', id: 2, email: 'test2@gmail.com' },
{ emailType: 'additional', id: 2, email: 'test2@gmail.com', username:'spp' }
];
//Below is the search criterion array. Extension method should return only that object which
//matches complete below lookUpArray
var lookUpArray = [{ key: 'emailType', value: 'additional' }, { key: 'id', value: 2 }];
var result = inputObjectArray.excSearchObjArrayForKeyValue(lookUpArray);
console.log(result);
Есть ли какая-либо возможность оптимизировать (производительность) выше поиска?
Комментарии:
1.
elseРегистр внутреннего цикла может содержатьbreak, илиcontinue outerесли вы добавитеouter:метку во внешний цикл. Кроме того,ifрегистр внутреннего цикла избыточен, он не изменит значениеexist(за исключением первого раза, когда оно изменяетсяtrueна1).2. Поскольку вы хотите улучшить производительность, сохраняйте длины, а не извлекайте их на каждой итерации 😉
3. Почему вы хотите оптимизировать производительность?
Ответ №1:
Это зависит от вашего варианта использования. Если вы будете запускать функцию поиска довольно часто (по сравнению с тем, как часто изменяется массив), и если у вас ограниченное количество возможных ключей для поиска, возможно, вам стоит создать и поддерживать структуру, подобную индексу. Прямо сейчас ваш поиск представляет собой O(m*n) операцию, где m — количество ключей, а n — количество элементов в массиве. При наличии надлежащей структуры данных поиск может превратиться в O(m) операцию. Поскольку я предполагаю, что n число, вероятно, намного больше, это может значительно повысить эффективность масштабирования поиска.
Если это не имеет смысла делать, тогда вам следует, по крайней мере, замкнуть свой внутренний цикл.
var self = this;
for (var index = 0; index < self.length; index ) {
var item = self[index];
var matches = true;
for (var i = 0; i < lookUpArray.length; i ) {
var lookUpItem = lookUpArray[i];
if (item[lookUpItem.key] !== lookUpItem.value) {
matches = false;
break;
}
}
if(matches) {
return item;
}
};
return null;
Или, как предлагает nnnnnn, вы могли бы выполнить то же самое более лаконично с помощью метки:
var self = this;
outer:
for (var index = 0; index < self.length; index ) {
var item = self[index];
for (var i = 0; i < lookUpArray.length; i ) {
var lookUpItem = lookUpArray[i];
if (item[lookUpItem.key] !== lookUpItem.value) {
continue outer;
}
}
return item;
};
return null;
Если вы используете ES6, вы могли бы даже использовать функции .find() и .every() .
var self = this;
return self.find(item =>
lookUpArray.every(lookUpItem =>
item[lookUpItem.key] === lookUpItem.val));
И я бы не советовал добавлять этот метод в прототип массива. Я бы просто сделал это служебным методом.
Комментарии:
1.
.some()Функция замедлила бы работу, не так ли? (По сравнению сforциклом.)2. @nnnnnn: Вполне вероятно, что это будет немного медленнее, но трудно сказать, без бенчмарка. Если бы это изначально поддерживалось средой браузера (в отличие от полизаполнения), я мог бы представить, что это будет немного быстрее. В любом случае, я обычно считаю, что лучше всего сосредоточиться на крупномасштабной эффективности и удобочитаемости и выполнять мелкую оптимизацию только тогда, когда это абсолютно необходимо.
3. Это короткое замыкание внутреннего цикла изменяет результат. Так и должно быть
if (... != ...) break(и все еще с использованиемexistпеременной или некоторого эквивалента), потому что цель состоит в том, чтобы найти элемент, соответствующий всем критериям поиска.4. @nnnnnn: Хороший улов! Я думаю, что я это исправил. Как это выглядит сейчас?
5. «Не стесняйтесь исправлять мой код» — Готово. (Двоеточие после метки , и оно должно быть перед
for, а не внутри нее. Некоторые люди пишут это в одной строке, напримерouter: for(...).) Я не часто использую метки, но иногда они полезны во вложенных циклах.
Ответ №2:
Вы можете использовать функции массива, такие как Array.prototype.filter и Array.prototype.every , вместо самостоятельного перебора элементов:
var utils = {
searchInArray: function(targetArray, lookupArray, caseSensitiveSearch) {
return targetArray.filter(function(x) {
return lookupArray.every(function(lookup) {
if (x[lookup.key] === undefined)
throw new Error('No ' lookup.key ' property in object ' x);
if (typeof x[lookup.key] !== typeof lookup.value)
throw new Error('Type mismatch on property ' lookup.key ' in object ' x);
if (typeof lookup.value === 'string' amp;amp; caseSensitiveSearch)
return x[lookup.key].toLowerCase() === lookup.value.toLowerCase();
else
return x[lookup.key] === lookup.value;
});
});
}
};
Рабочий демонстрационный фрагмент:
var utils = {
searchInArray: function(targetArray, lookupArray, caseSensitiveSearch) {
return targetArray.filter(function(x) {
return lookupArray.every(function(lookup) {
if (x[lookup.key] === undefined)
throw new Error('No ' lookup.key ' property in object ' x);
if (typeof x[lookup.key] !== typeof lookup.value)
throw new Error('Type mismatch on property ' lookup.key ' in object ' x);
if (typeof lookup.value === 'string' amp;amp; caseSensitiveSearch)
return x[lookup.key].toLowerCase() === lookup.value.toLowerCase();
else
return x[lookup.key] === lookup.value;
});
});
}
};
var inputObjectArray = [
{ emailType: 'primary', id: 1, username: 'saurabh', email: 'test@gmail.com', phone: '123' },
{ emailType: 'additional', id: 2, email: 'test2@gmail.com' },
{ emailType: 'additional', id: 2, email: 'test2@gmail.com', username: 'spp' }
];
var lookUpArray = [{
key: 'emailType',
value: 'aDdItIoNaL'
}, {
key: 'id',
value: 2
}];
var result = utils.searchInArray(inputObjectArray, lookUpArray, true);
console.log(result); Комментарии:
1. Это делает код намного аккуратнее, но является ли это «оптимизацией»? Не будет ли использование этих методов массива с обратными вызовами медленнее, чем
forциклы?2. @nnnnnn справедливости ради, OP не упомянул, что именно они хотят оптимизировать. Этот ответ оптимизирует структуру (и удобочитаемость);-P
Ответ №3:
Вы можете использовать Arrays.find функцию.
Метод find() возвращает значение в массиве, если элемент в массиве удовлетворяет предоставленной функции тестирования. В противном случае возвращается undefined.
Взгляните на эти примеры:
var inventory = [
{name: 'apples', quantity: 2},
{name: 'bananas', quantity: 0},
{name: 'cherries', quantity: 5}
];
function findCherries(fruit) {
return fruit.name === 'cherries';
}
console.log(inventory.find(findCherries)); // { name: 'cherries', quantity: 5 }
Вы также можете написать свою пользовательскую логику, например. для поиска простых чисел:
function isPrime(element, index, array) {
var start = 2;
while (start <= Math.sqrt(element)) {
if (element % start < 1) {
return false;
}
}
return element > 1;
}
console.log([4, 6, 8, 12].find(isPrime)); // undefined, not found
console.log([4, 5, 8, 12].find(isPrime)); // 5
Пожалуйста, отметьте правильно, если это полезно.
Комментарии:
1. Вопрос явно касается универсального метода, который охватывает совпадения по нескольким свойствам в массиве объектов.
2. помимо того, что это фактически не решает проблему, неясно, как это должно представлять оптимизацию производительности.
Ответ №4:
Чтобы получить первый подходящий объект, вы можете попробовать это
utils.searchInArray = function(lookUpArray, caseSensitiveSearch) {
if (!lookUpArray || lookUpArray.length <= 0)
return null;
caseSensitiveSearch = caseSensitiveSearch || true;
var self = this;
return self.find(function(obj) {
return lookUpArray.every(function(lookup) {
if (typeof lookup.value === 'string' amp;amp; caseSensitiveSearch)
return obj[lookup.key].toLowerCase() === lookup.value.toLowerCase();
else
return obj[lookup.key] === lookup.value;
});
});
};
Чтобы получить все совпадающие объекты
utils.searchInArray = function(lookUpArray, caseSensitiveSearch) {
if (!lookUpArray || lookUpArray.length <= 0)
return null;
caseSensitiveSearch = caseSensitiveSearch || true;
var self = this;
return self.filter(function(obj) {
return lookUpArray.every(function(lookup) {
if (typeof lookup.value === 'string' amp;amp; caseSensitiveSearch)
return obj[lookup.key].toLowerCase() === lookup.value.toLowerCase();
else
return obj[lookup.key] === lookup.value;
});
});
};