且听疯吟如此生活三十年

有些问题可能看起来无所谓,但是开开脑洞还是挺有意思的

比如,最近碰到一个问题,简化形式是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
IEnumerable<int> Range(int n) {
var i = 0;
while (i <= n) {
// DoSomething1...
yield return i;
i++;
}
}

Range(n).ForEach(x => DoSomething2(x));

void DoSomething2(x) {
}

看出问题了么?

  • IEnumerable 接口是没有 ForEach 方法的,ForEachList<T> 的方法,所以只能写成

      
    1
    Enumerable.Range(0, n).ToList().ForEach(x => DoSomething(x));

    但是显然这样就失去了延迟执行的意义了

  • 我们也可以尝试使用 IEnumerableSelect 方法,变成这样:

      
    1
    Enumerable.Range(0, n).Select(x => DoSomething2(x));

    当然这样也行不通,因为我们的 DoSomething2 方法是 void 类型的

  • 最后只能粗暴的给 DoSomething2 包装一个返回值

    1
    Enumerable.Range(0, n).Select(x => { DoSomething2(x); return true; });

如果 IEnumerable 支持 ForEach 方法就好了?

  • 事实上 C# 设计者对此作了解释:“foreach” vs “ForEach”
  • 总之来说,List<T>.ForEachList<T> 本身的方法, Linq 不会提供有副作用的方法,它违反了 Linq side-effect-free 的设计理念
  • Mmm,听起来好像很有道理 :(

当然,这个例子本身不具有太大的意义,但是——

不妨开个脑洞

如果可以用 void 作为泛型参数呢?

  • 这样的代码不再有问题了

    1
    Enumerable.Range(0, n).Select<int, void>(x => DoSomething2(x));
  • 也并没有违反 Linq 的设计理念(当然,取决于你怎么看了 :(

  • 更大的好处在于:
    如果把 void 看作泛型的一种,可以在不增加复杂度的前提下简化一些问题
    比如不需要为 MyClassMyClass<T> 写两次相同的代码了
    因为 MyClass 就相当于 MyClass<void>,我们可以统一所有处理逻辑,不再需要大堆的重载了。


搜索的时候发现有很多大牛讨论过这个问题了,受益匪浅
比如 C#的设计缺陷(2):不能以 void 作为泛型参数

1. tuple and record

现在有一些键值对,它们和给定 record 的项一一对应,如何转换成 record?

1
2
3
4
5
6
-record(test, {
a::binary(),
b::binary()
}).

KeyValuePairs = [{a, <<"a">>},{b, <<"b">>}].

很基础的问题,我们这样做:

1
2
3
4
Result = #test{
a = get_value(a, KeyValuePairs),
b = get_value(a, KeyValuePairs)
}.

如果 record 有一百个项呢?
重复的写 a = get_value(a, KeyValuePairs) 这样的代码一百次大概会让人怀疑「猿」生吧 :(

虽然 Erlang 并没有提供动态生成 record 的方法,但是我们知道

  • Erlang 的 record 实际上是用 tuple 来表示的,即 #test{a = <<"a">>, b = <<"b">>} 实际上是 {test, <<"a">>, <<"b">>}
  • 所有在运行时对 record 的操作实际上都是对 tuple 的操作
  • Result#test.a 实际上是 tuple 的 index
  • 可以使用 record_info(fields, record) 获取 Record 的 fields 信息

所以我们可以这样

1
2
3
4
5
Result = list_to_tuple([test |
[get_value(X, KeyValuePairs) || X <- record_info(fields, test)]]).

Result#test.a.
%% <<"a">>

2. record_info

很容易想到,我们要是把处理函数抽象出来,不是多了一个 kvpairs_to_record 的接口了么?

1
2
3
4
-spec kvpairs_to_record(kvpairs(), atom()) -> rec().
kvpairs_to_record(KeyValuePairs, Record) ->
list_to_tuple([Record |
[get_value(X, KeyValuePairs) || X <- record_info(fields, Record)]]).

很遗憾,行不通。编译的时候会报出 illegal record info 错误。

WTF?

  • record_info 并不是一个通常意义上的 BIF,它不能接受变量
  • 其原因在于 record structure 只存在于编译期,在运行时是不可见的,编译完成后,record 就已经被表示成为 tuple 了,自然没有办法在运行时再获取 record info 了

所以你只能这么「曲线救国」了

1
2
3
4
kvpairs_to_record(KeyValuePairs, Record, RecordInfo) ->
list_to_tuple([Record | [get_value(X, KeyValuePairs) || X <- RecordInfo]]).

Result = kvpairs_to_record(KeyValuePairs, test, record_info(fields, test)).

3. macro and record

所以就这样放弃了?
当然不,为了「代码洁癖」我们可以「不择手段」。
考虑到 define macro 也是编译期的,我们可以这样 trick

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
-module(test).
-export([do/0]).

-define(fuxk(Record, Val),
fun() ->
list_to_tuple([Record | [get(X, Val)
|| X <- record_info(fields, Record)]])
end
).

-record(test, {
a :: binary(),
b :: binary()
}).

do() ->
KV = [{a, <<"a">>},{b, <<"b">>}],
Result = ?fuxk(test, KV)(),
Result#test.a.
% <<"a">>

get(Key, KeyValuePairs) ->
proplists:get_value(Key, KeyValuePairs, undefined).

Goodness gracious - it works!

4. beam and record

当然像上面那样写实际上也没有好多少,依然还是不完美。
如果一定需要在运行时得到 record info 呢?
比如我们热升级代码,需要更新 record 定义怎么办?

幸好,record structure 会被写入到 beam 中,我们只需要 load beam 然后解析它,还是可以达到运行时获取 record info 的效果的。
具体实现可以参考 https://github.com/esl/parse_trans

当然,除非知道自己在做什么,否则不推荐这么做。

5. 最后

实际上我很好奇为什么 Erlang 不提供运行时访问 record structure 呢?信息已经存在于 beam 中了,实现一下不难吧。
最后,如果不需要考虑兼容,**推荐使用 map 来替代 record**,map 在运行时数据结构可见并且可以增删成员。

mptt

1. 预排序遍历树算法

  • mptt (Modified Preorder Tree Traversal)[^1]
  • 优点
    查询效率高,只需要一次查询即可获得层级结构中某个节点的所有子节点,无需递归查询
  • 缺点
    插入、删除、移动节点效率较低
  • 适用
    在传统关系数据库中实现层级树结构
    • 读压力 > 写压力, mptt 算法可以提高效率
    • 写压力 > 读压力,使用传统的邻接表 (adjacency list model)

2. 增删查改

  • Create

    • 假设增加的节点为 c, 该节点前一节点为 p
    • 节点 c 左值为 p 的右值 +1,右值为 p 右值 +2
    • 所有左值大于节点 c 的左值的节点,其左值均 +2
    • 所有右值大于节点 c 的右值的节点,其右值均 +2
    • 写入节点 c 到数据库
    1
    2
    3
    4
    SELECT @cRight := rgt FROM mptt	WHERE name = 'p';
    UPDATE mptt SET rgt = rgt + 2 WHERE rgt > @cRight ;
    UPDATE mptt SET lft = lft + 2 WHERE lft > @cRight ;
    INSERT INTO mptt(name, lft, rgt) VALUES('c', @cRight+ 1, @cRight+ 2);
  • Read

    • 查询节点 c 的子节点:

      • 查询所有左值大于 c 的左值且右值小于 c 的右值的节点

        1
        SELECT * FROM mptt WHERE lft BETWEEN @cLeft and @cRight;
    • 查询节点 c 的父节点:

      • 查询所有左值小于 c 的左值且右值大于 c 的右值(或左值)的节点

        1
        SELECT * FROM mptt WHERE lft < @cLeft and rgt > @cLeft;
    • 节点 c 的子节点个数:

      • (c.right - c.left - 1) / 2
  • Update
    移动节点即:

    • 删除节点
    • 在指定位置新增节点
  • Delete

    • 删除节点 c
    • 所有右值大于 c 右值的节点,右值 -2
    • 所有左值大于 c 左值的节点,左值 -2
    1
    2
    3
    DELETE FROM mptty WHERE lft BETWEEN @cLeft AND @cRight;
    UPDATE mptt SET rgt = rgt - 2 WHERE rgt > @cRight;
    UPDATE mptt SET lft = lft - 2 WHERE lft > @cLeft;

3. 重建树结构

很容易推断,对排序好的 mptt tree,仅需要一次遍历,即可根据所有节点的左右值记录重建树结构
以 python 为例:

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
# Node class
class Node(object):

def __init__(self, left, right):
super(Node, self).__init__()
self.left = left
self.right = right
self.depth = 1
self.children = []

# arg: Node List
def rebuild(l):
# 节点按左值排序,即遍历顺序
l.sort(key=lambda x: x.left)

# 使用列表暂存每层子树的父节点
# 如 pi[0] 表示第 2 层的节点的父节点在 l 中的 index
pi = [0]

for i, c in enumerate(l):
if c.left != 1:
p = l[i - 1]

# 使用 c 表示此节点,p 表示 c 的前一节点
# 如果连续的两个节点 c 和 p 的左值增加幅度为 1,则说明其深度增加了 1
# 且 p 为 c 及 c 的兄弟节点的父节点
if c.left == p.left + 1:
c.depth = p.depth + 1
if c.depth - 1 > len(pi):
pi.append(i - 1)
else:
pi[c.depth - 2] = i - 1

# 如果 c 的左值大于 p 的父节点的右值,则说明 p 与 c 并非兄弟节点
# 并可以计算出两节点的深度差为 c 的左值与 p 的右值之差减 1
elif c.left > l[pi[p.depth - 2]].right:
c.depth = p.depth - (c.left - p.right - 1)

# 不满足以上两个条件,说明 c 是 p 的兄弟节点
else:
c.depth = p.depth

# 将 c 作为 pi 中记录的父节点的子节点
l[pi[c.depth - 2]].children.append(c)

return l

Update

完整代码及生成 Json 和基于 D3.js[^2] 的树状图:
https://gist.github.com/caoyue/704e472215af29b08a27

[^1]: [1] http://www.sitepoint.com/hierarchical-data-database-2
[^2]: [2] http://d3js.org

对这些概念头疼了很久,尝试简单的整理下,不确切的地方欢迎指正~

1. Unicode

  • Unicode 是一个字符集,而不是一种编码方案
  • 简单来说 Unicode 是希望给地球上每一个字符一个数字编号,从而解决不同编码之间不统一的问题
  • Unicode 是没法直接拿来用的,我们使用的是它的编码方案

2. 编码方案

  • 通常使用的 UTF-8UTF-16 等等都是 Unicode 的编码方案
  • 所谓编码方案就是按一定的规则对 Unicode 的字符编号进行编码
  • 当然不同的编码的同一个字符,最后解析成 Unicode 字符编号都是一样的

3. 字体与 Unicode

  • 计算机使用字符的 Unicode 编号去寻找字体内的字符
  • 字体内部的特殊数据结构存储了 Unicode 编号和字符的对应关系

4. 例子

  • 汉字 的 Unicode 编号 10 进制为 26376
  • Unicode 编号表示为 16 进制 是 U+6708
  • 在 python 中用 u"\u6708" 表示
  • 在 UTF-8 中的编码是 0xE6 0x9C 0x88 ,使用了 3 个 Byte 来表示

5. UTF-8 和 Unicode 转换

  • Unicode 转 UTF-8

    • 汉字 的 Unicode 是 26376,转换为二进制是 1100111 00001000
    • 根据值大于 0x800 小于 0x10000 可以判断为三字节存储
    • 将 Unicode 二进制从低位往高位取出二进制数字,每次取 6 位,并按一定的规则进行填补

    转换

    110 011100 001000
    11100110 10011100 10001000
    0xE6 0x9C 0x88

  • UTF-8 转 Unicode
    同理进行逆运算即可

6. 遗留编码

  • ASCIIGB 2312Big5GBKGB 18030 这些都属于遗留编码方案
  • GB 2312 通常认为是字符集编码方案一体的
  • 将 GB 2313 编码转换为 Unicode 编号,需要通过转换表查询,无法像 UTF-8 一样直接根据编码规则转换

6. 编译并运行程序

  • (略)

7. 并发

  • 机制
    • Erlang 程序由成百上千个 Process 组成,这些 Process 之间可以互发消息
    • Process 能否接收到或者理解消息是不确定的,要知道结果必须向该 Process 发送消息询问并等待
    • Process 之间可以互相 Link ,当 Process 消亡时与之相连的 Process 会收到消息

8. 并发编程

  • 并发原语

    • Pid = spawn(Module, FuncName, Args)
      创建一个新的 Process,用于对 Func 求值,并返回该 Process 的 pid
    • Pid ! Message
      • 向指定 Pid 的 Process 发送消息,返回值为 Message 本身
      • 消息发送是异步的,无需等待即可进行其他操作
    • receive ... end
      • 接收一个发给当前进程的消息
    • self()
      获取自己的 pid
  • 注册进程

    • register(AnAtom, Pid)
    • unregiseter(AnAtom)
      进程死亡时会自动 unregiseter
  • 编写并发程序的一般模式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    -module (concurrency).
    -compile(export_all).

    start() ->
    spawn(?MODULE, loop, []).

    rpc(Pid, Request) ->
    Pid ! {self(), Request},
    receive
    {Pid, Response} ->
    {Pid, Response}
    end.

    loop(X) ->
    receive
    {From, Any} ->
    From ! {self(), "Received!"},
    io:format("Received: ~p~n", [Any]),
    loop(X)
    end.
    1
    2
    3
    4
    5
    6
    %% run in erlang shell
    Pid = concurrency:start().
    %% <0.33.0>
    concurrency:rpc(Pid, "test!")
    %% Received: "test"
    %% {<0.56.0>,"Received!"}

4. 异常

  • 抛出异常

    • 显式的 exit(Why)
      • 终止当前 Process
      • 如果当前 Process 未捕获这个异常,则系统会向所有 link 该 Process 的 Process 广播 {'EXIT', Pid, Why} 消息
    • 显式的 throw(Why)
      • 抛出供其调用者捕获的异常
      • 最好是添加注释说明抛出的异常
      • 如何处理由调用者选择,包括忽略
    • 系统错误 erlang:error(Why)
  • try..catch 捕获异常

    • try/catch 本身会消耗一点性能

    • 推荐的 try/catch 风格

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      %% 首先对 FuncOrExpressionSequence 求值
      %% 如果没有产生异常则顺序进行 Patterm 匹配, 匹配成功后执行后面的表达式
      %% 如果有异常抛出, 则顺序匹配 ExPattern(ExceptionType 是 throw、exit、error 中的一个, 默认为 throw)
      %% after 块中的代码用于清理工作,绝对会执行
      %% after 可以省略
      try FuncOrExpressionSequence of
      Pattern1 [when Guard1] ->Expressions1;
      Pattern2 [when Guard2] ->Expressions2;
      ...
      catch
      ExceptionType: ExPattern1 [when ExGuard1] ->ExExpressions1;
      ExceptionType: ExPattern2 [when ExGuard2] ->ExExpressions2;
      ...
      after
      AfterExpressions
      end.
  • 栈跟踪

    • 在触发异常的时候可以调用 erlang:get_stacktrace/0 来查看最近的栈跟踪信息,可以获得异常函数的调用路径(尾递归调用除外)

      1
      2
      3
      4
      5
      try func()
      catch
      error: X ->
      {X, erlang:get_stacktrace()}
      end.

5. 顺序型编程进阶

  • BIF (built-in function)

    • binary

      • 相对于 List 活着 tuple , binary 更节省内存,输入输出更为高效

      • binary_to_term/term_to_binary 可将任何的 binary 和 Erlang 值(List、atom、tuple 甚至 binary 等)转换成为 binary,但是这个 binary 是以所谓的 「外部数据格式」 存储的,类似于其他语言的序列化与反序列化)

        1
        2
        3
        A = <<1,2,3>>.
        B = term_to_binary(A).
        %% <<131,109,0,0,0,3,1,2,3>>
      • binary 中的数字,每一个都在 0~255 之间(因为每一个数字表示一个 byte,其值在 0000 0000 ~ 1111 1111 [0 ~ 29 -1] 之间)

      • GB2312 的汉字转成 UTF-8 时,绝大多数是 3 个字节

        1
        2
        A = <<"且听疯吟"/utf8>>.
        %% <<228,184,148,229,144,172,231,150,175,229,144,159>>
    • bit 语法

      • 封包与解包

        • 以 RGB 色彩为例:
          创建一个 16 bit (2 byte)的内存块,存放一个 RGB 三元组,并为 Red 分配 5 bit,为 Green 分配 6 bit,为 Blue 分配 5 bit

          1
          2
          3
          4
          5
          6
          7
          8
          Red = 2,
          Green = 60,
          Blue = 29,
          RGB = <<Red:5, Green:6, Blue:5>>.
          %% <<23, 157>>
          <<R1:5, G1:6, B1:5>> = RGB.
          {R1, G1, B1}.
          %% {2, 60, 29}
        • 注意取值范围。比如我们为 Blue 分配了 5 bit,但是为 Blue 赋值 61,转换成二进制为 111101,超过了 5 bit,则会发生截断,取低五位,即实际值为 29

          1
          2
          3
          4
          5
          6
          7
          integer_to_list(61,2).
          %% "111101"
          integer_to_list(29,2).
          %% "11101"

          <<2:5,60:6,61:5>> == <<2:5,60:6,29:5>>.
          %% true
      • bit 语法表达式
        • 形如 <<E1, E2, E3, ... , En>>
        • 每一个元素都是二进制数据中的一个区块
        • 元素的值表示有下面几种方式
          • Value
          • Value:Size
          • Value/TypeSpecifierList
          • Value:Size/TypeSpecifierList
        • 其中 TypeSpecifierList 是形如 End-Sign-Type-Unit 组成的字符串,其中不同的 Type 选项如下,每一个都可以忽略且没有顺序要求:
          • End = big / native / little
            决定字节序,默认 big
          • Sign = signerd / unsigned
            仅用于模式匹配,默认 unsigned
          • Type = integer/ float / binary
            默认 integer
          • Unit = 1 / 2 / 3 / ... / 255
            • 整个区块长度为 Size * Unit,其值必须大于或等于 0 且是 8 的倍数
            • 其值依赖于 Type,如果 Type 是 integer 或者 float,则值为 1 ,是 binary 则值为 8
      • binary 模式匹配
    • apply

      • apply(Module, Func, [Arg1, Arg2, ... , Argn])
      • 对于参数个数已知的函数,M:Func([Arg1, Arg2, ... , Argn]) 的调用优于 apply
      • 使用 apply 调用的函数编译器无法优化,同时许多分析工具也无法分析其细节
      • 如无必要尽量少用 apply
    • 属性

      • module
      • import
      • export
      • compile
        • 编译器选项,常用的 -compile(export_all).
      • vsn
        无语法意义,用于文档分析
      • 用户定义属性 -SomeTag(Value)
        • 该值会被编译进模块
        • 该值可以在运行时使用 attrs:module_info() 提取
        • beam_lib 提供了一系列不加载模块代码就能分析的函数
    • 块表达式
      把多个表达式组织为单个表达式

      1
      2
      3
      4
      5
      6
      begin
      Expression1,
      Expression2,
      ...
      ExpressionN
      end
    • 布尔

      • Erlang 中不存在布尔类型,通常使用原子 true/false 代替作为布尔符号使用
      • 布尔表达式:and / not / or / xor
    • 字符集

      • Erlang 默认编码为 ISO-8859-1 (Latin-1)
      • Erlang 内部没有字符串数据类型,而是用一串整数列表表示
      • 因此要注意 Unicode 字符的处理
      • 使用 unicode 模块中如 unicode:characters_to_list 的函数处理 unicode 字符
    • epp

      • Erlang 预处理器,扩展宏,插入必须的包含文件等
    • 转义字符

    • 表达式/表达式序列

      • 表达式序列的值为序列中最后一个表达式的值
    • 函数引用

    • 包含文件

      • include
      • include_lib
    • 列表操作符

      • ++
        • 列表添加 ListA ++ ListB
          即把 ListB 附加到 ListA 尾部
        • 模式匹配中的 ++
          f("begin" ++ T) -> ... 即相当于模式匹配 [$b, $e, $g, $i, $n | T]
      • --
        列表删除 ListA -- ListN ,即从 ListA 中删除 ListB 中的所有元素,若元素 E 在 B 中重复出现 k 次,则只会从 ListA 中按顺序删除 k 个 E
      • 定义
        • 不带参数 -define(Macro, ...)
        • 带参数 -define(Macro(X,Y), ...)
        • 预定义宏
          • ?FILE 当前文件名
          • ?MODULE 当前模块名
          • ?LINE 当前行号
      • 宏的流程控制
        • -undef(Macro) 取消宏定义,在此语句后无法使用该宏
        • ifdef / ifndef / else / end
        • 结合调试标志,扩展 debug 日志输出等
    • 数值类型

      • 整型
        • 整型的计算是精确的
        • 其计算结果代表的数据长度只受限于可用内存
        • 表示法
          • 传统表示法,1, 1989, -1337
          • K 进制整数,2#01001011,16#fe34
      • 浮点型
        • 内部以 IEEE 754 的 64 bit 格式表示
    • 操作符优先级

    • 进程字典

      • 每一个 Erlang Process 都有自己的进程字典

      • 实际上提供的功能类似于全局变量

      • 由于不是非破坏性赋值,会导致代码有副作用

      • 尽量少用

      • 添加/获取进程字典

        1
        2
        3
        4
        @spec put(Key, Value) -> OldValue | undefined.
        @spec get(Key) -> Value | undefined.
        @spec get() -> [{Key, Value}].
        ...
    • 引用
      使用 BIF erlang:make_ref() 创建引用