CODEWITHSUNDEEP
algorithmoptimizationdata-structureslanguage-agnostic
MaiaVictor
MaiaVictor

Reputation: 53017

What is fast, compact representation of tree structures that prevents cache misses?

Graphical applications often represent images as flat arrays, instead of bidimensional arrays. If I'm not mistaken, this is done because flat arrays are much faster as they're compact and avoid cache misses. Example:

dimensional_array = [[1,2],[3,4],[4,5]]
four = dimensional_array[1,1]

flat_array = [1,2,3,4,5,6]
four = flat_array[1 + 2*1]

Is there a similar (or not) representation of free-form trees that allows for the same kind of performance gain?

free_form_tree = [[1,2,3],4,5,[[6,7],8]]

Upvotes: 4

Views: 1046

Answers (3)

Justin
Justin

Reputation: 4216

If your tree is fairly complete (or you don't care as much about wasting space) and can fit into memory then you can store the tree in an array. You can use the same formula that an array based heap uses to "search" the tree.

  • root is at index 0
  • Children are always at indices (2*i + 1) and (2*i + 2) where i is your current index.
  • Their parent is floor((i − 1) ∕ 2) where i is a child's index.

Storing binary tree as an array.

Also, see heap details here.

Upvotes: 3

Vikram Bhat
Vikram Bhat

Reputation: 6246

You can use a postorder or perorder representation of tree along with inorder representation but again then if there is change in tree then you recompute then in O(n) which is expensive for small speed up. Other implementations like B-tree or advance hybrid datastructure are complex to implement and not worthy of your time for relatively small speed up. Because all operations in tree are O(logn) for balanced tree so cache can only give speed up by some constant factor which is insignificant compared to O(logN)

Upvotes: 1

justhalf
justhalf

Reputation: 9117

You can read up on B-trees.

It is designed to read a block of its data from memory, thereby increasing memory performance.

You can look up more on Google using this query: "Cache oblivious tree" to get more links such as this

Upvotes: 1

Related Questions