Re: how to access a large datastructure efficiently?

[Alan Mackenzie <acm@muc.de>]

Hi, Christian,

Christian Wittern <cwittern@gmail.com> wrote:
> Hi there,

> Here is the problem I am trying to solve:

> I have a large list of items which I want to access.  The items are in 
> sequential order, but many are missing in between, like:

> (1 8 17 23 25 34 45 47 50)  [in reality, there is a value associated 
> with this, but I took it out for simplicity]

> Now when I am trying to access with a key that is not in the list, I 
> want to have the one with the closest smaller key returned, so for 6 
> and 7 this would be 1, but for 8 and 9 this would be 8.

> Since the list will have thousands of elements, I do not want to simply 
> loop through it but am looking for better ways to do this in Emacs lisp.  
> Any ideas how to achieve this?

You may want to use some sort of optimised tree structure, such as a
B-tree or an AVL-tree.  I am not an expert on such things.  There is an
article on the AVL-tree on the emacs wiki at
<http://www.emacswiki.org/emacs/AVLtrees>.

This may be what you want.  But I would try it first with a normal flat
list, and only go to the more complex data structure when the first try
really, really isn't fast enough.

> Christian

-- 
Alan Mackenzie (Nuremberg, Germany).