Learn you some Erlang

for great good!

• Home
• FAQ
• RSS
• Code

A Short Visit to Common Data Structures

Won't be too long, promised!

May mắn là giờ bạn đã hiểu được tương đối các thành phần ( functional subset ) của Erlang rồi và chắc hẳn sẽ không gặp bất cứ khó khăn nào khi đọc các chương trình viết bằng Erlang. Tuy nhiên, có một điều tôi cá với bạn là việc bạn có thể tư duy làm thế nào để xây dưng một chương trình có thể áp dụng được thực tiễn vẫn khá khó, ngay cả khi ở chương trước chúng ta đã tìm hiểu về cách giải quyết các vấn đề theo hướng hám rồi. Tôi muốn nhấn mạnh đó là bởi vì bản thân tôi trong quá trình học cũng cảm thấy tương tự điều này, tuy nhiên có thể do kinh nghiệm, yếu tố của từng người, vì vậy nếu bạn không cảm thấy mình đã làm được điều đó rồi thì tôi thật sự chúc mừng bạn. Chances are you now understand the functional subset of Erlang pretty well and could read many programs without a problem. However, I could bet it's still a bit hard to think about how to build a real useful program even though the last chapter was about solving problems in a functional manner. I'm saying this because it's how I felt like at about that point in my learning, but if you're doing better, congratulations!

Dù sao, theo quan điểm của tôi, chúng ta lên nhìn nhận một số vấn đề sau: phần lớn các kiểu dữ liệu cơ bản, shell, cách viết module and hàm ( đê quy ), các cách biên dịch, điểu khiển luồng, xử lí ngoại lệ, một số hoạt động trừu tượng ,etc. Chúng ta cũng đã biết được cách để lưu trữ dữ liệu vào bên trong bộ, danh sách và đã thực hiện một phần của cấu trúc cây nhị phân rồi. nhưng ngoài những thứ trên ra chúng ta vẫn chưa thấy được các cấu trúc dữ liệu khác trong bộ thư viên chuẩn của Erlang để cung cấp cho lập trình viên. Vì vây trong chương này chúng ta sẽ đi tìm hiểu chi tiết hơn các các loại dữ liệu khác và nó cũng quan trong không kém như danh sách hay bộ. Anyway, the point I'm coming to is that we've seen a bunch of things: most basic data types, the shell, how to write modules and functions (with recursion), different ways to compile, control the flow of the program, handle exceptions, abstract away some common operations, etc. We've also seen how to store data with tuples, lists and an incomplete implementation of a binary search tree. What we haven't seen is the other data structures provided to the programmer in the Erlang standard library.

Records

Cấu trúc dữ liệu đầu tiên mà chúng ta sẽ tìm hiểu đó là bản ghi ( Record ). Về vấn đề này tôi giá nói sau, trước tiên records khá hữu ích trong trường hơn bạn cần cấu trúc dữ liệu nhỏ mà cho phép bạn truy cập trực tiếp vào các thuộc tính thông qua tên, nếu bạn đã học các ngôn ngữ mệnh lệnh khác như C thì sẽ thấy records khá giống với với struct trong C. They are more or less an afterthought to the language and can have their share of inconveniences. I'll cover that later. They're still pretty useful whenever you have a small data structure where you want to access the attributes by name directly. As such, Erlang records are a lot like structs in C (if you know C.)

Records trong Erlang sẽ được khai báo như một thuộc tính của module như sau:

-module(records).
-compile(export_all).

-record(robot, {name,
                type=industrial,
                hobbies,
                details=[]}).

Ở đây chúng ta đã tạo ra một record có tên là 'robot', trong record này chứ 4 trường: name, type, hobbies và details. trong record cho phép bạn gán giá trị mặc định cho các trường, ở đây chúng ta sẽ gán giá trị mặc định cho các trường type và details với hai giá trị là industrial và []/ Đây là cách bạn định nghĩa một record , giờ hãy tạo một file module đặt tên là records và và đặt đoạn mã trên vào trong file module này:

first_robot() ->
    #robot{name="Mechatron",
           type=handmade, 
           details=["Moved by a small man inside"]}.

giờ ta sẽ biên dịch và kiểm tra những gì ta vừa viết:

1> c(records).
{ok,records}
2> records:first_robot().
{robot,"Mechatron",handmade,undefined,
       ["Moved by a small man inside"]}

Woops! Điều này phải chăng là hack! Cú pháp của Erlang records chỉ là một cách viết ngọt ngào của bộ. Vậy thì thực sự sao ta không dùng bộ thay vì mất công viết kiểu này. Thật may mắn là có một cách để viết record một cách đẽ nhìn hơn. Trong Erlang shell hỗ trợ một lệnh rr(Module), lệnh này cho phép bạn nạp record đã định nghĩa từ Module vào trong shell:

3> rr(records).
[robot]
4> records:first_robot().         
#robot{name = "Mechatron",type = handmade,
       hobbies = undefined,
       details = ["Moved by a small man inside"]}

