Re: how to speed up some lisp code?

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

Date: Thu, 19 Feb 2004 14:47:49 -0800

On Feb 18 2004, Joe Marshall <prunesquallor@comcast.net> wrote:

> John H Palmieri <palmieri@math.washington.edu> writes:
>
>> I'm a mathematician, and I want to do some computations (using lisp,
>> specifically Allegro, since that's what we have installed). In fact,
>> I have written code for doing the things I want, but it's too slow, so
>> now I would like advice on how to speed things up.
>
> Profile the code! This is the quickest and easiest way to find the
> bottlenecks.

Okay, I'll have to read the documentation on the profiler. I'm sure
it's very good and helpful, but I haven't been able to make much of
it yet.

> Using lists for `monomials' and `polynomials' may be quite reasonable
> depending on how much list traversal you are doing.
>
>> The sorts of things I need to do with monomials:
>> - test for equality
>> - test for "admissibility", and correct if it's inadmissible. A
>> monomial (a b c d ... ) is admissible if 2a >= b, 2b >= c, ... If
>> it's not admissible, there is a method for fixing that, which
>> replaces the inadmissible monomial with a polynomial: if 2b < c,
>> then use a formula to turn (b c) into a list of other terms
>> (x1 y1), (x2 y2), ..., and then replace (a b c d ...) with
>> (a x1 y1 d ...), (a x2 y2 d ...), .... (I'm constructing these
>> new monomials with append, which may be slow?
>
> This is likely to be a bottleneck. If you are using append to try to
> `cons on to the right hand side' of a list, it creates an O(n^2) process.
>
>
> It would help if you can post some of the code.

I've now posted some things here:

  http://www.math.washington.edu/~palmieri/Lisp/lambda.lisp
    manipulations with monomials and polynomials
  
  http://www.math.washington.edu/~palmieri/Lisp/matrix.lisp
    manipulations with matrices
    
  http://www.math.washington.edu/~palmieri/Lisp/ext.lisp
    the main functions (ext and bss), which rely on all the other stuff 

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