headers
John Lapeyre | 8 Sep 05:37

endcons

I think the Maxima manual should mention somewhere to be
careful about using endcons, because it makes a copy of the
list, rather than cons which doesn't make a copy. If
possible you should either build the list in the reverse
order or make a final call to reverse. This is certainly
common knowledge to lisp programmers and Maxima developers.

When building a very large list, I find the factor in speed is
orders of magnitude.

I searched 1) The Maxima manual 2) The Maxima Book,
3) the list archives since 2000.

Altogether, there are two references to the issue. I
was clued by this single oblique reference in the book:

 endcons(elem,list) returns an (unshared) list where ...

The second reference is in a post from Jaime Villate 2007.

Thanks,
John
Permalink | Reply |
headers
Stavros Macrakis | 8 Sep 06:01
Favicon

Re: endcons

John,

Maxima's list operations are all non-destructive (except for explicit assignments to list elements, e.g. list[23]: 5).  This means they must copy the whole list in many cases.  The documentation of endcons in the Maxima manual is actually fairly clear on this: "Returns a new list consisting of the elements of list followed by expr. " (http://maxima.sourceforge.net/docs/manual/en/maxima_37.html)  It is unfortunately not so clear in other cases where there might be as much or more doubt, e.g. 'delete' (also non-destructive).

Note that endcons, even if it didn't copy the whole list, would still have to traverse the whole list since Maxima uses singly-linked lists (as does Lisp) so you would still have the n^2 behavior.

           -s

On Sun, Sep 7, 2008 at 11:39 PM, John Lapeyre <john.lapeyre <at> gmail.com> wrote:
I think the Maxima manual should mention somewhere to be
careful about using endcons, because it makes a copy of the
list, rather than cons which doesn't make a copy. If
possible you should either build the list in the reverse
order or make a final call to reverse. This is certainly
common knowledge to lisp programmers and Maxima developers.

_______________________________________________
Maxima mailing list
Maxima <at> math.utexas.edu
http://www.math.utexas.edu/mailman/listinfo/maxima
Permalink | Reply |
headers
John Lapeyre | 8 Sep 06:37

Re: endcons

Stavros,

> Note that endcons, even if it didn't copy the whole list, would still have
> to *traverse* the whole list since Maxima uses singly-linked lists (as does
> Lisp) so you would still have the n^2 behavior.

   Ah, so it must be this list traversal that is responsible for the 
observed slowness.

In the Maxima manual the entry for cons says
 Returns a new list constructed...

and for endcons,

 Returns a new list consisting of ...

which agrees with what you said.

But in the Maxima Book, I read

 list2:cons(element,list1) returns a (new) list2, ...
       list1 and list2 have a common *shared* tail  [emphasize in original]

 endcons(element,list) returns an (unshared) list ...

which apparantley disagrees.

John
Permalink | Reply |

Gmane