From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: pjb@informatimago.com (Pascal J. Bourguignon) Newsgroups: gmane.emacs.help Subject: Re: how to access a large datastructure efficiently? Date: Thu, 04 Mar 2010 21:22:16 +0100 Organization: Informatimago Message-ID: <87hbovn8g7.fsf@informatimago.com> References: NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1272988964 32050 80.91.229.12 (4 May 2010 16:02:44 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Tue, 4 May 2010 16:02:44 +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 18:02:43 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 1O9Ka1-0002v9-57 for geh-help-gnu-emacs@m.gmane.org; Tue, 04 May 2010 18:02:41 +0200 Original-Received: from localhost ([127.0.0.1]:51372 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O9Ka0-0007Jc-R3 for geh-help-gnu-emacs@m.gmane.org; Tue, 04 May 2010 12:02:40 -0400 Original-Path: usenet.stanford.edu!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 34 Original-X-Trace: individual.net ij/gxy8ojRqhK4uVlst79wFBSGp5FvfD0UhWCVwz94/9fO6Sw0 Cancel-Lock: sha1:OGEzYTBmM2Y3Mzk4MjJhNWVlNjU0Mjk4NjM4ZGFiNTRlY2UxM2M0Zg== sha1:tcNbUEGeum+9pgaRbCdcLB8yN38= Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwAQMAAABtzGvEAAAABlBMVEUAAAD///+l2Z/dAAAA oElEQVR4nK3OsRHCMAwF0O8YQufUNIQRGIAja9CxSA55AxZgFO4coMgYrEDDQZWPIlNAjwq9 033pbOBPtbXuB6PKNBn5gZkhGa86Z4x2wE67O+06WxGD/HCOGR0deY3f9Ijwwt7rNGNf6Oac l/GuZTF1wFGKiYYHKSFAkjIo1b6sCYS1sVmFhhhahKQssRjRT90ITWUk6vvK3RsPGs+M1RuR mV+hO/VvFAAAAABJRU5ErkJggg== X-Accept-Language: fr, es, en X-Disabled: X-No-Archive: no User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.3 (darwin) Original-Xref: usenet.stanford.edu gnu.emacs.help:177354 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:72906 Archived-At: Christian Wittern 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