复杂系统

Complexity: A Guided Tour

这篇笔记断断续续写了很久,不是时间问题,不是理解问题,就是复杂性问题。复杂性理论作为泛理论,本质是对多个学科进行组合提炼,发展出思想。我们能读到的基本是思想,内在逻辑,但是如果基于表面提炼出的思想,探究其内在、本质等,显然还差了很多,至少这个理论现在也是这种状态…

复杂系统

17世纪,拉普拉斯时期开始,还原论成了科学的主导,大多数人认为,世界是客观的,给我们足够多的参数,我们可以还原整个客观的世界,更直观的说,如果你了解了整体的各个部分,以及把这些部分整合起来的机制,你就可以了解这个整体。 侯世达说,只要精神正常的人,就不会反对还原论。最近几十年开始,一些人开始尝试建立新的基础,包括控制论、协同学、系统科学,当然也包括本书的主题-复杂系统,这些人中包括了侯世达(圣塔菲实验室里的低调的研究者),而本书的作者米歇尔也是其中的一位。

什么是复杂性,现实世界太多直观的例子,单只行军蚁是已知行为最简单的生物,如果把100只行军蚁放在一个平面,它们会不断外围绕圈然后体力耗尽而死,但是如果把上百万只聚集在一起,群体形成整体,涌现出所谓的“集体智能”,于是蚁群变成了超生物。类似的还有免疫系统,市场经济,人类细胞,以及我们为之沉迷的“智能”和意识

这些系统都具有如下的共性:

  1. 复杂的集体行为
  2. 信号和信息处理
  3. 适应性

而复杂系统理论就是试图解释这种没有中央控制下的简单个体,如何通过自组织,形成产生模式处理信息甚至进化学习的整体。 这是个泛理论,研究的交叉学科领域。

用书中的定义:复杂系统是由大量组分组成的网络,不存在中央控制,通过简单运作规则产生出复杂的集体行为和复杂的信息处理,并通过学习和进化产生适应性。, 进一步抽象化:复杂系统是具有涌现和自组织行为的系统。

显然,涌现自组织行为产生的机制是复杂性理论研究者最关注的。

复杂综述

从伽利略开始,科学引入了实验观测,牛顿在伽利略基础上提出运动三定律,至此,牛顿为我们描绘了一个钟表宇宙:设定好初始状态,沿着三大定律一直走下去。上个世纪20年代,海森堡提出了测不准定律,钟表宇宙慢慢的崩塌。而进入60年代,混沌理论指出,系统的演进对初始条件有种敏感依赖度,即如果系统的混沌的,测量初始位置时如果产生极小的误差,在预测未来运动时,也会产生极其巨大的误差。庞加莱的三体问题就是一个典型的混沌系统。

量子理论的出现告诉我们,这个世界的基本组成本身是不确定的,而混沌理论告诉我们即使一个确定性系统,无任何随机源,因为一些初始条件敏感性,这个系统(的发展)仍然是不确定的

混沌理论的出现是突破性的,它告诉我们非线性是系统的关键因素,而还原论只关注线性

Logistic映射是一个非常直观的混沌表现:

x(t+1) = μx(t)(1-x(t))

Logistic映射描述了一个时间离散的动力系统,t为迭代时间步长,x(t) [0,1], μ是参数。 在这个系统里,μ的设置,将产生完全不同,不可预测的结果。

0<μ<1

1<μ<3

3<μ<3.6

μ=3.6

μ=4时,系统完全进入分叉

分叉

然后对混沌系统深入研究,发现其在宏观层面仍然是可预测的,这方面的研究包括倍周期之路,费根保姆常数等。

