Thursday, October 22, 2015

Optimal Layout of Static Arrays for Search

A recent publication has some surprising results. Elements are commonly stored in sorted order to allow for efficient binary search. An analysis of the different layouts (B-tree, sorted array, van Emde Boas, etc) has found that the Eytzinger layout (invented in 1590!) is actually the optimal layout.

http://arxiv.org/abs/1509.05053

No comments:

Post a Comment