Re: how to access a large datastructure efficiently?

[Thierry Volpiatto <thierry.volpiatto@gmail.com>]

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/