Re: how to speed up some lisp code?

From: John H Palmieri (palmieri_at_math.washington.edu)
Date: 02/20/04 

Date: Fri, 20 Feb 2004 10:49:06 -0800

On Feb 20 2004, Joe Marshall <jrm@ccs.neu.edu> wrote:

> I've looked at and played with your code. For the BSS function, the
> bulk of the time is spent in reducing the matrix to row-echelon form.
>
> The *main* performance problem seems to be rooted in the naive use of
> list manipulation functions. I don't mean this as a personal slight
> --- I understand that you aren't a professional Lisp hacker.

No, no problem, you're very nice about the whole thing. And thanks
for spending so much time with it.

> The literature on how to effectively use lists is pretty sparse.
>
> The thing to keep in mind when using lists is that the cost accessing
> an element goes up the further away the element is from the head of
> the list. So you want to try to organize your algorithms to avoid
> unnecessary list traversal, and *especially* to make sure that
> functions that process the entire list can be written to process the
> list sequentially from first to last element.
>
> Allow me to critique some individual examples. Again, don't take this
> personally, I'm hoping to improve your code.
>
> From what I can tell, there is no real loss of generality by fixing
> the lex order at <, and it will make things simpler. This function
> orders monomials lexicographically:

[snip]

> I'd write it like this:
>
> (defun lex-less-than (left right)
> (and (not (eq left right)) ; short circuit EQ lists
> (consp right) ; right must be at least as long as left
> (or (not (consp left)) ; either left is shorter
> (< (car left) (car right)) ; the first element is smaller
> (and (= (car left) (car right)) ; the first elements are same
> (lex-less-than (cdr left) (cdr right))))))

I think I made a mistake when coding this; I actually can't think of a
time when I need to compare monomials of different lengths. So I
could probably simplify this more. Anyway: I don't think eq is the
right thing to use: (eq '(1 2 3) '(1 2 3)) is nil, so it probably
won't save any time. Does equal traverse the lists, or is it
efficient enough to use as a replacement here?

> This function modifies a matrix by replacing or inserting a new row:

[snip]

> (defun insert-vector-in-matrix (vec mat n)
> "replace row[N] of MAT with VEC, and return resulting matrix"
> (let ((old-vec (assoc n mat)))
> (if old-vec
> (progn (setf (cdr old-vec) vec)
> mat)
> (acons n vec mat))))

I think because my main experience with lisp is in emacs lisp
hacking, I don't think of using the power of setf enough. Thanks.

> The function inadmissible-p is this:

[snip]

> The solution? First we need a function that can split a list at a
> particular element. I'm assuming that inadmissible monos are fairly
> rare. If they are quite common, then inadmissible-p should extract
> the prefix and suffix at the same time as it searches for the bad
> value.

Actually, inadmissible monomials occur fairly frequently. One of the
main tasks is essentially to start with a monomial MONO and then make
(cons -1 MONO) admissible.

I'll have to think about your suggestions and try out some of them, to
see what happens. Using values to return more than one thing is
something I've used once or twice, but not something that leaps to the
top of my mind when I'm writing code.

[snip]

>>>> The sorts of things I need to do with polynomials:
>>>> - add two polynomials, mod 2. That is, do (set-exclusive-or POLY1 POLY2).
>
> This will be expensive because you will by necessity have to traverse
> each POLY at least once. If the POLYs are in some order, though, you
> can compute the set-xor in order fairly efficiently.
>
>>>> - given a polynomial P, find all monomials in P which end in an odd
>>>> number.
>
> The *end* of the polynomial P is the hardest element to get to! If
> this is important, consider storing the polynomials backwards (least
> significant element first?).

(It's the ends of the monomials, not the ends of polynomials, that
I care about. Still expensive to get to, but since monomials are
relatively short, I hope not as bad as with the longer lists that
polynomials tend to be. I'll think about storing monomials
backwards.)

>>>> - given a polynomial P, find all monomials in P which don't consist
>>>> entirely of odd numbers.
>
> You may wish to create little structures to represent monomials and
> polynomials. It is expensive to traverse the entire polynomial
> looking for the odd monomials, but it should be quite easy to note
> when creating a monomial or polynomial whether there are any even
> elements.
>
> I hope this helps.

I think it will. Thanks very much. 

-- 
J. H. Palmieri
Dept of Mathematics, Box 354350    mailto:palmieri@math.washington.edu
University of Washington           http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350

Relevant Pages

  • how to speed up some lisp code?
    ... I'm using a data type I'll call a "monomial": these are sorted lists ... These could have thousands of monomials ... The sorts of things I need to do with polynomials: ...
    (comp.lang.lisp)
  • Re: how to speed up some lisp code?
    ... polynomials are represented as a defstruct with a field that contains the ... > The integers in the lists are small: ... > The sorts of things I need to do with monomials: ... > The sorts of things I need to do with polynomials: ...
    (comp.lang.lisp)
  • Re: how to speed up some lisp code?
    ... > but the integer representation you mentioned seems suboptimal ... > numbers appearing in your monomials are small then this ... I can use fixnums if I represent monomials as lists of integers, ... The lexicographic order is more important with the matrix ...
    (comp.lang.lisp)
  • Re: how to speed up some lisp code?
    ... bottlenecks. ... Using lists for `monomials' and `polynomials' may be quite reasonable ... If you are using append to try to ...
    (comp.lang.lisp)
  • Re: Number Theory problem: seeking Calculus example
    ... polynomials, and ask whether all of this information ... The list of references in this paper is the most ... mentioned in the following two lists of well known ... it seems that a group of mathematicians ...
    (sci.math)