第4章使用元組 · Erlang并發編程（試讀）

# 第4章使用元組 | 翻譯: | 王飛 | |-----|-----| | 校訂: | 連城 | 元組用以將多個對象組合成一個新的復雜對象。對象{E1,E2,E3,...En}表示一個**大小為 n 的元組**。元組用于描述包含**固定**數目的元素的數據結構；對于**可變**數目的元素，應該使用**列表**來存儲。 ### 處理元組的BIF 以下是一些可以用來操縱元組的BIF： tuple_to_list(T) > > 將元組T轉化成一個列表。 > 如：tuple_to_list({1,2,3,4})?[1,2,3,4]。 list_to_tuple(L) > > 將列表L轉化成一個元組。 > 如：list_to_tuple([a,b,c])?{a,b,c}。 element(N,T) > > 返回元組T的第N個元素。 > 如：element(3,{a,b,c,d})?c。 setelement(N,T,Val) > > 返回一個新的元組，這個元組是將元組T的第N個元素用Val替換之后的一個拷貝。 > 如：setelement(3,{a,b,c,d},xx)?{a,b,xx,d}。 size(T) > > 返回元組T包含的元素個數。 > 如：size({a,b,c})?3 。 ### 返回多個值我們經常想讓一個函數返回多個值，使用元組來實現這一目的是十分方便的。例如，函數parse_int(List)從一個由ASCII字符構成的列表List中提取最開始的數字，如果存在，就返回一個由被提取出來的數字和列表剩下的部分組成的元組，如果列表中沒有數字的話，就返回原子式eoString。 ~~~ parse_int(List) -> parse_int(skip_to_int(List), 0). parse_int([H|T], N) when H >= $0, H =< $9 -> parse_int(T, 10 * N + H - $0); parse_int([], 0) -> eoString; parse_int(L, N) -> {N,L}. ~~~ skip_to_int(L)返回L中第一個以ASCII字符0到9中的任意一個開始的子列表。 ~~~ skip_to_int([]) -> []; skip_to_int([H|T]) when H >= $0, H =< $9 -> [H|T]; skip_to_int([H|T]) -> skip_to_int(T). ~~~ 如果我們使用字符串"abcd123def"（"abcd123def"的列表形式是[97,98,99,49,50,51,100,101,102]）來測試parse_int： ~~~ > tuples:parse_int("abc123def"). {123,[100,101,102]}} ~~~ 在parse_int的基礎上，可以實現一個提取所有嵌入在字符串里面的數字的解釋器。 ~~~ parse_ints([]) -> []; parse_ints(L) -> case parse_int(L) of eoString -> []; {H,Rest} -> [H|parse_ints(Rest)] end. ~~~ 因此： ~~~ > tuples:parse_ints("abc,123,def,456,xx"). [123,456] ~~~ ### 密碼加密幾乎每天筆者們都不得不記住許多不同的密碼——信用卡的密碼，門禁密碼等等。這些密碼可以用一種方法記錄下來，并且不會被犯罪分子利用嗎？假設我們有一張密碼為3451的LISA信用卡，它的密碼可以像這樣被編碼： ~~~ a b c d e f g h i j k l m n o p q r s t u v w x y z 1 0 5 3 4 3 2 7 2 5 4 1 9 4 9 6 3 4 1 4 1 2 7 8 5 0 lisa ~~~ 這樣密碼就可以寫在一張紙上，即使這張紙落在他人手上，密碼也是安全的。我們如何解碼信息呢？用來加密密碼的密鑰是公開的——因此我們可以很容易地讀出密碼（3451）–試試看！我們很容易的就可以構造一個用來執行加密的函數encode(Pin,Password)[[1]](#)： ~~~ encode(Pin, Password) -> Code = {nil,nil,nil,nil,nil,nil,nil,nil,nil, nil,nil,nil,nil,nil,nil,nil,nil,nil, nil,nil,nil,nil,nil,nil,nil,nil}, encode(Pin, Password, Code). encode([], _, Code) -> Code; encode(Pin, [], Code) -> io:format("Out of Letters~n",[]); encode([H|T], [Letter|T1], Code) -> Arg = index(Letter) + 1, case element(Arg, Code) of nil -> encode(T, T1, setelement(Arg, Code, index(H))); _ -> encode([H|T], T1, Code) end. index(X) when X >= $0, X =< $9 -> X - $0; index(X) when X >= $A, X =< $Z -> X - $A. ~~~ 我們看一下以下的例子： ~~~ > pin:encode("3451","DECLARATIVE"). {nil,nil,5,3,4,nil,nil,nil,nil,nil,nil,1,nil,nil,nil, nil,nil,nil,nil,nil,nil,nil,nil,nil,nil,nil} ~~~ 我們現在使用隨機數來替換沒有被填充的nil元素： ~~~ print_code([], Seed) -> Seed; print_code([nil|T], Seed) -> NewSeed = ran(Seed), Digit = NewSeed rem 10, io:format("~w ",[Digit]), print_code(T, NewSeed); print_code([H|T],Seed) -> io:format("~w ",[H]), print_code(T, Seed). ran(Seed) -> (125 * Seed + 1) rem 4096. ~~~ 然后我們需要一些小函數將所有東西連接在一起： ~~~ test() -> title(), Password = "DECLARATIVE", entries([{"3451",Password,lisa}, {"1234",Password,carwash}, {"4321",Password,bigbank}, {"7568",Password,doorcode1}, {"8832",Password,doorcode2}, {"4278",Password,cashcard}, {"4278",Password,chequecard}]). title() -> io:format("a b c d e f g h i j k l m \ n o p q r s t u v w x y z~n",[]). entries(List) -> {_,_,Seed} = time(), entries(List, Seed). entries([], _) -> true; entries([{Pin,Password,Title}|T], Seed) -> Code = encode(Pin, Password), NewSeed = print_code(tuple_to_list(Code), Seed), io:format(" ~w~n",[Title]), entries(T, NewSeed). ~~~ 最后我們可以運行這個程序了： ~~~ 1> pin:test(). a b c d e f g h i j k l m n o p q r s t u v w x y z 1 0 5 3 4 3 2 7 2 5 4 1 9 4 9 6 3 4 1 4 1 2 7 8 5 0 lisa 9 0 3 1 2 5 8 3 6 7 0 4 5 2 3 4 7 6 9 4 9 2 7 4 9 2 carwash 7 2 2 4 3 1 2 1 8 3 0 1 5 4 1 0 5 6 5 4 3 0 3 8 5 8 bigbank 1 0 6 7 5 7 6 9 4 5 4 8 3 2 1 0 7 6 1 4 9 6 5 8 3 4 doorcode1 1 4 3 8 8 3 2 5 6 1 4 2 7 2 9 4 5 2 3 6 9 4 3 2 5 8 doorcode2 7 4 7 4 2 5 6 5 8 5 8 8 9 4 7 6 5 0 1 2 9 0 9 6 3 8 cashcard 7 4 7 4 2 7 8 7 4 3 8 8 9 6 3 8 5 2 1 4 1 2 1 4 3 4 chequecard true ~~~ 之后這些信息可以用很小的字體打印出來，粘在一張郵票的背后，藏在你的領帶里面[[2]](#)。 ### 字典我們將一組鍵惟一的鍵—值（Key-Value）對定義為字典[[3]](#)。存在字典里的值可能會重復。對Key和Value的數據類型都沒有限制，但是只能通過Key來查詢字典。我們定義一下字典操作： new() > 創建并返回一個空字典。 lookup(Key,Dict) > 在字典Dict中查找一個Key-Value對，如果找到則返回{value,Value}，否則返回undefined。 add(Key,Value,Dict) > 添加一個新的Key-Value對到字典Dict中，并返回一個新的字典，以反映add函數對字典造成的改變。 delete(Key,Dict) > 從字典Dict里刪除Key所對應的Key-Value對，并返回一個新的字典。程序4.1展示了一個字典是怎樣將Key-Value對以元組的形式存放到列表里面的。它并不是實現一個字典最好的方法，在這里它只是一個例子。程序4.1 ~~~ -module(dictionary). -export([new/0,lookup/2,add/3,delete/2]). new() -> []. lookup(Key, [{Key,Value}|Rest]) -> {value,Value}; lookup(Key, [Pair|Rest]) -> lookup(Key, Rest); lookup(Key, []) -> undefined. add(Key, Value, Dict) -> NewDict = delete(Key, Dict), [{Key,Value}|NewDict]. delete(Key, [{Key,Value}|Rest]) -> Rest; delete(Key, [Pair|Rest]) -> [Pair|delete(Key, Rest)]; delete(Key, []) -> []. ~~~ 我們用字典來構建和管理一個包含了各位作者鞋碼的小型數據庫： ~~~ D0 = dictionary:new(). [] > D1 = dictionary:add(joe, 42, D0). [{joe,42}] > D2 = dictionary:add(mike, 41, D1). [{mike,41},{joe,42}] > D3 = dictionary:add(robert, 43, D2). [{robert,43},{mike,41},{joe,42}] > dictionary:lookup(joe, D3). {value,42} > dictionary:lookup(helen, D3). undefined ... ~~~ ### 非平衡二叉樹字典適合保存少量的數據項，但是當項的數量不斷增加，更好的方法是用通過使用鍵的序列關系來訪問數據的樹形結構來組織數據。這種結構的訪問時間與它所包含的項的數量成對數關系–列表是線性的訪問時間。我們認為最簡單的樹組織形式是**非平衡二叉樹**。樹內部的結點用{Key,Vlue,Smaller,Bigger}來表示。Value是被存儲在樹的一些結點中對象的值，它的鍵為Key。Smaller是一棵子樹，它的所有結點的鍵值都小于Key，Bigger也是一棵子樹，它的所有結點的鍵值都大于或等于Key。樹的葉子用原子式nil表示。我們從lookup(Key,Tree)函數開始，這個函數搜索Tree以確定樹中是否有與Key相關的項。 ~~~ lookup(Key, nil) -> not_found; lookup(Key, {Key,Value,_,_}) -> {found,Value}; lookup(Key, {Key1,_,Smaller,_}) when Key < Key1 -> lookup(Key, Smaller); lookup(Key, {Key1,_,_,Bigger}) when Key > Key1 -> lookup(Key, Bigger). ~~~ 函數insert(Key,Value,OldTree)將數據Key-Value添加到樹OldTree中，并返回一棵新樹。 ~~~ insert(Key, Value, nil) -> {Key,Value,nil,nil}; insert(Key, Value, {Key,_,Smaller,Bigger}) -> {Key,Value,Smaller,Bigger}; insert(Key, Value, {Key1,V,Smaller,Bigger}) when Key < Key1 -> {Key1,V,insert(Key, Value, Smaller),Bigger}; insert(Key, Value, {Key1,V,Smaller,Bigger}) when Key > Key1 -> {Key1,V,Smaller,insert(Key, Value, Bigger)}. ~~~ 第一個子句得到數據，并插入到一棵新樹當中，第二個子句將復寫已經存在的結點，第三個和第四個子句確定當Key的值小于、大于或等于樹中當前結點的Key時，應該采取什么樣的行為。當構建了一棵樹之后，我們會想用一種方法將這棵樹的結構打印出來。 ~~~ write_tree(T) -> write_tree(0, T). write_tree(D, nil) -> io:tab(D), io:format('nil', []); write_tree(D, {Key,Value,Smaller,Bigger}) -> D1 = D + 4, write_tree(D1, Bigger), io:format('~n', []), io:tab(D), io:format('~w ===> ~w~n', [Key,Value]), write_tree(D1, Smaller). ~~~ 我們可以用一個測試函數將數據插入到樹中，并把它打印出來： ~~~ test1() -> S1 = nil, S2 = insert(4,joe,S1), S3 = insert(12,fred,S2), S4 = insert(3,jane,S3), S5 = insert(7,kalle,S4), S6 = insert(6,thomas,S5), S7 = insert(5,rickard,S6), S8 = insert(9,susan,S7), S9 = insert(2,tobbe,S8), S10 = insert(8,dan,S9), write_tree(S10). ~~~ 圖4.1 一棵非平衡二叉樹 ~~~ nil 12 ===> fred nil 9 ===> susan nil 8 ===> dan nil 7 ===> kalle nil 6 ===> thomas nil 5 ===> rickard nil 4 ===> joe nil 3 ===> jane nil 2 ===> tobbe nil ~~~ 注意這棵樹并不是十分“平衡”。按照嚴格的順序插入鍵的隊列，比如像這樣： ~~~ T1 = nil, T2 = insert(1,a,T1), T3 = insert(2,a,T2), T4 = insert(3,a,T3), T5 = insert(4,a,T4), ... T9 = insert(8,a,T8). ~~~ 使這棵樹看起來變成了一個列表（見圖4.2）。當鍵的順序隨機的時候，我們使用的方法是很好的。如果在一個插入序列里，鍵是有序排列的，這棵樹就變成了一個列表。我們將在第??章講述怎樣構建平衡二叉樹。圖4.2 變化后的非平衡二叉樹 ~~~ nil 8 ===> a nil 7 ===> a nil 6 ===> a nil 5 ===> a nil 4 ===> a nil 3 ===> a nil 2 ===> a nil 1 ===> a nil ~~~ 我們也需要能夠刪除二叉樹內的元素： ~~~ delete(Key, nil) -> nil; delete(Key, {Key,_,nil,nil}) -> nil; delete(Key, {Key,_,Smaller,nil}) -> Smaller; delete(Key, {Key,_,nil,Bigger}) -> Bigger; delete(Key, {Key1,_,Smaller,Bigger}) when Key == Key1 -> {K2,V2,Smaller2} = deletesp(Smaller), {K2,V2,Smaller2,Bigger}; delete(Key, {Key1,V,Smaller,Bigger}) when Key < Key1 -> {Key1,V,delete(Key, Smaller),Bigger}; delete(Key, {Key1,V,Smaller,Bigger}) when Key > Key1 -> {Key1,V,Smaller,delete(Key, Bigger)}. ~~~ 當要刪除的結點是樹中的葉子，或者在這個結點下面只有一顆子樹時，刪除操作是很容易的（子句1到4）。子句6和7中，要刪除的結點并沒有被確定位置，而是繼續在合適的子樹中向前搜索。在子句5當中，要刪除的結點被找到，但是它是樹中的一個內部結點（例如結點同時有Smaller和Bigger子樹）。這種情況下,Smaller子樹中具有最大鍵的結點將被刪除，并且整棵樹在這個點重建。 ~~~ deletesp({Key,Value,nil,nil}) -> {Key,Value,nil}; deletesp({Key,Value,Smaller,nil}) -> {Key,Value,Smaller}; deletesp({Key,Value,Smaller,Bigger}) -> {K2,V2,Bigger2} = deletesp(Bigger), {K2,V2,{Key,Value,Smaller,Bigger2}}. ~~~ ### 平衡二叉樹在前面幾節里，我們學會了怎樣構建一棵非平衡二叉樹。但不幸的是非平衡二叉樹可能會變成一個列表，這樣對樹的插入和刪除操作就是非隨機的了。一個更好的方法是保持樹在任何情況下都是**平衡**的。 Adelsom-Velskii和Landis [?]（在[?]中描述）使用一個簡單的標準來衡量**平衡**這個概念：如果一棵樹的每個結點的兩個子樹高度之差不超過1，我們就說這棵樹是平衡的。具有這種特性的樹常常被稱作*AVL*樹。平衡二叉樹能夠在O(logN)的時間規模里完成查找、插入和刪除操作，N是樹中結點的個數。假設我們用元組{Key,Value,Height,Smaller,Bigger}表示一棵 AVL樹，用{_,_,0,_,_}表示一棵空樹。然后在樹中的查找操作就很容易實現了： ~~~ lookup(Key, {nil,nil,0,nil,nil}) -> not_found; lookup(Key, {Key,Value,_,_,_}) -> {found,Value}; lookup(Key, {Key1,_,_,Smaller,Bigger}) when Key < Key1 -> lookup(Key,Smaller); lookup(Key, {Key1,_,_,Smaller,Bigger}) when Key > Key1 -> lookup(Key,Bigger). ~~~ lookup的代碼和非平衡二叉樹中的基本一樣。插入操作這樣實現： ~~~ insert(Key, Value, {nil,nil,0,nil,nil}) -> E = empty_tree(), {Key,Value,1,E,E}; insert(Key, Value, {K2,V2,H2,S2,B2}) when Key == K2 -> {Key,Value,H2,S2,B2}; insert(Key, Value, {K2,V2,_,S2,B2}) when Key < K2 -> {K4,V4,_,S4,B4} = insert(Key, Value, S2), combine(S4, K4, V4, B4, K2, V2, B2); insert(Key, Value, {K2,V2,_,S2,B2}) when Key > K2 -> {K4,V4,_,S4,B4} = insert(Key, Value, B2), combine(S2, K2, V2, S4, K4, V4, B4). empty_tree() -> {nil,nil,0,nil,nil}. ~~~ 思路是找到要插入的項將被插入到什么地方，如果插入使得樹變得不平衡了，那么就平衡它。平衡一棵樹的操作通過combine函數實現[[4]](#)。 ~~~ combine({K1,V1,H1,S1,B1},AK,AV, {K2,V2,H2,S2,B2},BK,BV, {K3,V3,H3,S3,B3} ) when H2 > H1, H2 > H3 -> {K2,V2,H1 + 2, {AK,AV,H1 + 1,{K1,V1,H1,S1,B1},S2}, {BK,BV,H3 + 1,B2,{K3,V3,H3,S3,B3}} }; combine({K1,V1,H1,S1,B1},AK,AV, {K2,V2,H2,S2,B2},BK,BV, {K3,V3,H3,S3,B3} ) when H1 >= H2, H1 >= H3 -> HB = max_add_1(H2,H3), HA = max_add_1(H1,HB), {AK,AV,HA, {K1,V1,H1,S1,B1}, {BK,BV,HB,{K2,V2,H2,S2,B2},{K3,V3,H3,S3,B3}} }; combine({K1,V1,H1,S1,B1},AK,AV, {K2,V2,H2,S2,B2},BK,BV, {K3,V3,H3,S3,B3} ) when H3 >= H1, H3 >= H2 -> HA = max_add_1(H1,H2), HB = max_add_1(HA,H3), {BK,BV,HB , {AK,AV,HA,{K1,V1,H1,S1,B1},{K2,V2,H2,S2,B2}}, {K3,V3,H3,S3,B3} }. max_add_1(X,Y) when X =< Y -> Y + 1; max_add_1(X,Y) when X > Y -> X + 1. ~~~ 打印一棵樹也很簡單: ~~~ write_tree(T) -> write_tree(0, T). write_tree(D, {nil,nil,0,nil,nil}) -> io:tab(D), io:format('nil', []); write_tree(D, {Key,Value,_,Smaller,Bigger}) -> D1 = D + 4, write_tree(D1, Bigger), io:format('~n', []), io:tab(D), io:format('~w ===> ~w~n', [Key,Value]), write_tree(D1, Smaller). ~~~ 現在讓我們來看看我們的勞動成果。假設我們在一棵AVL樹中插入鍵為1,2,3,...,16的16個數據。結果如圖4.3，它是一棵平衡的樹了（跟上一節那棵變形的樹比較一下）。最后是AVL樹中的刪除操作： ~~~ delete(Key, {nil,nil,0,nil,nil}) -> {nil,nil,0,nil,nil}; delete(Key, {Key,_,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}}) -> {nil,nil,0,nil,nil}; delete(Key, {Key,_,_,Smaller,{nil,nil,0,nil,nil}}) -> Smaller; delete(Key, {Key,_,_,{nil,nil,0,nil,nil},Bigger}) -> Bigger; delete(Key, {Key1,_,_,Smaller,{K3,V3,_,S3,B3}}) when Key == Key1 -> {K2,V2,Smaller2} = deletesp(Smaller), combine(Smaller2, K2, V2, S3, K3, V3, B3); delete(Key, {K1,V1,_,Smaller,{K3,V3,_,S3,B3}}) when Key < K1 -> Smaller2 = delete(Key, Smaller), combine(Smaller2, K1, V1, S3, K3, V3, B3); delete(Key, {K1,V1,_,{K3,V3,_,S3,B3},Bigger}) when Key > K1 -> Bigger2 = delete(Key, Bigger), combine( S3, K3, V3, B3, K1, V1, Bigger2). ~~~ 圖4.3 一棵平衡二叉樹 ~~~ nil 16 ===> a nil 15 ===> a nil 14 ===> a nil 13 ===> a nil 12 ===> a nil 11 ===> a nil 10 ===> a nil 9 ===> a nil 8 ===> a nil 7 ===> a nil 6 ===> a nil 5 ===> a nil 4 ===> a nil 3 ===> a nil 2 ===> a nil 1 ===> a nil ~~~ deletisp函數刪除并返回樹中最大的元素。 ~~~ deletesp({Key,Value,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}}) -> {Key,Value,{nil,nil,0,nil,nil}}; deletesp({Key,Value,_,Smaller,{nil,nil,0,nil,nil}}) -> {Key,Value,Smaller}; deletesp({K1,V1,2,{nil,nil,0,nil,nil}, {K2,V2,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}}}) -> {K2,V2, {K1,V1,1,{nil,nil,0,nil,nil},{nil,nil,0,nil,nil}} }; deletesp({Key,Value,_,{K3,V3,_,S3,B3},Bigger}) -> {K2,V2,Bigger2} = deletesp(Bigger), {K2,V2,combine(S3, K3, V3, B3, Key, Value, Bigger2)}. ~~~ 腳注 | [[1]](#) | encode/2和本章其它一些例子的代碼調用了io模塊中的函數。這個模塊是一個提供給用戶進行格式化輸入輸出的標準模塊。它的詳細特性將在第??章和附錄??中描述。 | |-----|-----| | [[2]](#) | 只有一個作者是系領帶的。 | |-----|-----| | [[3]](#) | 這在數據庫管理系統的**數據字典**里面是不用懷疑的。 | |-----|-----| | [[4]](#) | 有關合并規則的詳細描述可以在第[??]章找到。 | |-----|-----|