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:
>> 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. ;-)


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

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