[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: how to access a large datastructure efficiently?
From: |
Thierry Volpiatto |
Subject: |
Re: how to access a large datastructure efficiently? |
Date: |
Thu, 04 Mar 2010 12:00:17 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.1.93 (gnu/linux) |
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/
- how to access a large datastructure efficiently?, Christian Wittern, 2010/03/03
- Re: how to access a large datastructure efficiently?, Christian Wittern, 2010/03/04
- Re: how to access a large datastructure efficiently?, Thierry Volpiatto, 2010/03/04
- Re: how to access a large datastructure efficiently?, Thien-Thi Nguyen, 2010/03/04
- Re: how to access a large datastructure efficiently?, Andreas Politz, 2010/03/04