From b6fe2eb4cf9df6923f11c7f24e9da0af7b48d24a Mon Sep 17 00:00:00 2001
From: Andreas Roehler <andreas.roehler@online.de>
Date: Thu, 4 Mar 2010 20:43:07 +0100
Subject: [PATCH] access a large datastructure

---
 code/elbb.el | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)

diff --git a/code/elbb.el b/code/elbb.el
index 4f179d8..0db8b24 100644
--- a/code/elbb.el
+++ b/code/elbb.el
@@ -1,3 +1,103 @@
+* how to access a large datastructure efficiently?
+
+To: help-gnu-emacs@gnu.org
+From: Thierry Volpiatto <thierry.volpiatto@gmail.com>
+Date: Thu, 04 Mar 2010 17:09:35 +0100
+Subject: Re: how to access a large datastructure efficiently?
+
+Andreas Röhler <andreas.roehler@easy-emacs.de> writes:
+
+> Thierry Volpiatto wrote:
+>> Andreas Röhler <andreas.roehler@easy-emacs.de> writes:
+>> 
+>>> Thierry Volpiatto wrote:
+>>>> Thierry Volpiatto <thierry.volpiatto@gmail.com> writes:
+>>>>
+>>>>> Hi,
+>>>>>
+>>>>> 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?
+>>>>> ,----
+>>>>> | (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?
+>> 
+>> No, in this case:
+>> 
+>> if (eq i elm) return (list i) ==> (i) ; which is n
+>> 
+>> and finally (car pair) ==> n
+>> 
+>
+> Hmm, sorry being the imprecise,
+> aimed at the first form, whose result equals the the second form once implemented this "="
+
+Ok, i understand, yes, we can do what you say and it's more elegant, i
+just notice also i forget to remove a unuseful else:
+
+,----
+| (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 should work the same.
+Thanks. ;-)
+
+-- 
+Thierry Volpiatto
+Gpg key: http://pgp.mit.edu/
+
 * cedet and auto-complete
 
 To: help-gnu-emacs@gnu.org
-- 
2.11.4.GIT