基于哈希表的字典/地图结构提供 O(1)
查找时间。然而,我一直看到在Elixir中的含义,找到匹配的函数头比在地图中查找某些东西更快。
例如,Elixir的 String.Unicode
将一个unicode字符列表编译成许多函数头因此,通过找到函数头来回答问“什么是é的最佳版本” upcase
期待“é”。
我不知道为什么这比单个更快或更高的内存效率 upcase
在地图中查找“é”的功能头。
同样,在展示如何在“Metaprogramming Elixir”中构建I18n库时,Chris McCord为每个翻译键提供了自己的功能头,并说:
“通过为每个转换映射生成函数头,我们再次让虚拟机接管快速查找。”
Elixir中的地图不提供O(1)查找吗? 找到匹配的函数头O(1)?为什么选择将静态列表编译为多个函数头而不是仅将其存储在映射中?
Elixir地图不是 平面 基于哈希表的数据结构。小地图是有序列表,其中地图<= 31个条目。当地图获得32个条目时,它将更改为具有查找的哈希特里结构 O(log n)
。毕竟,不可变的基于散列表的数据结构的更新非常昂贵,这是“构建”这些数据结构之一的主要方法。更改一个值将要求您仅使用一个项目更新新地图。它们基于Rich Hickey的持久性哈希映射,这是一种哈希数组映射的trie。
功能头匹配复杂度是 O(n)
最糟糕的情况,但可以通过编译器以我不完全理解的方式进行优化。在某些情况下,它可以将一些功能头模式转换为树。但是因为函数头匹配没有总订单,并且必须按照它们的定义顺序匹配,所以优化量非常有限。您可能只是幸运地使用功能头匹配的非常低的部分以及功能头匹配顺序的树。
头匹配的每一步都非常轻量级且高度优化,其中地图仍然很新,并且有一些性能优化。例如,如果密钥是复杂/嵌套的(例如,简单整数具有非常快的散列函数),则散列函数的复杂性并不简单。但是在你的unicode例子中,我打赌unicode标准,就其命令id的方式而言,将尽可能多的常用字符放在前面。这可能使VM非常容易优化并让您获得 非常 良好的查找时间。我敢肯定,如果你查找一个不起眼的字母表,你的复杂性就会改变。
但是,不仅动态生成具有函数匹配的模块作为查找数据的方式的原因在于您将颠覆全局状态,特别是code_server模块。一些查找可能会更快,但随着数据结构变大,加速可能会减慢。