Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array.
The binary tree is full on all levels except possibly the last level, where it is filled from left to right.
Specifically index 0 is the root node, and to get to a left child, you multiply current index by 2 and add 1. To get to a right child you multiply current index by 2 and add 2.
Going this route, as i understand it, the node order is breadth first.
I've seen people mention that depth first is better (in a paper about parallel GPU bvh construction), and was wondering, is there a good reason to choose depth first over breadth first, or is it highly dependent on specific usage patterns?
Asked By : Alan Wolfe
Answered By : KWillets
There's a paper on this: Khuong and Morin. Array Layouts For Comparison-Based Searching
They compare the Eytzinger, B-Tree, Van Emde Boas, and sorted array layouts and conclude that Eytzinger works best. The reasons are fairly complex, since things like simple address arithmetic and branch predictability combine with memory prefetch and processor features like speculative execution. They also rely on doing a fair amount of extra work by prefetching blocks which have only a small chance of matching the search argument.
However they do give a clear exposition of each mechanism.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/51443
0 comments:
Post a Comment
Let us know your responses and feedback