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