nedtrie（按位 trie）搜索操作的复杂性
我最近听说了 nedtries 并决定尝试实现它们，但他们的搜索操作的复杂性让我感到困扰；我无法忍受他们为什么要这么快。
据我了解，他们的搜索操作的预期复杂度应该是 O(m/2)，其中 m 是密钥的大小（以位为单位）。 如果将其与传统二叉树中搜索操作的复杂性进行比较， 你得到： log2(n) >= m/2
假设密钥长度为 32 位： log2(n) >= 16 <=> n >= 65536
因此 nedtries 应该比从 65536 个项目开始的二叉树更快。 然而，作者声称它们总是比二叉树更快，所以我的假设 关于它们的复杂性的判断是错误的，或者在 nedtrie 中搜索的每一步执行的计算要快得多。
那么，那又怎样呢？
I recently heard about nedtries and decided to try implementing them, but something bothers me about the complexity of their search operation; I can't stand why they are supposed to be so fast.
From what I understood, the expected complexity of their search operation should be
O(m/2) with m the size of the key in bits.
If you compare it to the complexity of the search operation in a traditional binary tree,
you get:
log2(n) >= m/2
Let's the key be 32bits long: log2(n) >= 16 <=> n >= 65536
So nedtries should be faster than binary trees starting from 65536 items.
However, the author claim they are always faster than binary tree, so either my assumption
on their complexity is wrong or the computations performed at each step of the search are vastly faster in a nedtrie.
So, what about it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
（请注意，我是 nedtries 的作者）。我认为我在 nedtries 页面前面对复杂性的解释有意义吗？也许不是。
您缺少的关键是，位之间的差异决定了复杂性。差异越大，搜索成本越低，反之差异越小，搜索成本越高。
事实上，它的工作原理源于现代的乱序处理器。作为一个总体简化，如果您避免使用主内存，您的代码运行速度将比依赖主内存时快 40-80 倍。这意味着您可以在从内存加载单个内容的时间内执行 50-150 个操作。这意味着您可以进行位扫描并找出我们接下来应该查看哪个节点，其时间不会比将该节点的缓存行加载到内存中所需的时间长得多。
这有效地消除了复杂性分析中的逻辑、位扫描和其他所有内容。它们都可能是 O(N^N)，这并不重要。现在重要的是，要查看的下一个节点的选择实际上是自由的，因此必须加载进行检查的节点数量是缩放约束，因此它是在总数中查看的节点的平均数量。节点数是其平均复杂度，因为主内存的缓慢性是迄今为止最大的复杂度限制。
这有道理吗？这意味着奇怪的事情，比如如果某些位在密钥的一端密集排列，但在密钥的另一端松散排列，则在密集排列的一端进行搜索将非常慢（接近 O(log N)，其中 N 是数字密集元素）比在松散堆积端搜索（接近 O(1)）要好。
很快有一天，我会抽出时间来添加利用按位尝试这一功能的新函数，因此您可以说“将此节点添加到松散/密集的空间中并返回您选择的密钥”以及各种变体主题。可悲的是，一如既往，这取决于时间和对时间的要求。
尼尔
(Note I'm the author of nedtries). I think my explanation of complexity on the front of the nedtries page makes sense? Perhaps not.
The key you're missing is that it's the difference between bits which determines complexity. The more the difference, the lower the search cost, whereas the lower the difference, the higher the search cost.
The fact this works stems from modern out-of-order processors. As a gross simplification, if you avoid main memory your code runs about 40-80x faster than if you are dependent on main memory. That means you can execute 50-150 ops in the time it takes to load a single thing from memory. That means you can do a bit scan and figure out what node we ought to go look at next in not much longer than the time it takes to load the cache line for that node into memory.
This effectively removes the logic, the bit scanning and everything else from the complexity analysis. They could all be O(N^N) and it wouldn't matter. What matters now is that the selection of the next node to look at is effectively free, so it's the number of nodes which must be loaded for examination is the scaling constraint and therefore it's the average number of nodes looked at out of the total number of nodes which is its average complexity, because main memory's slowness is by far the biggest complexity constraint.
Does this make sense? It means weirdnesses like if some bits are densely packed at one end of the key but loosely packed at the other end of the key, searches in the densely packed end will be very considerably slower (approaching O(log N) where N is the number of dense elements) than searches in the loosely packed end (approaching O(1)).
Someday soon I'll get round to adding new functions which take advantage of this feature of bitwise tries, so you can say "add this node to a loosely/densely packed space and return the key you chose" and all sorts of variations on that theme. Sadly, as always, it comes down to time and demands on one's time.
Niall
如果你有较小的树，你可以使用较小的键！
If you have smaller trees, you can use smaller keys!