[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 11:24:07 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.1.93 (gnu/linux) |
Christian Wittern <cwittern@gmail.com> writes:
> Thierry Volpiatto <thierry.volpiatto <at> gmail.com> writes:
>
>> >> 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]
>>
>> ,----
>> | (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...
>>
>
> This seems to do what I need, thanks! Now I have to see how that
> performs on the real data. I was hoping there would be a method
> that did not involve loops, but some kind of binary search. Would it be
> possible to use a hash-table here?
Yes.
Use loop like this:
,----
| ELISP> (setq A (make-hash-table))
| #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data
| ())
| ELISP> A
| #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data
| (1 "a" 2 "b" 3 "c"))
|
| ELISP> (puthash 1 "a" A)
| "a"
| ELISP> (puthash 2 "b" A)
| "b"
| ELISP> (puthash 3 "c" A)
| "c"
| ELISP> (loop for k being the hash-keys in A
| collect k)
| (1 2 3)
|
| ELISP> (loop for v being the hash-values in A
| collect v)
| ("a" "b" "c")
|
| ELISP> (loop for v being the hash-values in A using (hash-key k)
| collect (list k v))
| ((1 "a")
| (2 "b")
| (3 "c"))
`----
--
Thierry Volpiatto
Gpg key: http://pgp.mit.edu/