当人们开始探究复杂现象的本质时,人们慢慢跟可能是目前为止人类最伟大的理论联系在一起 – 熵增理论,显然,复杂系统关注的问题是这种逆熵的自组织系统是如何产生。从麦克斯韦妖,到西拉德将熵和信息联系在一起,再到玻尔兹曼的统计力学,作者带着我们走过了熵在宏观态和微观态的体现。然后信息出现了,香农的信息熵是信息源的可预测性,信息是用来计算的,所以,复杂性的一个很重要问题就是计算问题。计算问题由来已久,从莱布尼兹的符号系统,到希尔伯特问题,再到哥德尔不完备性,最后到图灵机,我们慢慢的认识到过去对数学和计算的期望可能只是幻想。

于是,我们发现,量子力学和混沌理论摧垮了精确预测的希望,而哥德尔和图灵的结果摧垮了数学和计算无所不能的希望。从历史的角度看,我们从来没有这么确信过,这个世界是复杂的。

之后,作者从进化,遗传,现代综合到角度进一步试图抓到复杂的本质。对于进化论,熵的减少是自然选择的结果,对于遗传学,进化的渐进过程,通过自然选择和个体细微随机变异产生,而宏观尺度的现象,如新物种诞生,可以用基因变异和自然选择微观过程解释。这不可避免的会触及生命本源问题,虽然通过DNA结构,我们越来越认清作为单个个体的本质,但是群体而言,元胞自动机,冯诺依曼自动复制机,可能给我们宏观上认识生命提供了更多的启示,显然,生命也是群体的涌现!

等待卡诺

总得来说,复杂系统明显表现出理论空泛,缺乏实质的特点,它的主题非常松散,而且核心定义又不明确,更关键的是由于理论工具的缺乏,无法形成体系。拿还原论来类比,它没有合适的定义和可以描述的数学工具,因此,无论是过去还是现在,都存在着瓶颈。这一点米歇尔也是直言不讳。可以说,复杂系统现在提供了一种新的思路,如果作为一门科学,还需要尼古拉卡诺这类的人出现,对于我们而言,能做的就是等待卡诺。

2017年度学习计划

技术

后端架构

  • 后端系统的docker化 【Docker相关】
  • 重构thor, java 8化,通用业务框架 【业务框架相关】
  • termite微服务框架 【服务框架相关,包括netty, ioc的深入了解】
  • api gateway重构 【LB相关】
  • extractor重构 【HA相关】
  • 系统化的架构理论【分布式存储相关】
  • 学习下go语言

机器学习

  • 深入理解主流的统计机器学习算法,包括SVM, 最大熵,AdaBoost,Random Forest,EM,条件随机场,HMM等。
  • 深入理解深度学习的内部运行原理,包括CNN, RNN, RCNN, LSTM
  • 机器学习平台搭建完成,完成基础的智能业务
  • 对caffe, tensorflow, mxnet等至少深入了解一种深度学习框架的技术架构

科学素养

数学

  • 微积分,至少可以看懂基本的证明
  • 数理统计,统计学的基本思想和概念
  • 随机过程, 随机过程的基本思想和概念
  • 线性代数, 熟练基本运算

物理

  • 量子力学,至少可以应对量子计算机的水准
  • 相对论,大体了解场方程的基本计算过程

生物

  • 神经生物学,神经的基本机制
  • 脑科学,脑工作的基本原理

个人

  • 读一本近代史
  • 读一本科学哲学相关著作
  • 读1-2本复杂系统、世界观相关的著作
  • 全年至少读15本书,可以产出10+的读书笔记

2016的科普学习

这一年读了不少科普书,卢昌海小楼与大师,寻找太阳系的疆界,太阳的故事,伽莫夫的从一到无穷大,物理世界奇遇记, 汪洁的时间的形状, 外星人防御计划, 各种简史人类简史, 万物简史, ,物理、数学、生物相关的包括温伯格的宇宙最初三分钟,霍金的时间简史宇宙简史,费曼自传别闹了,费曼先生, 数学那些事儿数学沉思录进化!进化?达尔文背后的故事科学的极致:漫谈人工智能 等等。

一年来科学素养有了一定提升,技术是基础科学的催化物,一定的科学素养间接的影响了自己的技术素养,总的来说真的很值。

