Re: how to access a large datastructure efficiently?

["Andreas Röhler" <andreas.roehler@easy-emacs.de>]

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?

Thanks BTW, very interesting

Andreas