我有以下数组:
let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
let b = ["egg", "salt", "beer"]
如何查看b
中a
中包含的单词的次数?
在上面的情况下,答案将是2次,因为来自b的所有单词都包含两次。但是,如果a
如下:
let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer"]
答案是1,因为egg
只包含一次。
时间效率是关键,因为我将使用超过10万个元素的列表。
你可以使用reduce
方法:
let words = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
var initialValue = {};
var reducer = function(word, index){
if(!word[index]){
word[index] = 1;
} else{
word[index] = word[index] + 1;
}
return word;
}
var results = words.reduce(reducer, initialValue);
console.log(results);
let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
let b = ["egg", "salt", "beer"]
let counts ={}
b.forEach(word=>{
counts[word] = a.filter(item => item ===word).length
});
console.log(counts)
这是一个相当简单的解决方案,结果将列出第二个列表中的所有内容,包括那些不在数据中的零。
在a
和b
的长度之和中,性能应该几乎是线性的。 (在a in o
中可能存在一些难以测量的非线性,但我不知道引擎内部使用的算法,所以我不能确定。)
请注意,bs.reduce((o, b) => Object.assign(o, {[b]: 0}), {})
只被调用一次,以形成第一个reduce
的初始累加器;它不是嵌套的缩减。
const counts = (as, bs) => as.reduce(
(o, a) => Object.assign(o, a in o ? {[a]: o[a] + 1} : {}),
bs.reduce((o, b) => Object.assign(o, {[b]: 0}), {})
)
const a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
const b = ["egg", "salt", "beer", "tofu"]
console.log(counts(a, b))
但实际表现可能会低于一些手工制作的for
或while
循环。 reduce
根本不像他们那样高效。
这实际上并没有回答问题。我误解了这个问题。更新版本是
const minMatch = (as, bs) => Math.min(...Object.values(as.reduce(
(o, a) => Object.assign(o, a in o ? {[a]: o[a] + 1} : {}),
bs.reduce((o, b) => Object.assign(o, {[b]: 0}), {})
)))
const a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
const b = ["egg", "salt", "beer"]
console.log(minMatch(a, b))
用a
迭代数组Array.reduce()
。将数组b
转换为Map,并将其用作reduce的初始值。
如果Map中存在数组a
中的项,则递增该值。如果没有,请忽略它。完成后,通过Math.min()
传播Map的值:
const a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
const b = ["egg", "salt", "beer"]
const result = Math.min(
...a.reduce((m, s) =>
m.has(s) ? m.set(s, (m.get(s) || 0) + 1) : m
, new Map(b.map(s => [s, 0]))
).values()
);
console.log(result);
这应该工作
let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "salt"];
let b = ["egg", "salt"];
const products = a.reduce((result, current) => {
b.forEach(word => {
if (word === current) {
result[word] = result[word] ? result[word] + 1 : 1;
}
})
return result;
}, {});
console.log(products); // { egg: 1, salt: 3 }
使用数字for
循环将a
减少为普通对象:
let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
let b = ["egg", "salt", "beer"]
const keys = b.reduce((o, k) => Object.assign(o, { [k]: true }), {})
const { length } = a
const values = {}
for (let i = 0; i < length; i++) {
const key = a[i]
if (key in keys) {
if (key in values) {
values[key]++
} else {
values[key] = 1
}
}
}
console.log(values)
数字for
循环比Array
和reduce
等forEach
方法更快,并且通常比for...of
和for...in
更快,因为它不使用iterators或反射来枚举数组的键。
keys
对象是根据b
的大小减少从O(n)到~O(1)的查找,给出总约O(n)的复杂度。如果b
也很大,那么使用数字for
循环来创建keys
,并注意查找可能会从~O(1)恶化到O(log(n)),这会给你一个总时间复杂度为O(n log) (N))。
该方法可以在迭代数组A时构建哈希映射,并在迭代数组B时访问该哈希映射(请参阅下面的代码)
let a = ["egg", "pepper", "salt", "bacon", "beer", "salt", "water", "beer", "egg"]
let b = ["egg", "salt", "beer"]
let hashMap = {};
for(let element in a){
if(!hashMap[a[element]])
hashMap[a[element]] = 0;
hashMap[a[element]]++;
}
var minVal = a.length;
for(let element in b){
if(hashMap[b[element]])
minVal = Math.min(minVal, hashMap[b[element]]);
}
console.log(minVal);