Elixir是否具有类似于Clojure的持久数据结构？ [英] Does Elixir have persistent data structures similar to Clojure?

问题描述

Elixir中所有不可变的数据结构是否持久存在？如果不是，那么哪个是哪个？另外，它们与Clojure中的持久性数据结构相比如何？

解决方案

是的，其中大多数是持久性数据结构。 / p>

例如，Elixir列表是链接列表，而链接列表是退化树（它只有一个分支）：

  Elixir：列表= [1、2、3、4] 
树：1-> 2-> 3-> 4 
  

每次将元素添加到列表中时，元素都会共享其尾巴：

  Elixir：[0 | list] 
树：0-> （1-> 2-> 3-> 4）
  

Elixir的HashSet和HashDict实现是基于Clojure的持久数据结构，实际上是树。 约瑟夫的博客上有一些文章。

映射也是持久性数据结构，它们非常有趣，因为它们的表示形式会根据键的数量而变化。如果您有小地图，请说：

 ％{：foo => 1，：bar => 2，：baz => 3} 
  

它表示为：

  -------------（：foo，：bar，：baz）
 | 
（地图，键，值） 
 ------（1、2、3）
  

所以每次更新一个键，我们共享键存储桶，仅更改值存储桶。这对于小型地图非常有效，但是一旦您获得约20个按键（在Erlang 18中），它们就会根据 Hash更改其表示形式数组映射的Tries 也类似于Clojure。

请注意，元组不是持久性的（它们表示内存中的连续空间）。一旦更改了元组中的一个元素，就会创建一个全新的元组。这使它们非常适合保存和访问少量元素以及对其进行模式匹配，但是您绝对不想保留很多元素。

Are all immutable data structures in Elixir persistent? If not, which of them are and which not? Also, how do they compare to the persistent data structures in Clojure?

解决方案

Yes, most of them are persistent data structures.

For example, Elixir lists are linked lists, and a linked list is a degenerate tree (it has only one branch):

Elixir: list = [1, 2, 3, 4]
Tree:   1 -> 2 -> 3 -> 4

Every time you prepend an element to a list, it will share its tail:

Elixir: [0|list]
Tree:   0 -> (1 -> 2 -> 3 -> 4)

Elixir's HashSet and HashDict implementations are based on Clojure's persistent data structures and are effectively trees. There is some write up on Joseph's blog.

Maps are also persistent data structures and they are very interesting because their representation change based on the amount of keys. When you have small maps, let's say:

%{:foo => 1, :bar => 2, :baz => 3}

It is represented as:

        -------------(:foo, :bar, :baz)
        |
(map, keys, values)
               |
               ------(1, 2, 3)

So every time you update one key, we share the "keys" bucket and change only the values bucket. This is very efficient for small maps but once you get to about ~20 keys, in Erlang 18, they change their representation to be based on Hash Array Mapped Tries which is similar to Clojure too.

Note tuples are not persistent though (they represent a contiguous space in memory). Once you change one element in the tuple, a whole new tuple is created. This makes them great for holding and accessing few elements as well as pattern matching on them but you definitely don't want to hold many elements.

这篇关于Elixir是否具有类似于Clojure的持久数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！