我正在阅读Peter Brass的高级数据结构.
在关于搜索树的章节的开头,他说有两种搜索树模型 - 一种是节点包含实际对象(如果树用作字典的值),另一种是所有对象存储在叶子和内部节点仅用于比较.
第二个模型比第一个模型有什么优势？
我正在从事计算生物学项目,我需要存储许多序列之间不同的基因座索引.现在,我正在使用B +树来实现这个目的,但我想使用位图索引对于这样一个用例会更快:两个序列之间只有少数基因座不同,平均为1%,而且它们是沿序列分布几乎相等; 所以似乎有很大的位图索引压缩空间.我的问题是我无法找到一种可以高效的压缩方法:
请提前获取您的建议.
在我目前的项目中,我必须比较128位值(实际上是md5哈希),我认为可以通过使用SSE指令来加速比较.我的问题是我无法找到关于SSE指令的好文档; 我正在寻找一个128位整数比较指令,让我知道一个散列是大于,小于或等于另一个.这样的指令是否存在？
PS:目标计算机是带有SSE2指令的x86_64服务器; 我也对同一工作的NEON指令感兴趣.
I.刚刚实现了一种按位trie(基于nedtries),但我的代码执行了很多内存分配(对于每个节点).与我的实现相反,在其他事物中声称nedtries很快,因为它们的内存分配数量很少(如果有的话).作者声称他的实施是"就地"的,但在这种情况下它的真正含义是什么？nedtries如何实现如此少量的动态内存分配？
Ps:我知道源代码可用,但代码很难遵循,我无法弄清楚它是如何工作的
在一个项目中,我目前的工作,我经常需要找到在其中的元素可以插入一个排序的数组可能的最低指数(C中类似的std :: LOWER_BOUND ++).我使用SSE加速我的算法似乎很吸引人,因为我正在使用uint32数组,其大小通常是处理器缓存行的大小.我之前从未使用过SSE指令,所以我无法弄清楚这个函数的SSE实现会是什么样子.请给出提示,以帮助我最好地用SSE写出来.
我最近听说过nedtries并决定尝试实现它们,但是有些事情让我对它的搜索操作的复杂性感到困扰; 我不能忍受为什么他们应该这么快.
根据我的理解,他们的搜索操作的预期复杂性应该是O(m/2),其中m是密钥的大小.如果将它与传统二叉树中搜索操作的复杂性进行比较,则得到:log2(n)> = m/2
设密钥为32位长:log2(n)> = 16 <=> n> = 65536
因此,从65536个项目开始,nedtries应该比二叉树更快.然而,作者声称他们总是比二叉树更快,所以我对其复杂性的假设是错误的,或者在搜索的每一步执行的计算在nedtrie中都要快得多.
那么,它呢？