是否在Elixir O（1）中查找地图？ [英] Is map lookup in Elixir O(1)?

问题描述

基于哈希表的dict / map结构提供了 O（1）查找时间。但是，我一直看到这样的含义：在Elixir中，找到匹配的函数头比在地图中查找内容更快。

Hash-table-based dict/map structures provide O(1) lookup time. Yet I keep seeing implications that in Elixir, finding a matching function head is faster than looking up something in a map.

例如，Elixir的 String .Unicode 将Unicode字符列表编译成许多函数头，以便通过查找 upcase 的函数头来回答é的大写版本是什么

For instance, Elixir's String.Unicode compiles a list of unicode characters into many function heads, so that asking "what's the upcase version of é" is answered by finding the function head for upcase that expects "é".

我不知道为什么它比有一个大写

I don't know why this would be faster or more memory efficient than having a single upcase function head that looks up "é" in a map.

类似地，当演示如何在元编程药剂中构建I18n库时，克里斯·麦考德（Chris McCord）会给每个函数头翻译键具有其自己的功能头，并说：

Similarly, when showing how to build an I18n library in "Metaprogramming Elixir", Chris McCord gives each translation key its own function head, and says:

通过为每个翻译映射生成功能头，我们再次让Virtu

"By generating function heads for each translation mapping, we again let the Virtual Machine take over for fast lookup."

Elixir中的地图不提供O（1）查找吗？ >是否找到匹配的函数头O（1）？为什么选择将静态列表编译为多个函数头而不是仅将其存储在映射表中？

Do maps in Elixir not provide O(1) lookup? Is finding a matching function head O(1)? Why opt for compiling a static list to many function heads instead of just storing it in a map?

推荐答案

Elixir映射表不是 flat 基于哈希表的数据结构。小地图是有序列表，其中地图有< = 31个条目。当映射获得32个条目时，它将变为具有 O（log n）查找的哈希树。毕竟，基于不可变哈希表的数据结构更新非常昂贵，这是构建这些数据结构之一的主要方法。更改一个值将需要您仅添加一个项目来更新新地图。它们基于Rich Hickey的持久性哈希映射，这是一种哈希数组映射的特里。

Elixir maps aren't flat hash-table-based datastructures. Small maps are ordered lists where the map has <= 31 entries. When a map gets 32 entries, it changes to a hash trie that has a lookup of O(log n). Immutable hash-table-based datastructures would be very expensive to update, after all, which is the primary method of "building up" one of these datastructures. Changing one value would require you to update a new map with just 1 more item. They're based on Rich Hickey's persistent hashmaps, which are a kind of hash array mapped trie.

函数头匹配的复杂度为 O（n） 最坏的情况，但是编译器可以用我不完全了解的方式对其进行优化。在某些情况下，它可以将某些功能头模式变成一棵树。但是由于函数头匹配没有总顺序，并且必须按照定义它们的顺序进行匹配，因此优化的数量非常有限。您可能只是幸运地使用了功能标头匹配的非常低的部分，并且也使用了功能标头匹配顺序的树。

Function head match complexity is O(n) worst-case, but can be optimized by the compiler in ways I do not fully understand. In some cases, it can turn some function head patterns into a tree. But because function head matches do not have a total order, and must match in the order in which they are defined, the amount of optimization is pretty limited. You might just be getting lucky in using parts of the function head match that are very low and also in a tree of the function head matching order.

标头的每一步match也非常轻巧且经过高度优化，其中地图仍然是相当新的，并且需要进行一些性能优化。例如，如果键是复杂的/嵌套的，则哈希函数的复杂性并不简单（但是，简单的整数具有非常快的哈希函数）。但在您的unicode示例中，我敢打赌unicode标准会根据其对ID排序的方式将其尽可能多的常用字符放在前面。这可能使VM非常容易优化，并使您获得非常的良好查找时间。我敢肯定，如果您查找一个晦涩的字母，您的复杂性将会改变。

Each step of a head match is also quite lightweight and highly optimized, where maps are still quite new and there are some performance optimizations to be had. The complexity of the hash function, for instance, is not simple if the key is complex/nested (simple integers, however, have very fast hash functions). But in your unicode example, I bet the unicode standard, by nature of how it orders the id's, puts as many of their commonly-used characters in the front. This probably makes it very easy for the VM to optimize and for you to get very good lookup times. I'm sure if you looked up an obscure alphabet, your complexity would change.

但是原因不只是动态地生成功能匹配的模块查找数据是您将要破坏全局状态，尤其是code_server模块。有些查询的速度可能更快，但是随着数据结构的增大，这些查询的速度可能会降低。

But the reason one wouldn't just dynamically generate a module with function matching as the way to look up data is that you would thrash global state, in particular the code_server module. Some of the lookups may go faster, but the speedups would probably slow way down as the datastructure got bigger.

这篇关于是否在Elixir O（1）中查找地图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！