想象一个对象,以字符串作为键,以它们出现的频率计数作为值。
{"bravo charlie": 10, "alpha bravo charlie": 10, "delta echo foxtrot": 15, "delta echo": 7}
我正在尝试优化一个算法,以便A)任何作为另一个键的子字符串并且具有相同频率值的键都应该被删除。包含较长的键应该保留。B)允许只有一个单词的键保留,即使它包含在另一个键中
下面的成对比较方法可以工作,但在大型对象上会变得非常非常慢。例如,一个具有560k个键的对象需要大约30分钟才能完成成对比较:
// for every multi word key
// if a part of a longer key in candidates AND have same length delete
let keys = Object.keys(candidates)
.sort((a, b) => b.length - a.length)
.filter(key => {
if (key.split(" ").length === 1) {
return false
}
return true
});
// ^ order keys by length to speed up comparisons and filter out single words
checkKeyI: for (const keyi of keys) {
checkKeyJ: for (const keyj of keys) {
// because we pre-sorted if length is less then we are done with possible matches
if (keyj.length <= keyi.length) {
continue checkKeyI
}
// keys must not match exactly
if (keyj === keyi) {
continue checkKeyJ
}
// keyi must be a substring of keyj
if (!keyj.includes(keyi)) {
continue checkKeyJ
}
// they must have the same freq occurr values
if (candidates[keyj] === candidates[keyi]) {
delete candidates[keyi]
continue checkKeyI
}
}
}
预期结果将是:
{"alpha bravo charlie": 10, "delta echo foxtrot": 15, "delta echo": 7}
因为bravo charlie
被淘汰了。他们有没有什么明显或聪明的方法来加快速度?
1条答案
按热度按时间sd2nnvve1#
1.根据键的长度对键进行排序(使用字母顺序作为决胜局)
1.从最长的键开始(按长度降序排列),将键添加到一个trie中,该键的叶子节点将存储该值。
1.要插入一个键,先遍历trie,如果键只有一个单词,就插入它;如果键有多个单词,并且找到了相同频率的匹配项,就不要插入它。
这会将复杂性从
O(n^2)
降低到O(n*m)
,其中n = number of strings
和m = length of longest string