Đó! trông cách này có vẻ dễ dàng, dễ nhìn hơn không. Có thể bạn để ý rằng trong hàm first_robot/0, chúng ta đã không định nghĩa trường hobbies cùng với giá trị mặc định Mặc dù vậy, trong Erlang nếu bạn không đinh nghĩa giá trị mặc đinh thì nếu không xác định giá trị khi tạo một record thì Erlang sẽ tự động đặt giá trị là undefined.

Để thấy rõ được hành vi mặc đinh được tạo trong record, hãy biên dịch hàm sau đây: To see the behavior of the defaults we set in the robot definition, let's compile the following function:

car_factory(CorpName) ->
    #robot{name=CorpName, hobbies="building cars"}.

Và kiểm tra nó trong shell:

5> c(records).
{ok,records}
6> records:car_factory("Jokeswagen").
#robot{name = "Jokeswagen",type = industrial,
       hobbies = "building cars",details = []}

Xem ra chúng ta đã có một con robot thích danh thời giam để lắp ráp những chiếc xe oto phải ko nhỉ.

Bạn phải biết rằng nếu chỉ viết một record không thì không có ý nghĩa gì nhiều. Thay vào đó chúng ta cần một phương pháp để lấý các giá trị bên trong record đó ra. Thông thường có hai cách để làm điều này, cách đầu tiên đó là xử dụng ký tự '.' ( 'dot syntax' ). Đặt giả thiết rằng bạn đinh nghĩa một record cho robot như sau:

5> Crusher = #robot{name="Crusher", hobbies=["Crushing people","petting cats"]}. 
#robot{name = "Crusher",type = industrial,
       hobbies = ["Crushing people","petting cats"],
       details = []}
6> Crusher#robot.hobbies.
["Crushing people","petting cats"]

Ugh, thật sự đây không phải là một cú pháp gọn gàng. Một phần là do bản chất của record vẫn là bộ và trình biên dịch chỉ nhìn nhận nó như một mẹo để dịch sang bộ mà thôi. do đó bạn phải lưu trữ các từ khóa của record và xác định biến đó ứng với giá trị nào, đó là lí do vì sao #robot là một phần của Crusher#robot.hobbies. Thật đáng thất vọng phai nó rằng không có một cách nào để biểu diễn gọn gàng hơn. Thậm chí nó còn tồi tề hơn khi bạn làm viẹc với các record lồng nhau. This is due to the nature of records as tuples. Because they're just some kind of compiler trick, you have to keep keywords around defining what record goes with what variable, hence the #robot part of Crusher#robot.hobbies. It's sad, but there's no way out of it. Worse than that, nested records get pretty ugly:

7> NestedBot = #robot{details=#robot{name="erNest"}}.
#robot{name = undefined,type = industrial,
       hobbies = undefined,
       details = #robot{name = "erNest",type = industrial,
                        hobbies = undefined,details = []}}
