From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: =?ISO-8859-1?Q?Andreas_R=F6hler?= Newsgroups: gmane.emacs.help Subject: Re: how to access a large datastructure efficiently? Date: Thu, 04 Mar 2010 09:13:48 +0100 Message-ID: <4B8F6BBC.2000607@easy-emacs.de> References: <873a0gshb6.fsf@tux.homenetwork> <87y6i8r1j3.fsf@tux.homenetwork> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1267690411 11476 80.91.229.12 (4 Mar 2010 08:13:31 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 4 Mar 2010 08:13: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 Thu Mar 04 09:13:26 2010 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 1Nn6BR-0005Gv-D7 for geh-help-gnu-emacs@m.gmane.org; Thu, 04 Mar 2010 09:13:25 +0100 Original-Received: from localhost ([127.0.0.1]:51736 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Nn6BQ-0005oT-DO for geh-help-gnu-emacs@m.gmane.org; Thu, 04 Mar 2010 03:13:24 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1Nn6Ak-0005ny-MJ for help-gnu-emacs@gnu.org; Thu, 04 Mar 2010 03:12:42 -0500 Original-Received: from [140.186.70.92] (port=42208 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Nn6Aj-0005f2-Mb for help-gnu-emacs@gnu.org; Thu, 04 Mar 2010 03:12:42 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1Nn69d-0006KS-0d for help-gnu-emacs@gnu.org; Thu, 04 Mar 2010 03:11:33 -0500 Original-Received: from moutng.kundenserver.de ([212.227.126.171]:54375) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1Nn69c-0006KN-Kc for help-gnu-emacs@gnu.org; Thu, 04 Mar 2010 03:11:32 -0500 Original-Received: from [192.168.178.27] (p54BE98DD.dip0.t-ipconnect.de [84.190.152.221]) by mrelayeu.kundenserver.de (node=mreu2) with ESMTP (Nemesis) id 0LuYaa-1NeKlD1MR6-010FNi; Thu, 04 Mar 2010 09:11:27 +0100 User-Agent: Thunderbird 2.0.0.19 (X11/20081227) In-Reply-To: <87y6i8r1j3.fsf@tux.homenetwork> X-Provags-ID: V01U2FsdGVkX1+C8HChweZ66qqetp8SSIJao2mtdBawFIfjkIQ KXktlDUoPeF05lg5/6+X7z0v9RtLE3tuZJNPzMC0+wNZMIOd9b fNouQKPh8WcS37gelC24izh9AC1Cggc1tXcyGvOCF0= X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. 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:72355 Archived-At: Thierry Volpiatto wrote: > Thierry Volpiatto writes: > >> Hi, >> >> 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? >> ,---- >> | (defun closest-elm-in-seq (n seq) >> | (let ((pair (loop with elm = n with last-elm >> | for i in seq >> | if (and last-elm (< last-elm elm) (> i elm)) return (list last-elm i) >> | do (setq last-elm i)))) >> | (if (< (- n (car pair)) (- (cadr pair) n)) >> | (car pair) (cadr pair)))) >> `---- >> >> That return the closest, but not the smaller closest, but it should be >> easy to adapt. > > Case where your element is member of list, return it: > > ,---- > | (defun closest-elm-in-seq (n seq) > | (let ((pair (loop with elm = n with last-elm > | for i in seq > | if (eq i elm) return (list i) > | else if (and last-elm (< last-elm elm) (> i elm)) return (list last-elm i) > | do (setq last-elm i)))) > | (if (> (length pair) 1) > | (if (< (- n (car pair)) (- (cadr pair) n)) > | (car pair) (cadr pair)) > | (car pair)))) > `---- > For the smallest just return the car... > if n is member of the seq, maybe equal-operator too (<= last-elm elm) is correct? Thanks BTW, very interesting Andreas