从这些科学史至少可以得到这些鸡汤:

  • 合适的人应该在合适的位置上
  • 持之以恒的信念是成功的源泉
  • 运气很重要

2016年终于过去了,希望好运能够到来,找到更时候自己的位置,持之以恒地走下去。

Mac下运行voc-dpm

因为搞voc-dpm,需要搭建matlab环境,折腾了很久才搞定。

我下载的是matlab2014b,下载后运行voc-dpm的demo会报如下的错误。

Error using mex No supported compiler or SDK was found. For options,
visit http://www.mathworks.com/support/compilers/R2014a/maci64.html.

参考Require,要求xcode 4.6+, gfortran 4.3.x, 都符合要求.mex -setup后仍然不行,显然matlab没有找到xcode的compiler。

翻各种资料终于找到,需要更新一个配置

1
>> edit ([matlabroot '/bin/maci64/mexopts/clang_maci64.xml'])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<ISYSROOT>
<and>
<cmdReturns name="xcode-select -print-path"/>
<or>
<dirExists name="$$/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk" />
<dirExists name="$$/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.10.sdk" />
<dirExists name="$$/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.11.sdk" />
<dirExists name="$$/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.12.sdk" />
<cmdReturns name="find $$ -name MacOSX10.9.sdk" />
<cmdReturns name="find $$ -name MacOSX10.10.sdk" />
<cmdReturns name="find $$ -name MacOSX10.11.sdk" />
<cmdReturns name="find $$ -name MacOSX10.12.sdk" />
</or>
</and>
</ISYSROOT>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<SDKVER>
<and>
<and>
<cmdReturns name="xcode-select -print-path"/>
<or>
<dirExists name="$$/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.9.sdk" />
<dirExists name="$$/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.10.sdk" />
<dirExists name="$$/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.11.sdk" />
<dirExists name="$$/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.12.sdk" />
<cmdReturns name="find $$ -name MacOSX10.9.sdk" />
<cmdReturns name="find $$ -name MacOSX10.10.sdk" />
<cmdReturns name="find $$ -name MacOSX10.11.sdk" />
<cmdReturns name="find $$ -name MacOSX10.12.sdk" />
</or>
</and>
<cmdReturns name="echo $$ | rev | cut -c1-10 | rev | egrep -oh '[0-9]+\.[0-9]+'" />
</and>
</SDKVER>

处,分别增加10.12.sdk(我的系统是macOS Sierra + Xcode8.1)。

voc-dpm需要openmp的支持,但是mac的clang编译器并不支持,需要做如下的处理:

首先

1
2
brew install homebrew/boneyard/clang-omp
brew install homebrew/boneyard/libiomp

安装clang-omp, 然后ln -s /usr/local/lib/libiomp5.dylib /usr/local/lib/libgomp.dylib 创建符号链接, 此时系统存在一个支持omp的clang编译器和标准的clang编译器,继续修改clang_maci64
CC指令换成CC="$XCRUN_DIR/xcrun -sdk macosx$SDKVER clang-omp",然后include libs分别增加omp的引用位置

INCLUDE="-I&quot;$MATLABROOT/extern/include&quot; -I&quot;/usr/local/include/libiomp&quot; -I&quot;$MATLABROOT/simulink/include&quot;" LINKLIBS="-L&quot;$MATLABROOT/bin/maci64&quot; -L&quot;/usr/local/lib&quot; -lmx -lmex -lmat -lc++"

重启matlab mex -setup则正常.

后端工程师的成长

工程师成长之前的观点。 工程师怎么成长

我的观点核心是,认清自己的定位体系化的成长,通过技术视野促进自己的成长。

Java基础

对于Java而言,最基础的无外乎Java Specs JVM Specs 阅读代码,尤其是基础类库的时候有疑问基本可以从这里翻。

总体上把握的话还是 Thinking in Java, 进阶就是思想上的问题,这些可以看下:

