对DOM的基本 *** 作可概括如下：
| *** 作原语 | 描述 |
|---|---|
| child i | 将游标设为当前的第 i i i个子节点 |
| parent | 将游标设为当前的父节点 |
| remove i | 移除第 i i i个子节点 |
| append html | 增加一个子节点，内容为html |
| modify attr x / reset attr | 修改或重置attr属性 |
| sort indices | 按照indices对子节点顺序重排 |
其中child和parent对应了树上移动，remove、append和sort能对树形结构进行更改，modify和reset对节点进行修改。显然用这些基本 *** 作来描述如何将一个DOM树变换为另外一个DOM树是完备的。
事实上，去除sort，其他 *** 作也是完备的，因为sort等价于remove和append的结合。但是由于代价因素，有必要引入此 *** 作。
之所以需要Diff算法，就是要寻找一个低的代价将一个DOM树转化成另一个DOM树。如果抛开代价，那么Diff算法就失去了实际意义。（不计代价则可直接使用整体替换的方式）
所以说引入基本 *** 作的概念，也是为了将整个过程细粒度化，从而优化掉部分非必要的 *** 作。当然，基本 *** 作在执行代价上并非等价的，通过经验估计可以得到它们的开销级别：
| *** 作 | 代价 | 解释 |
|---|---|---|
append | 大 | 解析HTML，生成完整的节点或子树 |
remove | 小 | 指针变化，触发GC时较大 |
sort | 小 | 多指针变化，需要遍历一遍孩子 |
modify | 小 | 赋值；少数情况下需要解析 |
child | 极小 | 指针变化 |
parent | 极小 | 指针变化 |
通过对代价的分析，我们可以得出结论：Diff中的结果应当尽可能少的使用append，其他 *** 作可以近似同等考虑，并且指针 *** 作可以忽略代价。
常见的Diff算法都是基于同层次的，例如其他框架中的DOM Diff、Git中的文件树Diff。这么做的好处就是不需要考虑纵向的复用，只需要考虑同层次的复用，从而使得算法更简单。
其步骤就是使用双指针，指针进行相同的移动，分别指向两棵树的同层级部分。于是我们可以边遍历，边处理差异。
指针的移动原则指针的移动并非对孩子依次进行，而是按照一定原则进行。具体而言，就是按照算法认为差异的但修改的代价最小的进行。算法按照这样的原则选中的两个节点形成一个配对，从而递归进行一个子树到另一个子树的变换过程。
子树的Diff差异分为三个级别：子树、儿子、属性。最有利的情况就是子树相同。对于判断子树相同，我们可以使用之前的哈希树，以常数时间判断。显然，对于子树相同，我们可以直接跳过。否则我们需递归进行。
属性的Diff对于算法中双指针移动到的两个节点，我们认为它们是差异的。首先一个必要的步骤是比较节点上的属性差异。基于哈希，我们首先检查属性的哈希，如果属性相同，显然可以跳过；否则遍历属性找不同。
子元素的Diff子元素的Diff是一个复杂的复合问题，我们将它分解成三个子问题：
(1). 寻找两个子元素，递归进行Diff
(2). 找到哪些子元素被添加了
(3). 找到哪些子元素被删除了
子问题(1)
子问题(1)是算法的核心问题，属于是决策问题，它需要体现指针移动原则中的最小代价。基于贪心的思路，可以设计如下的配对过程：
找到子树完全相同的两个节点对于子树不完全相同的两个节点： 找到标签相等，且内部元素相等的两个节点找到标签相等，且属性相等的两个节点找到标签相等的两个节点对于1，也就是子树Diff过程，这两个节点可以直接被跳过，代价最低；对于2.1，仅该层节点出现差异，其子孙无差异，代价很低；对于2.2，该层节点无差异，但其子孙有差异，代价未知；对于2.3，均有差异，但类型相同，代价未知但一定高于2.2。
按照如上顺序执行配对，对于1和2.1显然是最优的，但2.2与2.3只能近似优化，原因是深于子节点层次的情况我们是不知道的，只能贪心地进行下去。
子问题(2)和(3)
在子问题(1)基础上，对于标签不等的，前一个子元素集合中剩下的未配对的就是被删除的元素；后一个子元素集合中剩下的未配对的就是被增加的元素。
算法伪代码A - B：
- 比较tag
1. tag不等 => 移除B，增加A
2. tag相等 => dynamic_cast
- 比较属性
1. A中属性与B中不等
1. A中属性为默认值 => 重置属性
2. A中属性不为默认值 => 设置属性
- 比较inner_elements
1. 对于outer_hash相等的配对（完全相同） => 排序
2. 对于outer_hash不等的配对
1. 寻找tag相等且inner_hash相等的配对（属性变更） => 递归
2. 寻找tag相等且attribute_hash相等的配对（内部元素变更） => 递归
3. 寻找tag相等的配对（内部元素变更且属性变更）=> 递归
4. tag不等
1. 在A中剩下的 => 增加
2. 在B中剩下的 => 移除
3. 按照配对排序
对于子元素Diff算法，使用散列映射优化，能够将复杂度优化为 O ( m ) O(m) O(m)， m m m表示子元素个数。
对总体，最坏情况下是 O ( n ) O(n) O(n)。在每次只进行一个 *** 作的假设下，对满叉树而言，平均复杂度为 O ( l o g n ) O(logn) O(logn)。
代价分析最坏代价肯定是替换整棵树，这是基于两棵树完全不同的最坏假设而言的。在每次只进行一个 *** 作的假设下，对满叉树而言，代价比较平均，除非出现子树的整体移动。
二看Diff算法 优点和缺点优点
算法简单，执行效率高。
缺点
无法优化整体移动的代价：
基于同层次的Diff算法无法识别这种移动情形，最终的结果仍然是先删后增。
本项目中SVG的DOM结构层级比较少，且整体移动的情况很罕见，故坏情况的出现概率非常低。相反，组件在本项目中被设计的的组织结构恰好为同层次结构，因此上述算法对本项目的针对性相当强。
核心代码子元素Diff
void SVGElement::inner_differ(const SVGElement &element,
std::vector<_el_idx> &removal,
std::vector<_el_idx> &addition,
std::vector<std::pair<_el_idx, _el_idx>> &unchanged,
std::vector<std::pair<_el_idx, _el_idx>> &changed) const {
std::function<const std::string(const std::shared_ptr<SVGElement> &)> get_tag;
get_tag = [](const std::shared_ptr<SVGElement> &x){
if (x->get_raw_HTML() != STR_NULL) return std::string("#") + std::to_string(x->get_outer_hash());
return std::string(x->get_tag());
};
std::unordered_map<std::string, std::set<_el_idx>> tags_map;
std::set<_el_idx> A, B;
int c = 0;
for (auto &a : _inner_elements) A.insert({a, c++}); c = 0;
for (auto &b : element.get_inner_elements()) tags_map[get_tag(b)].insert({b, c}), B.insert({b, c++});
c = 0;
for (auto &_a : _inner_elements) { // with outer hash equal
auto &tag = get_tag(_a);
_el_idx a = { _a, c++ };
if (!A.count(a) || !tags_map.count(tag)) continue;
_el_idx match = { nullptr, -1 };
for (auto &b : tags_map[tag]) {
if (b.ptr->get_outer_hash() == a.ptr->get_outer_hash()) {
match = b;
break;
}
}
if (match.idx >= 0) {
tags_map[tag].erase(match);
A.erase(a), B.erase(match);
unchanged.push_back({a, match});
}
}
c = 0;
for (auto &_a : _inner_elements) { // with inner hash equal
auto &tag = get_tag(_a);
_el_idx a = { _a, c++ };
if (!A.count(a) || !tags_map.count(tag)) continue;
_el_idx match = { nullptr, -1 };
for (auto &b : tags_map[tag]) {
if (b.ptr->get_inner_hash() == a.ptr->get_inner_hash()) {
match = b;
break;
}
}
if (match.idx >= 0) {
tags_map[tag].erase(match);
A.erase(a), B.erase(match);
changed.push_back({a, match});
}
}
c = 0;
for (auto &_a : _inner_elements) { // with attribute hash equal
auto &tag = get_tag(_a);
_el_idx a = { _a, c++ };
if (!A.count(a) || !tags_map.count(tag)) continue;
_el_idx match = { nullptr, -1 };
for (auto &b : tags_map[tag]) {
if (b.ptr->get_attribute_hash() == a.ptr->get_attribute_hash()) {
match = b;
break;
}
}
if (match.idx >= 0) {
tags_map[tag].erase(match);
A.erase(a), B.erase(match);
changed.push_back({a, match});
}
}
c = 0;
for (auto &_a : _inner_elements) { // with tag equal
auto &tag = get_tag(_a);
_el_idx a = { _a, c++ };
if (!A.count(a) || !tags_map.count(tag) || tags_map[tag].size() == 0) continue;
_el_idx match = *tags_map[tag].begin();
tags_map[tag].erase(match);
A.erase(a), B.erase(match);
changed.push_back({a, match});
}
for (auto &a : A) addition.push_back(a);
for (auto &b : B) removal.push_back(b);
}
属性Diff
const std::string SVGElement::attribute_differ(const SVGElement &element) const {
std::stringstream ss;
if (_id != element.get_id()) {
if (_id == STR_NULL) ss << "reset id" << std::endl;
else ss << "modify id \"" << _id << "\"" << std::endl;
}
if (_lang != element.get_lang()) {
if (_lang == STR_NULL) ss << "reset lang" << std::endl;
else ss << "modify lang \"" << _lang << "\"" << std::endl;
}
// 省略其他数百个属性...
}
Diff = 子树Diff + 属性Diff + 子元素Diff
const std::string SVGElement::operator-(const SVGElement &element) const {
std::stringstream ss;
// tag differ
if (get_tag() != element.get_tag()) {
auto svg = outer_SVG();
ss << "replace " << svg.size() << std::endl << svg << std::endl;
return ss.str();
}
// cast
auto _element = static_cast<const SVGElement &>(element);
// attribute differ
if (element.get_attribute_hash() != get_attribute_hash()) ss << attribute_differ(_element);
// inner differ
if (element.get_inner_hash() == get_inner_hash()) return ss.str();
// extract change relation
std::vector<_el_idx> removal;
std::vector<_el_idx> addition;
std::vector<std::pair<_el_idx, _el_idx>> unchanged;
std::vector<std::pair<_el_idx, _el_idx>> changed;
inner_differ(element, removal, addition, unchanged, changed);
// remove
int m = _inner_elements.size(), n = element.get_inner_elements().size();
int *indices = new int[m], *removed = new int[n];
std::fill(indices, indices + m, 0); std::fill(removed, removed + n, 0);
for (auto &r : removal) removed[r.idx] = 1;
for (int i = 1; i < n; i++) removed[i] += removed[i - 1];
for (auto &r : removal) ss << "remove " << r.idx - (r.idx > 0 ? removed[r.idx - 1] : 0) << std::endl;
// append
for (auto &a : addition) {
auto svg = a.ptr->outer_SVG();
ss << "append " << svg.size() << std::endl << svg << std::endl;
}
// change recursively
for (auto &c : changed) {
auto &a = c.first; auto &b = c.second;
ss << "child " << b.idx - removed[b.idx] << std::endl;
ss << (*a.ptr - *b.ptr);
ss << "parent" << std::endl;
}
// sort
for (auto &c : unchanged) {
auto &a = c.first; auto &b = c.second;
indices[b.idx - removed[b.idx]] = a.idx;
}
for (auto &c : changed) {
auto &a = c.first; auto &b = c.second;
indices[b.idx - removed[b.idx]] = a.idx;
}
for (int i = 0; i < addition.size(); i++) {
auto &a = addition[i];
indices[unchanged.size() + changed.size() + i] = a.idx;
}
bool ordered = true;
for (int i = 0; i < m && ordered; i++) if (indices[i] != i) ordered = false;
if (!ordered) {
ss << "sort \"";
for (int i = 0; i < m; i++) {
ss << indices[i];
if (i < m - 1) ss << ",";
}
ss << "\"" << std::endl;
}
delete[] removed; delete[] indices;
return ss.str();
}
调用inner_differ后，我们只是获取了算法中认为被修改的、被添加的、被删除的元素。我们还需要对它们进行后处理：对索引进行编号，然后配对，以正确得到基本 *** 作remove和sort中需要的索引参数。
此外，还要在最开头判断标签是否相等。如果标签不相等，则进行整树替换；否则可以进行类型转换，并执行后续各Diff过程。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）