[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: how to access a large datastructure efficiently?
From: |
Alan Mackenzie |
Subject: |
Re: how to access a large datastructure efficiently? |
Date: |
Tue, 04 May 2010 15:41:23 -0000 |
User-agent: |
tin/1.6.2-20030910 ("Pabbay") (UNIX) (FreeBSD/4.11-RELEASE (i386)) |
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).
- Re: how to access a large datastructure efficiently?,
Alan Mackenzie <=