然后就是深度问题,如果从系统设计的角度看,无外乎Concurrent(JUC), Nio, Streaming等等,这些基本需要深入的研究和理解下。

Java之外

深度的本源还是基础,比如看nio的多路复用,免不了epoll/kqueue之类,性能优化也免不了进程/线程管理等,这类的基础还是os和linux kernel相关。而socket相关又免不了TCP/IP4层。 JUC里的CAS AQS很多东西又设计到JMM,这些基本又是计算机体系结构的内容。这些都是技能树里的叶节点。

  • Linux内核
  • 操作系统
  • 深入理解计算机系统

基础的外延才是架构,如果希望对架构有个较深的整体认识,还需要对架构模式有一定的认识。比如经典的POSA系列。

后端系统的最终还是分布式,分布式的基本思想需要有一定的把握力,比如分布式难点,Paxos, 2PC, CAP等,如果没有类似的宏观概念基本没有什么架构观念在里面。

MIT 6.824 是个很好的梳理。

进阶

程序员没有什么捷径,就是多读多写代码。

  • netty
  • spring
  • guava
  • elasticsearch
  • dubbo(x)

怎么读,我认为最有效的方法还是造轮子

视野

通用的技术社区我就不列了,而且通用社区基本每天都有后端的各种信息,这个能解决很多问题。

其他的,如知乎的R大,InfoQ(Qcon, ArchSummit), JavaOne, OpenJDK Maillist等等。

回到目前的团队

接下来做的事情:

  • 基础服务docker化 (jenkins, gitlab, jira, testlink etc.)
  • 数据基础服务的搭建 (database混乱, log混乱, 数据中心化等)
  • 服务轻量级化 (termite, 轮子, 部分服务docker化)
  • Java 8化 (拥抱变化, 包括为了的java9的jigsaw.)
  • 组件化 (为了业务而做组件?组件的价值是什么? )
  • 其他的… (比如change队列, yaml loader, optlog etc. 我要做这些的目的是什么? )

我们写过的代码,做过的调研,是好牙医技术的财富,更是我们技术生涯的财富。

公司成长和个人成长永远是双赢的。

最后

人的精力总是有限的,成长都是暗时间的累计,差距也是一分一毫的累计。

人都是懒惰的,当自驱力失效的情况下,强制是唯一的手段。

EOF

EnumSet

EnumSet

EnumSet是JDK 1.5推出的,针对Enum类型的特殊的Set数据接口。这种数据结构只能由同一种类型的Enum类型进行创建。

在数据结构内部,它使用了Bit Vectors来辅助操作,因此,操作性能极其高效。
同时,其Iterator是弱一致的(Weakly Consistent)因此针对写操作不会抛出ConcurrentModificationException
Null元素不允许插入,它不是线程安全的。

EnumSet设计为抽象类,因此只能通过静态工厂来进行创建,整个创建过程EnumSet进行了进一步的封装

1
2
3
4
5
6
7
8
Enum<?>[] universe = getUniverse(elementType);
if (universe == null)
throw new ClassCastException(elementType + " not an enum");
if (universe.length <= 64)
return new RegularEnumSet<>(elementType, universe);
else
return new JumboEnumSet<>(elementType, universe);

当Enum元素个数<=64时,返回RegularEnumSet,反之,返回JumboEnumSet

RegularEnumSet

对于RegularEnumSet

使用elements作为位向量,通过每一位来表征Set元素的是否存在

1
2
3
4
5
/**
* Bit vector representation of this set. The 2^k bit indicates the
* presence of universe[k] in this set.
*/
private long elements = 0L;

看下其addAll函数

1
2
3
4
void addAll() {
if (universe.length != 0)
elements = -1L >>> -universe.length;
}

RegularEnumSet使用 -1L >>> -universe.length来进行位向量设置。

这个操作是什么意思?

先从位操作开始,Java的位操作符有三个, << >> >>> 左移,有符号右移,无符号右移。对于无符号右移操作符