8> (NestedBot#robot.details)#robot.name. 
"erNest"

Trong một record lồng nhau, bắt buộc phải có dấu ngoặc.

Để hiển thì thêm mức độ phụ thuộc của record đối với bộ, hay nhìn ví dụ sau đây:

9> #robot.type.
3

Vậy kết quả trên là phần tử nào trong bộ ? What this outputs is which element of the underlying tuple it is.

Một trong những tính nằng của bộ đó là việc kết hợp chúng với khớp mẫu và chốt canh cho đầu vào của hàm . Vd hay khai báo một record ở đầu file và sau đó thêm các hàm sau đây: One saving feature of records is the possibility to use them in function heads to pattern match and also in guards. Declare a new record as follows on top of the file, and then add the functions under:

-record(user, {id, name, group, age}).

%% use pattern matching to filter
admin_panel(#user{name=Name, group=admin}) ->
    Name ++ " is allowed!";
admin_panel(#user{name=Name}) ->
    Name ++ " is not allowed".

%% can extend user without problem
adult_section(U = #user{}) when U#user.age >= 18 ->
    %% Show stuff that can't be written in such a text
    allowed;
adult_section(_) ->
    %% redirect to sesame street site
    forbidden.

Trong cú pháp trên, nó sẽ khớp để gán ( bind ) một biến tới bất kỳ trường nào của record trong hàm ( nó cũng cho phép bind các biến tới nhiều trường), bạn có thể nhìn vào hàm admin_panel/1 để thấy. Một lưu ý là như ví dụ trong hàm adult_section/1 , để bind môt biến vào toàn bộ record bạn sẽ phải viết SomeVar = #some_record{}. Nào như thường lệ hãy biên dịch đoạn mã và chạy trong shell: The syntax to bind a variable to any field of a record is demonstrated in the admin_panel/1 function (it's possible to bind variables to more than one field). An important thing to note about the adult_section/1 function is that you need to do SomeVar = #some_record{} in order to bind the whole record to a variable. Then we do the compiling as usual:

10> c(records).
{ok,records}
11> rr(records).
[robot,user]
12> records:admin_panel(#user{id=1, name="ferd", group=admin, age=96}).
"ferd is allowed!"
13> records:admin_panel(#user{id=2, name="you", group=users, age=66}). 
"you is not allowed"
14> records:adult_section(#user{id=21, name="Bill", group=users, age=72}).
allowed
15> records:adult_section(#user{id=22, name="Noah", group=users, age=13}).
forbidden

Bạn có thể thấy rõ ở ví dụ trên, chúng ta không nhất thiết phải khớp với tât cả thành phần có trong bộ hay nói một cách khác là chúng ta không cần quan tâm tới có bao nhiêu các trường trong bộ cần biết khi viết hàm. Thay vào đó chúng ta chỉ cần quan tâm tới những phần cần so sánh, vd như ở hàm adult_section/1 chúng ta có thể chỉ cần quan tâm tới trường 'age' hay 'group' và khớp chúng nếu chúng thật sự cần còn những trường còn lại có thể bỏ qua không cần phải khớp với tât cả nhưng phần còn lại của cấu trúc. Nếu chúng ta sư dụng kiểu bộ , định nghĩa hàm sẽ có dạng function({record, _, _, ICareAboutThis, _, _}) -> .... Trường hợp nếu ai đó muốn thêm một phân tử vào bộ thì họ ( chắc chắn sẽ không hài lòng về việc làm này ) sẽ phải tìm kiếm xung quanh để sửa lại tât cả các bộ bên trong các hàm đã viết trước đó. What this lets us see is how it is not necessary to match on all parts of the tuple or even know how many there are when writing the function: we can only match on the age or the group if that's what's needed and forget about all the rest of the structure. If we were to use a normal tuple, the function definition might need to look a bit like function({record, _, _, ICareAboutThis, _, _}) -> .... Then, whenever someone decides to add an element to the tuple, someone else (probably angry about it all) would need to go around and update all functions where that tuple is used.

Các vi dụ hàm tiếp theo đây sẽ chỉ ra cách để cật nhật một record The following function illustrates how to update a record (they wouldn't be very useful otherwise):

repairman(Rob) ->
    Details = Rob#robot.details,
    NewRob = Rob#robot{details=["Repaired by repairman"|Details]},
    {repaired, NewRob}.

Sau đó:

16> c(records).
{ok,records}
17> records:repairman(#robot{name="Ulbert", hobbies=["trying to have feelings"]}).
{repaired,#robot{name = "Ulbert",type = industrial,
                 hobbies = ["trying to have feelings"],
                 details = ["Repaired by repairman"]}}

Có vẻ như robot của tôi đã được sửa rồi. Như bạn thây cú pháp để cập nhật một record có chút khác biệt. Nó trông như chúng ta cập nhật (Rob#robot{Field=NewValue}) nhưng thực sự thì đó chỉ là một cơ ( mẹo ) để trình biên dịch gọi tới hàm erlang:setelement/3. And you can see my robot has been repaired. The syntax to update records is a bit special here. It looks like we're updating the record in place (Rob#robot{Field=NewValue}) but it's all compiler trickery to call the underlying erlang:setelement/3 function.

Điều cuối cùng tôi muón nói về record. Chúng thật sự rất hữu ích nhưng việc thường xuyên phải lặp lại các đoạn mã record như vậy thực sự khó chịu. Có thể bạn ko biét rằng các Lập trình viên Erlang thường xuyên phải chia sẻ các record giữa các module cùng với sự trợ giúp từ header files, Erlang header files khá giống với C counter-part, cả hai chỉ là những đoạn mã được thêm vào trong module. bạn có thể tạo ra một file đặt tên là records.hrl và thêm đoạn mã sau: One last thing about records. Because they're pretty useful and code duplication is annoying, Erlang programmers frequently share records across modules with the help of header files. Erlang header files are pretty similar to their C counter-part: they're nothing but a snippet of code that gets added to the module as if it were written there in the first place. Create a file named records.hrl with the following content:

%% this is a .hrl (header) file.
-record(included, {some_field,
                   some_default = "yeah!",
                   unimaginative_name}).

Sau đó, để sử dụng record từ file này records.erl, đơn giản chỉ cần thêm dòng sau vào trong file module:

-include("records.hrl").

Và hãy thử hàm sau:

included() -> #included{some_field="Some value"}.

Giờ như thường lệ mở shell lên và:

18> c(records).
{ok,records}
19> rr(records).
[included,robot,user]
20> records:included().
#included{some_field = "Some value",some_default = "yeah!",
          unimaginative_name = undefined}

Hooray! Đó là tất cả những gì về record mà tôi muôn nói. Trông chúng thật rối nhưng lại rất hữu ích. Mặc dù cú pháp của chúng không thực sự gọn gàng, ưa nhìn nhưng chúng thực sự quan trọng cho việc bảo trì các đoạn mã của bạn. That's about it for records; they're ugly but useful. Their syntax is not pretty, they're not much but a hack, but they're relatively important for the maintainability of your code.

Key-Value Stores

Trong các chương trước , tôi đã chỉ cho bạn cách để xây dụng một cấu trúc cây rồi, đồng thời trong cấu trúc cũng sử dụng nó như một dạng cặp khóa-giá trị ( key-value ) cho sổ địa chỉ. Tuy nhiên các địa chỉ đó thật sự tê, chúng ta không thể làm gì với chúng được cả, không thể xóa hay chuyển đổi được gì hết. Ngoài việc áp dụng nó với đệ quy ra chúng ta không thể làm được nhiều cả. Vì vậy đã đến lúc tôi sẽ giới thiệu cho bạn một vài cấu trúc dữ liệu và module hữu ích giúp chúng ta trong việc lưu trữ dữ liệu liên quan tới từ khóa cụ thể rồi. bởi vì thông tin rất nhiều, cho lên tôi sẽ không đi sâu vào chi tiết định nghĩa của mỗi hàm sẽ làm gì hay đánh giá toàn bộ module mà thay vào đó tôi sẽ chỉ đơn giản đính kèm một liên kết tới tài liệu hướng dẫn thôi. I've had you build a tree back a few chapters, and the use was to use it as a key-value store for an address book. That book sucked: we couldn't delete or convert it to anything useful. It was a good demonstration of recursion, but not much more. Now is the time to introduce you to a bunch of useful data structures and modules to store data under a certain key. I won't define what every function does nor go through all the modules. I will simply link to the doc pages. Consider me as someone responsible about 'raising awareness about key-value stores in Erlang' or something. Sounds like a good title. I just need one of these ribbons.

Để lưu trực một lượng dữ liệu không lớn, bạn có thể sử dụng hai loại cấu trúc dữ liệu cơ bản, cấu trúc đâu tiên là proplist, đây là cấu trúc của bất kỳ kiểu dữ liệu bộ danh sách được viét dưới dạng [{Key,Value}] Có thể bạn sẽ thấy ngạc nhiên vì loại cấu trúc kỳ lạ này tuy nhiên thực sự thì không có một nguyên tác nào cho điều đó cả. thực tế quy tắc đối với proplist không bị ràng buộc vì thế nó cũng có thể chứa các giá trị boolean, số nguyên hay bất cứ kiểu dũ liệu nào mà bạn muốn. mặc dù vậy trong trong chương này chúng ta chỉ quan tâm tới danh sách cùng cặp giá trị bộ dạng key-value thôi. Để thao tác cùng proplists chúng ta sẽ sử dụng module proplists sẵn có trong Erlang, module có rất nhiều hàm giúp cho việc giao tiếp với proplíst một cách thuận tiện như proplists:delete/2, proplists:get_value/2, proplists:get_all_values/2, proplists:lookup/2 và proplists:lookup_all/2. For small amounts of data, there are basically two data structures that can be used. The first one is called a proplist. A proplist is any list of tuples of the form [{Key,Value}]. They're a weird kind of structure because there is no other rule than that. In fact the rules are so relaxed that the list can also contain boolean values, integers and whatever you want. We're rather interested by the idea of a tuple with a key and a value in a list here, though. To work with proplists, you can use the proplists module. It contains functions such as proplists:delete/2, proplists:get_value/2, proplists:get_all_values/2, proplists:lookup/2 and proplists:lookup_all/2.

Đọc qua module, chắc hẳn bạn sẽ thấy ngạc nhiên là không có một hàm nào để thêm hay sửa một phần tử trong dánh sách. Điều này không phải là thiêú sot mà có chủ ý, về cơ bản chúng ta vẫn thao tác trên một kiểu dữ liệu danh sách và hình dung proplist như một câu trúc. Và để thêm hay sửa môth phần tử trong cấu trúc này chúng ta làm tương tự như khi thao tác với danh sách bàng việc sử dụng toán tử cons ( | ), như vậy ta sẽ có lists:keyreplace/4. hoặc sử dụng hàm lists:keyreplace/4 cho việc sửa đổi phần từ dữ liệu. Thông thường trong một chương trình làm việc với một lượng dữ liệu không lớn nhưng sử dụng một bộ danh sách, để làm việc được bạn sẽ phải sử dụng tới hai hay nhiều module để thao tác với hai kiểu dữ liệu này, điều này thực sự hơi phức tạp và rối, tuy nhiên nhờ vào định nghĩa không rõ ràng của proplist, cho lên nó thường xuyên được dùng để thao tác với configuration lists và mô tả chùng cho một đôí tượng cụ thể nào. Lưu ý là Proplist không phải là một cấu trúc dữ liệu hoàn chỉnh, thay vào đó nó có thể coi như một mẫu chung cho một đôi tượng hay vật để sử dụng thao tác với danh sách và bộ. module proplists cũng được coi là một loại công cụ cho mẫu này.

trong You'll notice there is no function to add or update an element of the list. This shows how loosely defined proplists are as a data structure. To get these functionalities, you must cons your element manually ([NewElement|OldList]) and use functions such as lists:keyreplace/4. Using two modules for one small data structure is not the cleanest thing, but because proplists are so loosely defined, they're often used to deal with configuration lists, and general description of a given item. Proplists are not exactly complete data structures. They're more of a common pattern that appears when using lists and tuples to represent some object or item; the proplists module is a bit of a toolbox over such a pattern.

Trong trường hợp bạn muốn sử dụng một cấu trúc key-value hoàn chỉnh cho việc lưu trữ một lượng nhỏ dữ liệu. module orddict sẽ là thứ mà bạn cần. Orddicts ( ordered dictionaries) có thể coi là một hình thức khác của proplists. Ở cấu trúc dũ liệu này mỗi khóa sẽ chỉ cho phép lưu trữ duy nhất một lần và danh sách trong cấu trúc này sẽ được sắp xếp để cải thiện cho việc tìm kiếm, etc. Sau đây là một số hàm phổ biến được dùng để thêm, sủa, xóa ( CRUD ) các phần tử khi thao tác với kiểu dứ liệu này orddict:store/3, orddict:find/2 (Trong trường hợp bạn không chắc từ khóa bạn tìm có tồn tại hay không), orddict:fetch/2 (trong trường hợp bạn chắc chắn từ khóa có tồn tại) and orddict:erase/2.

If you do want a more complete key-value store for small amounts of data, the orddict module is what you need. Orddicts (ordered dictionaries) are proplists with a taste for formality. Each key can be there once, the whole list is sorted for faster average lookup, etc. Common functions for the CRUD usage include orddict:store/3, orddict:find/2 (when you do not know whether the key is in the dictionaries), orddict:fetch/2 (when you know it is there or that it must be there) and orddict:erase/2.

Orddict là cấu trúc được sử dụng như một sự cân bằng giữa tính phức tạp và hiệu suất với điều kiện là ̃số lượng phàn tử hoạt động là khoảng 75 phần tử (bạn có thể xem kết quả thử nghiệm của tôi ). Trong trường hợp nếu số lương phần vượt qúa thì bạn lên lựa chọn một cấu trúc key-value khác cho việc lưu trữ để đảm bảo hiệu suất tốt hơn. Orddicts are a generally good compromise between complexity and efficiency up to about 75 elements (see \ơ my benchmark). After that amount, you should switch to different key-value stores.

Ngoài ra chúng ta cũng có hai cấu trúc/module key-value cho việc xử lí với lượng lớn dũ liệu: đó là dicts và gb_trees. Với các kiểu dữ liệu từ điển ( Dictionaries ) này , các lớp giao tiếp của chúng tương tư như kiẻu orddicts: dict:store/3, dict:find/2, dict:fetch/2, dict:erase/2, ngoài ra các hàm dict:map/2 There are basically two key-value structures/modules to deal with larger amounts of data: dicts , dict:fold/2 là lựa chọn rất tốt trong vấn đề mở rộng orddicts khi cần. and gb_trees. Dictionaries have the same interface as orddicts: dict:store/3, dict:find/2, dict:fetch/2, dict:erase/2 and every other function, such as dict:map/2 and dict:fold/2 (pretty useful to work on the whole data structure!) Dicts are thus very good choices to scale orddicts up whenever it is needed.

Đôi với gb_trees ( General Balanced Trees ) , hay chính xác chúng là một cụm các hàm hơh là một dạng cấu trúc. Trong cấu trúc này cần phân biệt giữa 2 mode: mode đầu tiên, ở mode này bạn nhân thức rõ ràng được cấu trúc ( tôi gọi chế đọ ày là 'smart mode'), và mode thứ hai, mode mà bạn không nhận thực dược nhiều về cáu trúc ( tội gõ là 'naive mode'). trong naive mode, bao gồm các hàm gb_trees:enter/3, gb_trees:lookup/2 and gb_trees:delete_any/2. các hàm thông minh: gb_trees:insert/3, gb_trees:get/2, gb_trees:update/3 and gb_trees:delete/2. Nó cung có hàm gb_trees:map/2 khi bạn cần. on the other hand, have a bunch more functions leaving you more direct control over how the structure is to be used. There are basically two modes for gb_trees: the mode where you know your structure in and out (I call this the 'smart mode'), and the mode where you can't assume much about it (I call this one the 'naive mode'). In naive mode, the functions are gb_trees:enter/3, gb_trees:lookup/2 and gb_trees:delete_any/2. The related smart functions are gb_trees:insert/3, gb_trees:get/2, gb_trees:update/3 and gb_trees:delete/2. There is also gb_trees:map/2 , which is always a nice thing when you need it.

vì gb_trees là cấu trúc dữ liệu mang tính cân bằng do đó nhược điểm của 'naive' so với 'smart' đó là bất cứ khi nào bạn chèn thêm một phần tử mới ( hay xóa một cụm các phần tử), nó sẽ cân phải tự chinh lại các phần tử để thỏa mãn tính chất cân bằng. Việc làm này sẽ tiêu tốn thời gian tài nguyên bộ nhớ ( thậm chí một số trường hợp chỉ kiểm tra mà không thay đổi gì cả ). Tuy nhiên trong hàm của chế độ 'smart' luôn giả đinh rằng tât các các khóa đã tồn tại trong cây , do đó nó cho phép bạn bỏ qua tất cả các kiểm tra và giảm thời gian thực hiện. The disadvantage of 'naive' functions over 'smart' ones is that because gb_trees are balanced trees, whenever you insert a new element (or delete a bunch), it might be possible that the tree will need to balance itself. This can take time and memory (even in useless checks just to make sure). The 'smart' function all assume that the key is present in the tree: this lets you skip all the safety checks and results in faster times.

Vậy trong trường hợp nao bạn lên sử dụng gb_trees thay vì sử dụng dicts ? Thật lòng mà nói thực sự không rõ ràng để quyết định lên sử dụng cáu trúc nào. Dựa trên kết quả kiểm tra benchmark module của tôi so sánh hiệu suất giữa gb_trees và dicts, trong nhiều trường kết quả hiệu suất giữa chúng không thực sự sai biệt nhau lắm. Tuy vậy, nhìn vào kết quả kiểm tra này nó chứng mình được khả năng đọc của cấu trúc dicts tương đối nhanh trong khi các hoạt động khác trong gb_trees lại nhỉnh hơn chút. vì vậy tùy theo tùy cầu của bạn trong việc giải quyết bài toán, công việc mà quyết định chọn xem cấu trúc nào thích hợp nhất. When should you use gb_trees over dicts? Well, it's not a clear decision. As the benchmark module I have written will show, gb_trees and dicts have somewhat similar performances in many respects. However, the benchmark demonstrates that dicts have the best read speeds while the gb_trees tend to be a little quicker on other operations. You can judge based on your own needs which one would be the best.

Ngoài ra cũng lưu ý là cấu trúc dicts có hỗ trợ hàm 'fold' trong khi gb_treé thì không, mặc dù gb_trees vẫn có hàm để lặp iterator , nhưng nó sẽ trả về một phần của cây và gọi hàm gb_trees:next(Iterator) để lấy giá tri các phàn khác theo thứ tự. Đó là lí do vì sao bạn cần viêt các hàm đệ quy của riêng mình dựa trên những tiện ích cung cấp từ cấu trúc gb_trees hơn là sử dụng hàm fold. Một điều nữa là gb_trees cho hỗ trợ bạn truy cập nhanh chóng tới các phần tử nhỏ nhất và lớn nhất của nó thông qua hàm gb_trees:smallest/1 và gb_trees:largest/1.

Oh and also note that while dicts have a fold function, gb_trees don't: they instead have an iterator function, which returns a bit of the tree on which you can call gb_trees:next(Iterator) to get the following values in order. What this means is that you need to write your own recursive functions on top of gb_trees rather than use a generic fold. On the other hand, gb_trees let you have quick access to the smallest and largest elements of the structure with gb_trees:smallest/1 and gb_trees:largest/1.

Cuối cùng tôi chỉ muốn nhắc là tùy theo nhu cấu ứng dụng của bạn mà hãy quyết định chọn cấu trúc key-value phù hợp. Các quyết định có thể phụ thuôc vào nhiều yêu tố khác nhau vd như số lượng dữ liệu bạn cần lưu trữ, các hoạt động cần thiết để thao tác với dữ liệu, etc. Và để chắc chắn trước quyết định của mình bạn có thể tiến hành các phép đo lường , kiểm tra hiệu suất. I would therefore say that your application's needs is what should govern which key-value store to choose. Different factors such as how much data you've got to store, what you need to do with it and whatnot all have their importance. Measure, profile and benchmark to make sure.

Lưu ý: Ngoài các cấu trúc đã tìm hiểu ở phần này ra, còn có một số cấu trúc key-value đặc biệt được dùng để thao tác với các dữ liệu có kích cỡ khác nhau. Vd như ETS tables, DETS tables và mnesia database. Tuy nhiên, tôi sẽ không đề cập chi tiết trong chương này vì chúng có liên quan chặt chẽ tới khái niệm đa tiến trình và phân tán. thay vào đó chúng ta sẽ tìm hiểu chúng ở các chương tiếp theo. Ở đây tôi chỉ giới thiệu qua chúng để gợi sự tò mò của bạn và những người quan tâm tới mà thôi. However, their use is strongly related to the concepts of multiple processes and distribution. Because of this, they'll only be approached later on. I'm leaving this as a reference to pique your curiosity and for those interested.

Bổ sung:
Từ phiên bản 17.0 trở đi, các nhà phát triển ngôn ngữ đã bổ sung thêm kiểu dữ liệu native key-value mới như một sự thay thế cho dicts, bạn có hể tìm hiểu tại Postscript: Maps.

Arrays

Trong các bài học trước đến này những gì chúng ta thấy đó là các cấu trúc dữ liệu trong Erlang có thể hoạt động với hầu hết tất cả các kiểu dữ liệu, Tuy nhiên trong trường hợp chúng ta cần một kiểu cấu trúc để hoạt động hiêu quả hơn với kiểu số thì sao ? Thật may mắn, trong Erlang cung cấp cho chúng ta một kiểu cấu trúc như vậy. Trong phần này chúng ta sẽ tìm hiểu về arrays, đây là cấu trúc được tối ưu cho việc thao tác với kiểu số, bạn có thể truy cập vào các phần tử thông qua chỉ mục và áp dụng 'fold' cho toàn bộ cấu trúc, ngoài ra trong quá trình lặp bạn có thể bỏ qua các phần tử không xác đinh rõ ràng giá trị. But what about code that requires data structures with nothing but numeric keys? Well for that, there are arrays. They allow you to access elements with numerical indices and to fold over the whole structure while possibly ignoring undefined slots.

Don't drink too much kool-aid:
Người với các imperative counterpart arrays không thể tìm kiếm hay chèn dữ liệu liệu vào trong một khoảng thời gian nhất định. chúng ra cũng ít khi sử dụng chúng trong nhiêu ngôn ngữ bởi vì hiệu suất xử lí của chúng khá chậm, chậm hơn so với các kiểu khác ( đặc biệt là so với danh sách) Erlang arrays, at the opposite of their imperative counterparts, are not able to have such things as constant-time insertion or lookup. Because they're usually slower than those in languages which support destructive assignment and that the style of programming done with Erlang doesn't necessary lend itself too well to arrays and matrices, they are rarely used in practice.

Thông thường, arrays sẽ được sử dụng trong các bài toán cần tới tính toán ma trận cùng với một só khái niệm như Erlang programmers who need to do matrix manipulations and other uses requiring arrays tend to use concepts called Ports ( với sự hỗ trợ của công cụ này, việc thực hiện các hoạt động đòi hỏi tính xử lí cao sẽ được chuyển sang cho một ngôn ngữ khác, cụ thể là C để xử lí ) hay C-Nodes, Linked in drivers và NIFs (Experimental, R13B03+).

Điểm khác biệt nữa so với các cấu trúc khác đó là Arrays là một trong số ít cấu trúc sử dụng chỉ mục bắt đầu từ 0 ( đối nghịch với bộ và danh sách) , bên cạnh đó có module regular expressions module cũng sử dụng chỉ mục tương tự, do đó hãy cẩn thân nhầm nhẫn giũa chúng. Arrays are also weird in the sense that they're one of the few data structures to be 0-indexed (at the opposite of tuples or lists), along with indexing in the regular expressions module. Be careful with them.

A Set of Sets

Nếu bạn đã từng nghiên cứu về lý thuyết tập hợp ( set ) trong toán học, chắc hẳn bạn sẽ có một vài y tưởng về set để làm điều gì đó. còn nếu không phải, bạn có thể quên những gì tôi nói. Tuy vậy tôi vẫn sẽ nói tăng set là một tập hợp các phần tử duy nhất và có thể so sánh hay thực hiện các thao tác trên chúng, vd như tìm những phần các phần tử cùng thuộc hai nhóm, hoặc không thuộc bất kỳ nhóm nào hoặc chỉ thuộc về một nhóm. Ngoài ra còn một số thao tác phức tạp hơn cho phép bạn xác định mối quan hệ giữa các nhóm và thực hiện các hành vi dựa trên các quan hệ đó. Trong phạm vi của cuốn sách này tôi sẽ chỉ đưa ra các khái niệm cơ bản và cách sử dụng thôi và tôi sẽ không đi chi tiết về lí thuyết tập, nếu bạn tò mò muốn tìm hiểu bạn có thể tìm kiếm thông tin trong các cuốn sách về toán học hay các bài trên mạng. If you've ever studied set theory in whatever mathematics class you have an idea about what sets can do. If you haven't, you might want to skip over this. However, I'll just say that sets are groups of unique elements that you can compare and operate on: find which elements are in two groups, in none of them, only in one or the other, etc. There are more advanced operations letting you define relations and operate on these relations and much more. I'm not going to dive into the theory (again, it's out of the scope of this book) so I'll just describe them as it is.

Trong Erlang có tất tât cả 4 module được xây dựng sẵn để thao tác với sets. Nghe có vẻ kỳ lạ nhưng đây là kết quả đồng thuận chung từ những người thực hiện Erlang, và sau khi tìm hiểu được hơn về sets chắc chắc bạn cùng đồng ý với ý kiến này bởi vì không có một cách nào 'tốt nhất' cho việc xây dưng set cả. 4 module đó là ordsets, sets, gb_sets and sofs (sets of sets):

There are 4 main modules to deal with sets in Erlang. This is a bit weird at first, but it makes more sense once you realize that it's because it was agreed by implementers that there was no 'best' way to build a set. The four modules are ordsets, sets, gb_sets and sofs (sets of sets):

ordsets

Ordsets về bản chất là một danh sách có thứ tự. Đây là kiểu dữ liệu có tốc độ chậm nhất trong cá loại dũ liệu set, chúng thường được sử dụng để làm việc với các tập dữ liệu không lớn. Tuy vậy chúng khá đơn giản và dễ đọc. sau đây là một số hàm tiêu chuẩn cho chúng: ordsets:new/0, ordsets:is_element/2, ordsets:add_element/2, ordsets:del_element/2 , ordsets:union/1, ordsets:intersection/1, and a bunch more.

are implemented as a sorted list. They're mainly useful for small sets, are the slowest kind of set, but they have the simplest and most readable representation of all sets. There are standard functions for them such as ordsets:new/0, ordsets:is_element/2, ordsets:add_element/2, ordsets:del_element/2 , ordsets:union/1, ordsets:intersection/1, and a bunch more.

sets

Sets (the module) có cấu trúc khá giống với cấu trúc của kiểu dữ liệu dict mà trước đó ta đã tìm hiểu. Chúng có có những giao tiếp hàm giống với ordsets, nhưng khác với ordsets, hiệu suất và khả năng làm việc của sets tốt hơn nhiều. tương tự kiểu từ điển , chúng rất hữu ích cho các vấn đề liên quan tới các hoạt động đòi hỏi một lượng lớn đọc dữ liệu. vd như việc kiểm tra một phân tử có nằm trong tập hợp hay không. is implemented on top of a structure really similar to the one used in dict. They implement the same interface as ordsets, but they're going to scale much better. Like dictionaries, they're especially good for read-intensive manipulations, like checking whether some element is part of the set or not.

gb_sets

Gb_sets, tương tự cấu trúc này được xây dựng dựa trên cấu trúc cây cân bằng ( General Balanced Tree ) và structure similar to the one used in the gb_trees module. gb_sets are to sets what gb_tree is to dict; an implementation that is faster when considering operations different than reading, leaving you with more control. While gb_sets implement the same interface as sets and ordsets, they also add more functions. Like gb_trees, you have smart vs. naive functions, iterators, quick access to the smallest and largest values, etc.

sofs

Sets of sets (sofs) are implemented with sorted lists, stuck inside a tuple with some metadata. They're the module to use if you want to have full control over relationships between sets, families, enforce set types, etc. They're really what you want if you need mathematics concept rather than 'just' groups of unique elements.

Don't drink too much kool-aid:
While such a variety can be seen as something great, some implementation details can be downright frustrating. As an example, gb_sets, ordsets and sofs all use the == operator to compare values: if you have the numbers 2 and 2.0, they'll both end up seen as the same one.

However, sets (the module) uses the =:= operator, which means you can't necessarily switch over every implementation as you wish. There are cases where you need one precise behavior and at that point, you might lose the benefit of having multiple implementations.

It's a bit confusing to have that many options available. Björn Gustavsson, from the Erlang/OTP team and programmer of Wings3D mainly suggests using gb_sets in most circumstances, using ordset when you need a clear representation that you want to process with your own code and 'sets' when you need the =:= operator (source.)

In any case, like for key-value stores, the best solution is usually to benchmark and see what fits your application better.

Directed Graphs

There is one other data structure that I want to mention here (not that there are not more than what's mentioned in this chapter, on the contrary): directed graphs. Again, this data structure is more for readers who already know the mathematical theory that goes with it.

Directed graphs in Erlang are implemented as two modules, digraph and digraph_utils. The digraph module basically allows the construction and modification of a directed graph: manipulating edges and vertices, finding paths and cycles, etc. On the other hand, digraph_utils allows you to navigate a graph (postorder, preorder), testing for cycles, arborescences or trees, finding neighbors, and so on.

Because directed graphs are closely related to set theory, the 'sofs' module contains a few functions letting you convert families to digraphs and digraphs to families.

Queues

The queue module implements a double-ended FIFO (First In, First Out) queue:

They're implemented a bit as illustrated above: two lists (in this context, stacks) that allow to both append and prepend elements rapidly.

The queue module basically has different functions in a mental separation into 3 interfaces (or APIs) of varying complexity, called 'Original API', 'Extended API' and 'Okasaki API':

Original API

The original API contains the functions at the base of the queue concept, including: new/0, for creating empty queues, in/2, for inserting new elements, out/1, for removing elements, and then functions to convert to lists, reverse the queue, look if a particular value is part of it, etc.

Extended API

The extended API mainly adds some introspection power and flexibility: it lets you do things such as looking at the front of the queue without removing the first element (see get/1 or peek/1), removing elements without caring about them (drop/1), etc. These functions are not essential to the concept of queues, but they're still useful in general.

Okasaki API

The Okasaki API is a bit weird. It's derived from Chris Okasaki's Purely Functional Data Structures. The API provides operations similar to what was available in the two previous APIs, but some of the function names are written backwards and the whole thing is relatively peculiar. Unless you do know you want this API, I wouldn't bother with it.

You'll generally want to use queues when you'll need to ensure that the first item ordered is indeed the first one processed. So far, the examples I've shown mainly used lists as a accumulators that would then be reversed. In cases where you can't just do all the reversing at once and elements are frequently added, the queue module is what you want (well, you should test and measure first! Always test and measure first!)

End of the short visit

That's about it for the data structures trip of Erlang. Thank you for having kept your arms inside the vehicles the whole time. Of course, there are a few more data structures available than that to solve different problems. I've only covered those that you're likely to encounter or need the most given the strengths of general use cases of Erlang. I encourage you to explore the standard library and the extended one too to find more information.

You might be glad to learn that this completes our trip into sequential (functional) Erlang. I know a lot of people get in Erlang to see all the concurrency and processes and whatnot. It's understandable, given it's really where Erlang shines. Supervision trees, fancy error management, distribution, and more. I know I've been very impatient to write about these subjects, so I guess some readers were very impatient to read about them.

However, I judged it made more sense to be comfortable with functional Erlang before moving on to concurrent Erlang. It will be easier to move on afterwards and focus on all the new concepts. Here we go!

• < Previous
• Index
• Next >