Re: how to access a large datastructure efficiently?

[Thierry Volpiatto <thierry.volpiatto@gmail.com>]

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

> Thanks BTW, very interesting
>
> Andreas
>
>
>

-- 
Thierry Volpiatto
Gpg key: http://pgp.mit.edu/