Shift Operators

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x1f (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.
If the promoted type of the left-hand operand is long, then only the six lowest- order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & with the mask value 0x3f (0b111111). The shift distance actually used is therefore always in the range 0 to 63, inclusive.

即:左操作符为int时,右操作符只有低5位有效,右操作数会与0x1f做and操作,如果左操作数是long,则右操作数只有低6位有效,会与0xbf做and操作。
但是,左右操作数都是负数又是什么意思?
再从计算机的原码,反码和补码说起,
一个数在计算机中的二进制表示, 叫做这个数的机器数。 机器数用最高位来存放符号,0表示正数,1表示负数。
比如 0000 0001 表示 1, 1000 0001 表示 -1, 00000001 10000001均为机器数。
因为符号位的存在,机器数并非真实数值,即真值,10000001的真值为-1而非129
原码:符号位与真值的绝对值, 0000 0001, 1000 0001
反码:正数的反码为其本身,负数的反码符号位不变,其他位取反,1000 0001 原 = 1111 1110 反
补码:正数的补码为祁本身,负数的补码符号位不变,其他位取反后+1 ,1000 0001 原 = 1111 1110 反 = 1111 1111 补
为什么要有这三种码? 只有原码具有识别含义,符号位的引入会导致机器识别数字的复杂度,期望的结果是符号位参与运算。即补码方式。
回到前面, -1L的,机器数为, 0xffffffffffffffff (补码),>>> 为无符号右移,右移后左侧补零。假设-universe.length = -5,则其机器数为0xfffffffb,由于只有后6位生效,因此其机器数为0x3b = 59,也就是0xffffffffffffffff右移59位,高位补零。其结果为 0…. 01 1111,即低五位为1,即长度为5,5个元素都存在。
-1L >>> -n [1,64],是一个常用技巧,生成长度为n的bit vectors.

1
2
3
4
5
6
7
public boolean add(E e) {
typeCheck(e);
long oldElements = elements;
elements |= (1L << ((Enum<?>)e).ordinal());
return elements != oldElements;
}

1
2
3
4
5
6
7
8
9
10
11
public boolean remove(Object e) {
if (e == null)
return false;
Class<?> eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
long oldElements = elements;
elements &= ~(1L << ((Enum<?>)e).ordinal());
return elements != oldElements;
}

RegularEnumSet的add和remove操作实现就非常容易理解了,及将bit vector对于的bit位设置成0或者1。

JumboEnumSet

对于超过64个元素的Enum,使用long elements作为bit vector显然无法描述,解决办法是,使用long输入,缺多少,补多少个long

1
2
3
4
5
6
/**
* Bit vector representation of this set. The ith bit of the jth
* element of this array represents the presence of universe[64*j +i]
* in this set.
*/
private long elements[];

数组长度如何确定?

1
2
3
4
JumboEnumSet(Class<E>elementType, Enum<?>[] universe) {
super(elementType, universe);
elements = new long[(universe.length + 63) >>> 6];
}

(universe.length+64)>>>6 右移6位 = 除以2^6,即除以64,长度直接除64,显然不对,比如68/64=1,此时显然应该为2,因此,通过+63再进行该除法,从而确定了数组长度。
对于操作:

1
2
3
4
5
6
void addAll() {
for (int i = 0; i < elements.length; i++)
elements[i] = -1;
elements[elements.length - 1] >>>= -universe.length;
size = universe.length;
}

对于addAll,显然,最后一个数组元素之前的所有long,全部置为-1,对于最后一个元素,进行 -1 >>> - universe.length即可(由于只取低6位,不用关注其数值到底多少)

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean add(E e) {
typeCheck(e);
int eOrdinal = e.ordinal();
int eWordNum = eOrdinal >>> 6;
long oldElements = elements[eWordNum];
elements[eWordNum] |= (1L << eOrdinal);
boolean result = (elements[eWordNum] != oldElements);
if (result)
size++;
return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean remove(Object e) {
if (e == null)
return false;
Class<?> eClass = e.getClass();
if (eClass != elementType && eClass.getSuperclass() != elementType)
return false;
int eOrdinal = ((Enum<?>)e).ordinal();
int eWordNum = eOrdinal >>> 6;
long oldElements = elements[eWordNum];
elements[eWordNum] &= ~(1L << eOrdinal);
boolean result = (elements[eWordNum] != oldElements);
if (result)
size--;
return result;
}

对于add和remove操作,首先确定操作元素位于数组的哪个索引 ordinal >>> 6 当前位置除以64获得,然后对确定索引的elements的long进行对应的bit的设置。 对于1L<<eOrdinal (由于只取低6为,不用关注祁具体的数值)

Benchmark

enumset-benchmark
两个Enum,一个26个元素,一个130个元素。

分别循环1000000, 10000000, 80000000进行contains(),add(),remove()操作。

对比EnumSet和传统的Set数据结构的性能:

测试结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Enum Set 26-elements loop 1000000 [ contains ]: 212
Gene Set 26-elements loop 1000000 [ contains ]: 146
Enum Set 26-elements loop 10000000 [ contains ]: 1089
Gene Set 26-elements loop 10000000 [ contains ]: 1074
Enum Set 26-elements loop 80000000 [ contains ]: 3444
Gene Set 26-elements loop 80000000 [ contains ]: 3533
Enum Set 130-elements loop 1000000 [ contains ]: 119
Gene Set 130-elements loop 1000000 [ contains ]: 94
Enum Set 130-elements loop 10000000 [ contains ]: 799
Gene Set 130-elements loop 10000000 [ contains ]: 867
Enum Set 130-elements loop 80000000 [ contains ]: 6202
Gene Set 130-elements loop 80000000 [ contains ]: 7172
Enum Set 26-elements loop 1000000 [ add ]: 87
Gene Set 26-elements loop 1000000 [ add ]: 108
Enum Set 26-elements loop 10000000 [ add ]: 424
Gene Set 26-elements loop 10000000 [ add ]: 570
Enum Set 26-elements loop 80000000 [ add ]: 3640
Gene Set 26-elements loop 80000000 [ add ]: 4161
Enum Set 130-elements loop 1000000 [ add ]: 81
Gene Set 130-elements loop 1000000 [ add ]: 89
Enum Set 130-elements loop 10000000 [ add ]: 830
Gene Set 130-elements loop 10000000 [ add ]: 899
Enum Set 130-elements loop 80000000 [ add ]: 6546
Gene Set 130-elements loop 80000000 [ add ]: 7209
Enum Set 26-elements loop 1000000 [ remove ]: 48
Gene Set 26-elements loop 1000000 [ remove ]: 53
Enum Set 26-elements loop 10000000 [ remove ]: 464
Gene Set 26-elements loop 10000000 [ remove ]: 483
Enum Set 26-elements loop 80000000 [ remove ]: 3631
Gene Set 26-elements loop 80000000 [ remove ]: 3787
Enum Set 130-elements loop 1000000 [ remove ]: 82
Gene Set 130-elements loop 1000000 [ remove ]: 87
Enum Set 130-elements loop 10000000 [ remove ]: 817
Gene Set 130-elements loop 10000000 [ remove ]: 889
Enum Set 130-elements loop 80000000 [ remove ]: 6621
Gene Set 130-elements loop 80000000 [ remove ]: 7136

由于基于Mac个人机进行测试,存在一定的误差,基于80000000的Loop可以看到:

RegularEnumSet

  • contains: 2.5%
  • add: 14.3%
  • remove: 4.3%

JumboEnumSet

  • contains: 15.6%
  • add: 10.1%
  • remove: 7.8%

Random存在耗时,会导致性能更接近,因此,该提升数据存在一定的不精确性,但是可以明显的看到。无论是RegularEnumSet还是Jumbo,均存在明显的性能提升。