我想使用隐式指针实现一个缓存无关的二叉树,它使用van Emde Boas布局存储在一个数组中.树中的所有项都是32位整数,并且树会变得相当大,因此存储指针意味着至少要多3倍的数据.
问题在于,在给定节点索引(我可以在遍历树时跟踪任何信息)时,我无法想到计算指向左右子节点的指针的任何非迭代方法.许多论文/讲座都是用隐式指针引用这些树,但我还没有看到计算指针的算法.有没有一种有效的方法呢？
我已经阅读了很多关于Cache Oblivious Algorithms和Streaming树等的内容.我理解我仍然无法看到的基础知识是什么它们对并行编程有好处？我想我看到John Harrop说他们是革命性的.
我理解表达式缓存无意义的含义.但我想知道是否有任何简单的解释,如何设计数据结构,可以最佳地使用缓存,而不知道缓存的大小.
您能否提供这样的解释,最好是(简单)示例？