publicclassDigitTrie{publicstaticfinalintRADIX=7;// Array of objects. Can itself contain an array of objects.Object[]root;// The maximal size/length of a child node (1 if leaf node)intrDepth;// equivalent to RADIX ** (depth - 1)publicObjectlookup(intkey){Object[]node=this.root;// perform branching on internal nodes herefor(intsize=this.rDepth;size>1;size/=RADIX){node=(Object[])node[(key/size)%RADIX];// If node may not exist, check if it is null here}// Last element is the value we want to lookup, return it.returnnode[key%RADIX];}}
rDepth 的值表示根节点的一个子节点的最大大小:一个有 n 个数字组成的数字,将拥有 RADIX 的 n 次幂数量的可能值,而且我们必须能将它们毫无冲突地全部放入前缀树。
在 lookup 方法的 for 循环里,size 的值表示当前节点的一个子节点的可以拥有的最大大小。对于每个我们访问过的子节点,这个 size 大小被分支因子递减,分支因子即是数字前缀树的基数。
但是,这样做为什么更快呢?通过使用一些位运算的技巧,我们可以同时消除整数的除法和取模。如果 power 是 2 的 n 次幂,我们可以得到 x / power == x >>> n[4] 和 x % power == x & (power - 1)。这两个公式其实是等价,跟整数的本质表示有关,也就是位组成的序列。
如果我们使用这个结果,并和前面的实现组合起来,我们将得到下列代码:
1234567891011121314151617181920212223
publicclassBitTrie{publicstaticfinalintBITS=5,WIDTH=1<<BITS,// 2^5 = 32MASK=WIDTH-1;// 31, or 0x1f// Array of objects. Can itself contain an array of objects.Object[]root;// BITS times (the depth of this trie minus one).intshift;publicObjectlookup(intkey){Object[]node=this.root;// perform branching on internal nodes herefor(intlevel=this.shift;level>0;level-=BITS){node=(Object[])node[(key>>>level)&MASK];// If node may not exist, check if it is null here}// Last element is the value we want to lookup, return it.returnnode[key&MASK];}}
#!/bin/bashbash ./configure --with-freetype-include=/usr/X11/include/freetype2 --with-freetype-lib=/usr/X11/lib
\ --enable-ccache --disable-warnings-as-errors
make clean
make all
不过,我们还是遇到这样一个问题:在函数之间参数的不匹配,我们无法保证每个函数的参数列表维持一个一致的风格,特别是涉及到二方或者三方库的调用的时候,你在 A 函数里调用 B,在 A 内部对 A 输入的参数做了一些处理,添加、移除或者转换参数列表后传入给 B 函数,这里就就有所谓阻抗不匹配的问题。如果 A 要在内部对 B 发起多次调用,并在 B 的参数列表已经长的话,无可避免代码显得非常累赘。