我有一系列对象。
每个对象都是{key, value}
对于每个对象键,都是一个由字符串['foo', 'bar', 'baz']
组成的数组。
我想从数组中删除['foo', 'bar', 'baz']
的所有重复项,以便仅对唯一值进行进一步处理。
目前我正在这样做
function removeArrayDupes(input){
var i = input.length;
var previous;
input.sort();
if (i){
while (--i){
var cur = input[i];
if (!cur.key){
// Remove empty records
input.splice(i,1);
} else {
// Clear duplicates
if ((previous) && (input[i].key) === previous){
input.splice(i,1);
regex= "/" + JSON.stringify(input[i].key) + "/g";
previous = input[i].key;
} else {
previous = input[i].key;
}
}
}
}
}
我的问题:如果重复数<3,则不会删除单个重复项。
我的大脑很累,因为我看不到我在哪里搞砸。
我可以多花一两个大脑来解决这个问题。
我正在寻找使用Vanilla JavaScript的解决方案。这不仅仅是使它起作用<
我想对这个问题以及是否有更好的算法有所了解。
TIA
样本数据:
[
{key: ["foo","bar","baz"], value: "Some data"},
{key: ["foo","bar","baz"], value: "Some data"},
{key: ["foo","bar","baz"], value: "Some data"},
{key: ["baz","bar","foo"], value: "Some data"},
{key: ["bar","foo","baz"], value: "Some data"},
{key: ["bar","foo","bar"], value: "Some data"},
{key: ["bar","foo","bar"], value: "Some data"},
{key: ["bar","foo","bar"], value: "Some data"},
{key: ["bar","foo","bar"], value: "Some data"},
{key: ["baz","bar","foo"], value: "Some data"},
{key: ["baz","bar","foo"], value: "Some data"},
]
所需的输出:
[
{key: ["foo","bar","baz"], value: "Some data"},
{key: ["baz","bar","foo"], value: "Some data"},
{key: ["bar","foo","baz"], value: "Some data"},
{key: ["bar","foo","bar"], value: "Some data"},
{key: ["baz","bar","foo"], value: "Some data"}
]
最佳答案
TL; DR
使用Set构造函数和spread syntax:
uniq = [...new Set(array)];
“聪明”但幼稚的方式
uniqueArray = a.filter(function(item, pos) {
return a.indexOf(item) == pos;
})
基本上,我们遍历数组,并针对每个元素检查此元素在数组中的第一个位置是否等于当前位置。显然,对于重复元素,这两个位置是不同的。
使用过滤器回调的第3个(“此数组”)参数,我们可以避免关闭数组变量:
uniqueArray = a.filter(function(item, pos, self) {
return self.indexOf(item) == pos;
})
尽管简洁,但是该算法对于大型数组(二次时间)并不是特别有效。
救援的哈希表
function uniq(a) {
var seen = {};
return a.filter(function(item) {
return seen.hasOwnProperty(item) ? false : (seen[item] = true);
});
}
通常是这样的。想法是将每个元素放在哈希表中,然后立即检查其是否存在。这给了我们线性的时间,但是至少有两个缺点:
由于哈希键只能是JavaScript中的字符串,因此此代码无法区分数字和“数字字符串”。也就是说,
uniq([1,"1"])
将仅返回[1]
出于相同的原因,所有对象都将被视为相等:
uniq([{foo:1},{foo:2}])
仅返回[{foo:1}]
。就是说,如果您的数组仅包含基元并且您不关心类型(例如,它始终是数字),则此解决方案是最佳的。
来自两个世界的最好
通用解决方案结合了这两种方法:它使用哈希查找原始图元和线性搜索对象。
function uniq(a) {
var prims = {"boolean":{}, "number":{}, "string":{}}, objs = [];
return a.filter(function(item) {
var type = typeof item;
if(type in prims)
return prims[type].hasOwnProperty(item) ? false : (prims[type][item] = true);
else
return objs.indexOf(item) >= 0 ? false : objs.push(item);
});
}
排序优衣库
另一种选择是先对数组排序,然后删除等于前一个元素的每个元素:
function uniq(a) {
return a.sort().filter(function(item, pos, ary) {
return !pos || item != ary[pos - 1];
})
}
同样,这不适用于对象(因为
sort
的所有对象都相等)。另外,我们无声地更改了原始数组作为副作用-不好!但是,如果您的输入已经排序,这就是方法(只需从上面删除sort
即可)。独一无二...
有时,我们希望根据某些条件(不仅仅是相等性)来对列表进行唯一化,例如,过滤出不同但共享某些属性的对象。可以通过传递回调来优雅地完成此操作。此“键”回调将应用于每个元素,并且删除具有相等“键”的元素。由于希望
key
返回原始值,因此哈希表在这里可以正常工作:function uniqBy(a, key) {
var seen = {};
return a.filter(function(item) {
var k = key(item);
return seen.hasOwnProperty(k) ? false : (seen[k] = true);
})
}
key()
是一个特别有用的JSON.stringify
,它将删除物理上不同但“看起来”相同的对象:a = [[1,2,3], [4,5,6], [1,2,3]]
b = uniqBy(a, JSON.stringify)
console.log(b) // [[1,2,3], [4,5,6]]
如果
key
不是原始的,则必须诉诸线性搜索:function uniqBy(a, key) {
var index = [];
return a.filter(function (item) {
var k = key(item);
return index.indexOf(k) >= 0 ? false : index.push(k);
});
}
在ES6中,您可以使用
Set
:function uniqBy(a, key) {
let seen = new Set();
return a.filter(item => {
let k = key(item);
return seen.has(k) ? false : seen.add(k);
});
}
或
Map
:function uniqBy(a, key) {
return [
...new Map(
a.map(x => [key(x), x])
).values()
]
}
两者也都可以与非原始键一起使用。
首先还是最后?
通过键删除对象时,您可能想保留“相等”对象中的第一个或最后一个。
使用上面的
Set
变体保留第一个变量,使用Map
保留最后一个变量:function uniqByKeepFirst(a, key) {
let seen = new Set();
return a.filter(item => {
let k = key(item);
return seen.has(k) ? false : seen.add(k);
});
}
function uniqByKeepLast(a, key) {
return [
...new Map(
a.map(x => [key(x), x])
).values()
]
}
//
data = [
{a:1, u:1},
{a:2, u:2},
{a:3, u:3},
{a:4, u:1},
{a:5, u:2},
{a:6, u:3},
];
console.log(uniqByKeepFirst(data, it => it.u))
console.log(uniqByKeepLast(data, it => it.u))
图书馆
underscore和Lo-Dash均提供
uniq
方法。他们的算法基本上类似于上面的第一个代码片段,归结为:var result = [];
a.forEach(function(item) {
if(result.indexOf(item) < 0) {
result.push(item);
}
});
这是二次方的,但是还有很多不错的东西,例如包装本机
indexOf
,通过键(在其说法中为iteratee
)进行唯一化的能力以及对已排序数组的优化。如果您使用的是jQuery,但在没有美元之前不能忍受任何事情,它会像这样:
$.uniqArray = function(a) {
return $.grep(a, function(item, pos) {
return $.inArray(item, a) === pos;
});
}
再次是第一个代码段的变体。
性能
函数调用在JavaScript中非常昂贵,因此上述解决方案尽管非常简洁,但并不是特别有效。为了获得最佳性能,请用循环替换
filter
并摆脱其他函数调用:function uniq_fast(a) {
var seen = {};
var out = [];
var len = a.length;
var j = 0;
for(var i = 0; i < len; i++) {
var item = a[i];
if(seen[item] !== 1) {
seen[item] = 1;
out[j++] = item;
}
}
return out;
}
这段丑陋的代码与上面的代码片段#3相同,但是速度提高了一个数量级(截至2017年,它的速度仅是后者的两倍-JS核心人员做得很好!)
function uniq(a) {
var seen = {};
return a.filter(function(item) {
return seen.hasOwnProperty(item) ? false : (seen[item] = true);
});
}
function uniq_fast(a) {
var seen = {};
var out = [];
var len = a.length;
var j = 0;
for(var i = 0; i < len; i++) {
var item = a[i];
if(seen[item] !== 1) {
seen[item] = 1;
out[j++] = item;
}
}
return out;
}
/////
var r = [0,1,2,3,4,5,6,7,8,9],
a = [],
LEN = 1000,
LOOPS = 1000;
while(LEN--)
a = a.concat(r);
var d = new Date();
for(var i = 0; i < LOOPS; i++)
uniq(a);
document.write('<br>uniq, ms/loop: ' + (new Date() - d)/LOOPS)
var d = new Date();
for(var i = 0; i < LOOPS; i++)
uniq_fast(a);
document.write('<br>uniq_fast, ms/loop: ' + (new Date() - d)/LOOPS)
ES6
ES6提供了Set对象,这使事情变得容易得多:
function uniq(a) {
return Array.from(new Set(a));
}
要么
let uniq = a => [...new Set(a)];
请注意,与python不同,ES6集按插入顺序进行迭代,因此此代码保留了原始数组的顺序。
但是,如果需要具有唯一元素的数组,为什么不从一开始就使用集?
发电机
可以在相同的基础上构建
uniq
的基于生成器的“惰性”版本:从参数中取下一个值
如果已经看到了,请跳过它
否则,产生它并将其添加到已经看到的值的集合中
function* uniqIter(a) {
let seen = new Set();
for (let x of a) {
if (!seen.has(x)) {
seen.add(x);
yield x;
}
}
}
// example:
function* randomsBelow(limit) {
while (1)
yield Math.floor(Math.random() * limit);
}
// note that randomsBelow is endless
count = 20;
limit = 30;
for (let r of uniqIter(randomsBelow(limit))) {
console.log(r);
if (--count === 0)
break
}
// exercise for the reader: what happens if we set `limit` less than `count` and why
关于javascript - Vanilla JavaScript:如何搜索对象数组,键是数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59113993/