Re: Lists and Vectors

[Pascal J. Bourguignon]

Nordlöw <per.nordlow@gmail.com> writes:

> If I have an association list say,
>
> '(
>   ("key" sym1 val1 num1)
>   ("key2" sym2 val2 num2)
> )
>
> , where each entry is a fixed sequence of various objects. 

If this is an a-list, then you could write it as:

   (("key1" . (sym1 val1 num1))
    ("key2" . (sym2 val2 numb2)))

to show that it is a list of cons cells.  

(a . (b c d)) <=> (a b c d), but the first notation shows that you
consider it as a list of cons, and notably that you don't expect nil
ie. () to be in the toplevel of the a-list.

Also, if we write the a-list properly like this, we can better answer
the following question:

> I might
> aswell use a vector to represent an entry in this alist, right?

You cannot use a vector instead of the cons cells of the a-list, but
you can use a vector as a value of an a-list entry.  Values can be of
any type.  In the case of emacs lisp, you could also easily use
vectors (or any other type) as keys in an a-list, since it uses equal
to compare keys.  

   (("key1" . [sym1 val1 num1])
    ("key2" . [sym2 val2 num2])
    ([?k ?e ?y ?3] . [sym3 val3 num3]))



> In this case, what do I gain by using a vector instead of list?

In general, vectors take half the space of lists, and access to the
nth element is done in O(1) instead of O(n) with lists.  However,
adding or removing an element in a vector is O(n) while in the case of
lists, it may be O(1) (prepending an element or removing the first
element or one of the few firsts elements) or O(n) (inserting,
appending an element or removing the nth element).


> What about performance?: aref() faster than nth() only for large
> vectors?

aref has to compute a multiplication and a sum, before doing one
memory load to get the element.  In the case of emacs lisp, the
multiplication is always by the same fixed factor AFAIK.

nth has to do n memory loads to get the element.

So indeed, aref will probably be faster than nth, even for indices as
small as 1 or 0.


> Is there vector-variant of assoc()? 

No.  Unless you count hash-tables as a vector variant.


> If not, why? 

Because there's no point. The advantage of using a list for a-list,
apart from the historical simplicity, is that you can easily prepend
the a-list with new associations, and therefore use the a-list in a
purely functional way.


   (defun f (bindings)
      (let ((val (cdr (assoc 'x bindings))))
         (if (zerop val)
             (list val)
             (cons val (f (cons (cons 'x (1- val)) bindings))))))

   (let ((bindings '((y . 0) (x . 1))))
      (list (f (cons (cons 'x 2) bindings))
            (cdr (assoc 'x bindings))))
   --> ((2 1 0) 1)



Note: you could use (require 'cl)  (acons key value a-list) 
      instead of (cons (cons key value) a-list).


> Has any one already written such a function?

Not AFAIK, but you can write it.  However, the semantics of assoc
require a sequential search of the keys in the list, so there would be
no gain.  On the contrary, we would now have O(n) complexity to
prepend a new entry to the a-vector.


-- 
__Pascal Bourguignon__