我正在尝试了解在
here描述的simipiled缓存隐藏的前瞻阵列,从
this presentation的第35页
Analysis of Insertion into Simplified
Fractal Tree:
- Cost to merge 2 arrays of size X is O(X=B) block I/Os. Merge is very
I/O efficient.- Cost per element to merge is O(1/B) since O(X) elements were
merged.- Max # of times each element is merged is O(logN).
- Average insert cost is O(logN/B)
我可以手写#1,#2和#3,但我不明白#4,从论文中,合并可以被认为是二进制加载,例如(31)B可以呈现：
11111
当插入新项目(加1)时,应该有5 = log(32)merge(5进位).但是,在这种情况下,我们必须合并32个元素！另外,如果每次加1,那么从0到2 ^ k将执行多少个系统？流氓应该是2 ^ k – 1.换句话说,一个插入合并！
那么#4如何计算？
解决方法
虽然你是正确的,在最坏的情况下,合并元素的数量(和转移)是N,并且总合并的数量也是相同的顺序,平均插入成本仍然是对数.它来自两个事实：合并成本不同,低成本合并的数量远高于高成本合并的数量.
这可能比较容易看出.
我们设置B = 1(即每个块1个元素,每个合并的最坏情况是一个成本)和N = 32(例如,我们将32个元素插入最初的空数组).
一半的插入(16)将元素放入大小为1的空子阵列中,因此不会导致合并.剩下的插入中,一个(最后一个)需要合并(移动)32个元素,一个(第16个)移动16个,第2个(第8个和第24个)移动8个元素,4个移动4个元素,以及8个移动2个元素.因此,元素移动的总数为96,给每个插入平均3次移动.
希望有帮助.
