From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Alan Mackenzie Newsgroups: gmane.emacs.help Subject: Re: how to access a large datastructure efficiently? Date: Thu, 4 Mar 2010 10:36:10 +0000 (UTC) Organization: muc.de e.V. Message-ID: References: NNTP-Posting-Host: lo.gmane.org X-Trace: dough.gmane.org 1272988531 29885 80.91.229.12 (4 May 2010 15:55:31 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Tue, 4 May 2010 15:55:31 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Tue May 04 17:55:30 2010 connect(): No such file or directory Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1O9KT2-00076Q-A2 for geh-help-gnu-emacs@m.gmane.org; Tue, 04 May 2010 17:55:28 +0200 Original-Received: from localhost ([127.0.0.1]:37494 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O9KT1-0004I0-SE for geh-help-gnu-emacs@m.gmane.org; Tue, 04 May 2010 11:55:27 -0400 Original-Path: usenet.stanford.edu!news.glorb.com!news2.glorb.com!feeder.erje.net!newsfeed.freenet.ag!newsfeed.freenet.de!news.tu-darmstadt.de!news.muc.de!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 35 Original-NNTP-Posting-Host: marvin.muc.de Original-X-Trace: colin2.muc.de 1267698970 16045 2001:608:1000::2 (4 Mar 2010 10:36:10 GMT) Original-X-Complaints-To: news-admin@muc.de Original-NNTP-Posting-Date: Thu, 4 Mar 2010 10:36:10 +0000 (UTC) User-Agent: tin/1.6.2-20030910 ("Pabbay") (UNIX) (FreeBSD/4.11-RELEASE (i386)) Original-Xref: usenet.stanford.edu gnu.emacs.help:177339 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:72900 Archived-At: Hi, Christian, Christian Wittern 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 . 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).