[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: how to access a large datastructure efficiently?
From: |
Andreas Politz |
Subject: |
Re: how to access a large datastructure efficiently? |
Date: |
Thu, 04 Mar 2010 17:49:54 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.1 (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?
>
> 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