R·ex / Zeng


音游狗、安全狗、攻城狮、业余设计师、段子手、苦学日语的少年。 MUGer, hacker, developer, amateur UI designer, punster, Japanese learner.

对于不可变数据的思考

注意:本文发布于 761 天前,文章中的一些内容可能已经过时。

Redux 中的一个隐藏 Bug

Bug 的成因

我在 这篇文章 中曾经说了一句关于 Redux 的话:“就算程序员未经过专门的训练(例如掌握框架的 Best Practice),也可以显著降低 Bug 出现的概率。”然而最近同学遇到的一个 Bug 让我想把这句话改掉:只有当 Redux 配合 Immutable-js 的时候,才可以显著降低 Bug 出现的概率。我相信这个坑大部分人都踩过:

// action
function updateData(data) {
    // ....
    dispatch({ data });
    // ....
}

// componenet
class X {
    // ....
    update(newData) {
        // get current data
        const { data } = this.props;
        // change data
        data.x = newData;
        // update new data to store
        updateStore(data);
    }
    // ....
    render() {
        return <div>{this.props.data.x}</div>;
    }
}
export default connect(
    ({ data }) => ({ data })
)(X);

当执行 update 的时候,界面并不会发生改变。在使用 Redux Devtools 查看 Diff 的时候,会发现 (states are equal)。有经验的大佬一眼就能看出来问题所在:由于 JavaScript 对于非基础类型是引用传值,因此当你在执行 data.x = newData 的时候,你已经把 Store 中的 data 改掉了,于是 Redux 在 Shallow Equal 的时候,会判断你传进来的值与 Store 中的值相等,本质上,上面的代码大概相当于下面的这段,这样看起来是不是简单多了:

const a = { x: 1 };
const b = a;
b.x = 2;
if (a.x !== b.x) {
    console.log(`update: ${a.x} -> ${b.x}`);
} else {
    // always execute this line
    console.log(`a.x === b.x === ${a.x}`);
}

一个很暴力的解决方案

有一个很暴力的解决方式,就是将原来的数据深克隆一份,修改之后再传回去。对于绝大部分编程语言来说,除了当对象的属性比较多,或者嵌套比较深的时候,会比较慢以外,对于空间的占用不会有太大影响,毕竟在一轮更新操作之后,之前的对象就不会被任何变量引用了,于是会被自动垃圾回收掉。但是可以有更好的方法,那就是不可变数据。

不可变数据的概念

不可变数据在函数式编程中经常出现,而且也是函数式编程语言最常见的几个特性之一。它的思想就是,每次尝试修改其中的内容,就创建一个新的数据。用代码描述的话,大概如下:

data = ['x', 1, 'y', 2, 'z', ['w', 3]]
a = make_immutable(data)
b = set(a, 'x', 2)
print(get(a, 'x')) // -> 1
print(get(b, 'x')) // -> 2

当然,具体的实现可以看本文第一段链接中的 Immutable-js(用起来与上面的代码有很大差别),我不打算在这儿讲这个库,因为官方文档已经足够详细了。

不可变数据的应用

可持久化数据结构

我在高中的时候曾经听过一个“可持久化线段树”的概念,它本质上也算一种不可变数据,因为每次对树的修改都会产生一个新的线段树,与真正的不可变数据比起来,它保存了每一个历史版本,通过共用节点来节省内存空间。

0

图片来源:https://www.cnblogs.com/zinthos/p/3899565.html

虽然它并不是专门用来解决上文中 Redux 的问题,但它竟然可以很方便地解决“区间第 k 大值”这样的问题(以前只知道线段树套平衡树),还是很让人惊讶的。在这里先膜拜一下提出一种实现方法(主席树)的 fotile 主席。顺便提一个梗,fotile 当年被称为“中国高端数据结构专家与领导者”……

后来我又看到了丽洁神犇的一篇文章《可持久化数据结构研究》,里面讲了可持久化线段树、可持久化块状链表、可持久化平衡树这三个数据结构以及应用场景。除了能解决被当作入门题的“区间第 k 大值”问题以外,它们还能解决离线转在线问题和动态凸包问题。文中也分析了几道真实的题目。这算是我见过的这类数据结构在算法中最优雅的运用了。唯一的缺点是,由于丽洁实在是太神,所以文章对新手挺不友好的……

函数式编程

又提到了这个词。前两周刚看了前同事翻译的《Elixir 程序设计》。后半部分并没有特别详细去看,因为我一时半会儿还用不上,但我对前面的内容印象挺深刻的。尤其是 Elixir 这样的函数式编程语言天生适合高并发的场景,一个很重要的原因是里面的数据都是不可变的,因此不需要信号量和锁来保证读写冲突;而且因为数据不可变,所以不用担心当前使用的数据在什么时候被哪段代码改掉了,这是不可能发生的。

追踪状态的改变

Redux 对于经常写 React 的同学已经比较熟悉了。在 Redux Devtools 里面可以追踪每一个时段的 Store 树,查看每次 Action 的 Payload,甚至还可以 Diff 被 Action 修改前后的数据。

Vuex 的原理并不是通过状态机来改变 Store,而是通过 Vue 通用的监听器来监听数据的改变,这就决定了 Vuex 是不可能对 Store 本身使用不可变数据的(Store 内部依旧可以使用不可变数据,但好像也没什么意义的样子)。

不过 Redux Devtools 和 Vuex Devtools 这两个工具并没有用不可变数据,我查看了一下它们的源码,发现 前者 是从 @@redux/INIT 时的状态(computedStates = [])开始不断使用 Reducer 计算,后者 则是在 state.history 中保存了所有完整的 Store 数据。我没法断定这两种方案哪个比较好,因为算法设计中有两个方法,一个是反复计算(用时间换空间),一个是缓存(用空间换时间),对于 Devtools 的需求,我认为这两种方法都是可行的。

不可变数据结构的实现

首先,将之前的元素深克隆一份再修改是绝对没问题的,但这太暴力了,不在本文的讨论范围之内……

高级语言中的实现

对于 JavaScript 这样的高级语言,可以参考 Immutable-js 的方式,对于不同的类型分别处理,对于一般的应用,也可以只考虑处理 Object。为了节省内存占用,在 make_immutable 的时候可以从小到大构造这个对象,修改的时候只需要从它开始往上走,创建新的对象,除了被修改的属性以外,其它属性保持之前的引用即可。对于旧的值,一旦引用数清零,就会被垃圾回收清理掉。举个例子,对于下面的数据:

const a = {
    x: 1,
    y: 2,
    z: { w: 3 }
};

应该先构造 { w: 3 } 这个数据,然后再构造整个 a 数据。最简单的实现方法当然是使用递归。然后如果在后文中 a.z 被“改掉”了,之前的 a 也被删掉了,那么 { w: 3 } 这个数据就可以被垃圾回收清理掉了。

数据结构 / 底层的实现

可以参考可持久化线段树的做法,为“修改”的数据建立新节点,修改指针的指向,通过共用节点的方式节约内存。如果是 C 这样没有垃圾回收功能的语言,还得手动写一下垃圾回收,其实也不难,只需要劫持一下赋值操作,使用引用计数就可以了。

版权声明:除文章开头有特殊声明的情况外,所有文章均可在遵从 CC BY 4.0 协议的情况下转载。
上一篇: 2017 年的回顾和结论
下一篇: 从连接器开始的一系列旅程

这是我们共同度过的

第 1553 天