Введение
Дедупликация массивов — хорошо известная тема, и ее часто задают в интервью. Для дедупликации есть две основные идеи:
- Сначала сортировка, линейный обход, а затем дедупликация, временная сложность O(n*log2n);
- Использование хэша, пространство для времени, временная сложность O(n);
В прошлой статье я проанализировал как устроены функции подчеркивания.По этому методу мы можем написать свою библиотеку функций.В этой статье давайте рассмотрим как делается функция дедупликации подчеркивания?
Дедупликация подчеркивания
Функции
Дедупликация подчеркивания находится в группе индексов (массивы).uniqфункция, ее API выглядит следующим образом:
uniq
_.uniq(array, [isSorted], [iteratee])Псевдоним:unique
Описание: возвращает дедуплицированную копию массива, используя === для проверки на равенство. Если вы уверены, что массив отсортирован, передайте true параметру isSorted, и эта функция запустит более быстрый алгоритм. Если вы хотите обработать элементы объекта, передать Обратитесь к итератору, чтобы получить свойства для сравнения.
Вышеупомянутый API в основном хочет объяснить несколько моментов:
- Возвращает копию массива, не затрагивая исходный массив
- Стандарт равенства
a===b, указывающее, что не только значения должны быть равны, но и типы должны быть равны - Если массив отсортирован, операция дедупликации более эффективна.
-
uniqОбъекты также можно сравнивать, при условии, что сравнение необходимо указатьсвойства объекта
Мы просто используем следующее_.uniq(array, [isSorted], [iteratee]),следующим образом:
console.log(_.uniq([1,4,2,2,3,3]));
console.log(_.uniq([1,2,2,2,3,3],true));
console.log(_.uniq([{
name:1,
gender:"male"
},{
name:2,
gender:"female"
},{
name:2,
gender:"male"
},{
name:4,
gender:"male"
}],true,"gender"));
Результат выглядит следующим образом:
Дедупликационное мышление и реализация
Основная идея дедупликации подчеркивания:
новыймассив набора результатов
res, траверс бытьдедуплицированный массив, поместите каждое значение обхода вresПеребрать массив, чтобы убедиться, что не будет текущегоresПереход значения наresСредний, окончательный результатresмножество.
function uniq(array){
var res = [];
array.forEach(function(element) {
if(res.indexOf(element)<0){
res.push(element);
}
}, this);
return res;
}
console.log(uniq([1,4,2,2,3,3])); //[1,4,2,3]
вЕсли массив отсортирован, операция дедупликации более эффективна., потому что сортировка может объединить одни и те же числа для удобства сравнения до и после.
function uniq(array, isSorted) {
var res = [];
var seen = null;
array.forEach(function (element,index) {
if (isSorted) {
//当数组有序
if(!index || seen !== element) res.push(element);
seen = element;
} else {
if (res.indexOf(element) < 0) {
res.push(element);
}
}
}, this);
return res;
}
console.log(uniq([1,2,"2",3,3,3,5],true)); //(5) [1, 2, "2", 3, 5]
Для дедупликации объектов мы знаем{}==={}为false, поэтому используйте===Объекты сравнения бессмыслены в реальных сценах.
Здесь я привожу пример реального сценария:
Я хочу выбрать мужчину (самца) и женщину (женщину) в группу, участники группы следующие:
var array = [{
name:"Tom",
gender:"female"
},{
name:"Lucy",
gender:"female"
},{
name:"Edward",
gender:"male"
},{
name:"Molly",
gender:"female"
}]
Мы модифицируем вышеuniq:
function uniq(array, isSorted, iteratee) {
var res = [];
var seen = [];
array.forEach(function (element, index) {
if (iteratee) {
//判断iteratee是否存在，存在的话，取出真正要比较的属性
var computed = element[iteratee];
if (seen.indexOf(computed) < 0) {
seen.push(computed);
res.push(element);
}
} else if (isSorted) {
//当数组有序
if (!index || seen !== element) res.push(element);
seen = element;
} else {
if (res.indexOf(element) < 0) {
res.push(element);
}
}
}, this);
return res;
}
console.log(uniq([{
name:"Tom",
gender:"female"
},{
name:"Lucy",
gender:"female"
},{
name:"Edward",
gender:"male"
},{
name:"Molly",
gender:"female"
}],true,"gender"));
Результат выглядит следующим образом:
подчеркивать
uniqРеализация в основном использует вышеуказанную идею. В приложении я приложил исходный код и некоторые комментарии.
Думаем о дедупликации
Выше я проанализировал подчеркиваниеuniqРеализация функции, перед этим я также читал такие статьи, как "N Ways to Remove Duplication in JavaScript"...в подчеркиванииuniqМетод реализации функции не является оптимальным решением, по крайней мере не оптимально с точки зрения временной сложности.
Так почему бы не подчеркнутьSetобъект для решения проблемы дедупликации, используйтеindexofВременная сложность поискаO(n), а хеш-запросO(1).
я считаюSetЯвляется ли объект, указанный в ES6, подчеркивание должно учитыватьПроблемы совместимости.
Так почему бы неobjтак какSetальтернативы?
Здесь я предполагаю, что дизайнеры подчеркивания хотят использовать только свою внутреннюю реализацию_.indexOfфункция. Вот мое предположение, если у вас есть какие-либо идеи, пожалуйста, оставьте сообщение!
Ниже прикрепляю реализацию ES6 (наиболее всем знакомая):
var a = [1,1,2,3,4,4];
var res = [...new Set(a)];
прикрепить сноваobjРеализация:
function uniq(array,iteratee){
var res = [];
var obj = {};
array.forEach(function(element) {
var computed = element;
if(iteratee) computed = element[iteratee];
if(!obj.hasOwnProperty(computed))
obj[(typeof computed)+"_"+JSON.stringify(computed)] = element;
}, this);
for(var p in obj){
res.push(obj[p]);
}
return res;
}
uniq([1,"1",2,3,4,4]);// (5) [1, "1", 2, 3, 4]
приложение
подчеркиватьuniqИсходный код функции и комментарии:
_.uniq = _.unique = function(array, isSorted, iteratee, context) {
if (array == null) return [];
if (!_.isBoolean(isSorted)) {
//如果没有排序
context = iteratee;
iteratee = isSorted;
isSorted = false;
}
/**
** 此处_.iteratee
** function (key){
* return function(obj){
* return obj[key];
* }
** }
** key就是这里的iteratee（对象的属性）,这里使用了闭包
**/
if (iteratee != null) iteratee = _.iteratee(iteratee, context);
var result = [];//返回去重后的数组（副本）
var seen = [];
for (var i = 0, length = array.length; i < length; i++) {
var value = array[i];//当前比较值
if (isSorted) {
//如果i=0时，或者seen（上一个值）不等于当前值，放入去重数组中
if (!i || seen !== value) result.push(value);
seen = value;//保存当前值，用于下一次比较
} else if (iteratee) {
var computed = iteratee(value, i, array);
if (_.indexOf(seen, computed) < 0) {
seen.push(computed);
result.push(value);
}
} else if (_.indexOf(result, value) < 0) {
result.push(value);
}
}
return result;
};