Re: how to access a large datastructure efficiently?

[Andreas Politz <politza@fh-trier.de>]

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?
>
> Christian 


I don't know how hash-table could help in this case, but maybe you want
to consider binary trees, as implemented in the avl-tree.el package.
Though, there is no function for finding the closest member with respect
to some data and a distance-function, but see below.

Finding a (closest) member should be constraint in logarithmic time.

(require 'avl-tree)

(setq avl (avl-tree-create '<))

(dotimes (i 2000)
  (when (= 0 (% i 4))
    (avl-tree-enter avl i)))

(avl-tree-member avl 80)
=> 80
(avl-tree-member avl 70)
=> nil


(defun avl-tree-closest-member (tree data delta-fn)
  ;; delta-fn : data x data -> Z
  (flet ((comp-delta (node)
           (funcall delta-fn data
                    (avl-tree--node-data node))))
    (let* ((node (avl-tree--root tree))
           closest
           (delta most-positive-fixnum)
           (compare-function (avl-tree--cmpfun tree))
           found)
      (while (and node
                  (not found))
        (when (< (comp-delta node) delta)
          (setq delta (comp-delta node)
                closest node))
        (cond
         ((funcall compare-function data (avl-tree--node-data node))
          (setq node (avl-tree--node-left node)))
         ((funcall compare-function (avl-tree--node-data node) data)
          (setq node (avl-tree--node-right node)))
         (t
          (setq found t))))
      (if closest
          (avl-tree--node-data closest)
        nil))))



(mapcar 
 (lambda (data)
   (avl-tree-closest-member
    avl data (lambda (n1 n2)
               (abs (- n1 n2)))))
 '(1001 1002 1003 1004))

=> (1000 1004 1004 1004)


-ap