fok*_*ute 1 complexity-theory bit-manipulation trie
我最近听说过nedtries并决定尝试实现它们,但是有些事情让我对它的搜索操作的复杂性感到困扰; 我不能忍受为什么他们应该这么快.
根据我的理解,他们的搜索操作的预期复杂性应该是O(m/2),其中m是密钥的大小.如果将它与传统二叉树中搜索操作的复杂性进行比较,则得到:log2(n)> = m/2
设密钥为32位长:log2(n)> = 16 <=> n> = 65536
因此,从65536个项目开始,nedtries应该比二叉树更快.然而,作者声称他们总是比二叉树更快,所以我对其复杂性的假设是错误的,或者在搜索的每一步执行的计算在nedtrie中都要快得多.
那么,它呢？
(注意我是nedtries的作者).我认为我对nedtries页面前面的复杂性的解释是有道理的吗？也许不是.
你缺少的关键是它是决定复杂性的比特之间的差异.差异越大,搜索成本越低,而差异越小,搜索成本越高.
这项工作的事实源于现代无序处理器.作为一个简单的简化,如果你避免使用主内存,你的代码运行速度比依赖主内存快40-80倍.这意味着您可以在从内存加载单个内容的时间内执行50-150个操作.这意味着您可以进行一些扫描并找出我们应该在下一个节点查看的节点,其时间不会超过将该节点的缓存行加载到内存所需的时间.
这有效地消除了逻辑,位扫描以及复杂性分析中的所有其他内容.它们都可以是O(N ^ N)并且无关紧要.现在重要的是,要查看的下一个节点的选择实际上是免费的,因此必须加载以供检查的节点数是缩放约束,因此它是从总数中查看的平均节点数.节点是它的平均复杂度,因为主内存的缓慢是迄今为止最大的复杂性约束.
这有意义吗？这意味着奇怪的是,如果某些位密集地堆在密钥的一端但是在密钥的另一端松散地打包,那么在密集的端搜索将非常慢(接近O(log N),其中N是数字密集元素)比在松散包装的末端搜索(接近O(1)).
有一天我很快就会添加新功能,利用按位尝试的这个功能,所以你可以说"将这个节点添加到一个松散/密集的空间并返回你选择的密钥",以及各种各样的变化.主题.可悲的是,一如既往,它归结为时间和对一个人的要求.
尼尔