Re: how to access a large datastructure efficiently?

[pjb@informatimago.com (Pascal J. Bourguignon)]

Christian Wittern <cwittern@gmail.com> writes:

> 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?

Why do you have a list?

If you had a vector, you could do a dichotomy, and find it in O(log(n)).

Or, if you need to insert or remove elements between searches, as the
others have advised, use a binary tree, preferablemente a balanced
binary tree.  I prefer the left-leaning red-black trees over the avl
trees. 



-- 
__Pascal Bourguignon__
http://www.informatimago.com