Re: how to access a large datastructure efficiently?

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

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 "="

Andreas

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