[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: how to access a large datastructure efficiently?
From: |
Pascal J. Bourguignon |
Subject: |
Re: how to access a large datastructure efficiently? |
Date: |
Tue, 04 May 2010 15:41:28 -0000 |
User-agent: |
Gnus/5.11 (Gnus v5.11) Emacs/22.3 (darwin) |
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