how to access a large datastructure efficiently?

how to access a large datastructure efficiently?

[Christian Wittern]

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?

Christian

Re: how to access a large datastructure efficiently?

[Thierry Volpiatto]

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.

-- 
Thierry Volpiatto
Gpg key: http://pgp.mit.edu/

Re: how to access a large datastructure efficiently?

[Thierry Volpiatto]

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...

-- 
Thierry Volpiatto
Gpg key: http://pgp.mit.edu/

Re: how to access a large datastructure efficiently?

[Andreas Röhler]

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?

Thanks BTW, very interesting

Andreas

Re: how to access a large datastructure efficiently?

[Christian Wittern]

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 

Re: how to access a large datastructure efficiently?

[Thierry Volpiatto]

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/

Re: how to access a large datastructure efficiently?

[Alan Mackenzie]

Hi, Christian,

Christian Wittern <cwittern@gmail.com> wrote:
> 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?

You may want to use some sort of optimised tree structure, such as a
B-tree or an AVL-tree.  I am not an expert on such things.  There is an
article on the AVL-tree on the emacs wiki at
<http://www.emacswiki.org/emacs/AVLtrees>.

This may be what you want.  But I would try it first with a normal flat
list, and only go to the more complex data structure when the first try
really, really isn't fast enough.

> Christian

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: how to access a large datastructure efficiently?

[Thierry Volpiatto]

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/

Re: how to access a large datastructure efficiently?

[Thien-Thi Nguyen]

() Christian Wittern <cwittern@gmail.com>
() Thu, 4 Mar 2010 08:15:47 +0000 (UTC)

   some kind of binary search

How do you binary search a singly-linked list?

thi

Re: how to access a large datastructure efficiently?

[Andreas Röhler]

Thierry Volpiatto wrote:
> 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
> 

Hmm, sorry being the imprecise,
aimed at the first form, whose result equals the the second form once implemented this "="

Andreas

>> Thanks BTW, very interesting
>>
>> Andreas
>>
>>
>>
> 

Re: how to access a large datastructure efficiently?

[Thierry Volpiatto]

Andreas Röhler <andreas.roehler@easy-emacs.de> writes:

> Thierry Volpiatto wrote:
>> 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
>> 
>
> Hmm, sorry being the imprecise,
> aimed at the first form, whose result equals the the second form once implemented this "="

Ok, i understand, yes, we can do what you say and it's more elegant, i
just notice also i forget to remove a unuseful else:

,----
| (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 should work the same.
Thanks. ;-)


> Andreas
>
>>> Thanks BTW, very interesting
>>>
>>> Andreas
>>>
>>>
>>>
>> 
>
>
>
>

-- 
Thierry Volpiatto
Gpg key: http://pgp.mit.edu/

Re: how to access a large datastructure efficiently?

[Andreas Politz]

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

Re: how to access a large datastructure efficiently?

[Pascal J. Bourguignon]

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?

Why do you have a list?

If you had a vector, you could do a dichotomy, and find it in O(log(n)).

Or, if you need to insert or remove elements between searches, as the
others have advised, use a binary tree, preferablemente a balanced
binary tree.  I prefer the left-leaning red-black trees over the avl
trees. 



-- 
__Pascal Bourguignon__
http://www.informatimago.com

Re: how to access a large datastructure efficiently?

[Stefan Monnier]

> 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]

If those integer-valued keys are really positions in a buffer, then
a good solution might be to store this "list" as a text property.


        Stefan