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. I'll explain what
sort of things I'm working with, and I'm wondering about good ways to
deal with them. I think my main question is, how should I represent
each sort of structure? For each data type, should I use defstruct
or defclass, or just represent it as a list, or an alist, or a hash
table?
(By the way, I know some lisp, mainly from emacs lisp hacking, but I
am almost a beginner. When it comes to writing fast code, I am
certainly a beginner. Please keep this in mind when giving advice:
any suggestion, no matter how simple, might be helpful, because I
might have missed it.)
I'm using a data type I'll call a "monomial": these are sorted lists
of non-negative integers. So far, the lists have length at most 7 or
8, but if I can speed things up, I'll want to go up to 20, or more.
The integers in the lists are small: less then 200. Right now, I'm
representing these as lists. (I played around with representing them
as integers: the list (a b c ...) gets translated into an integer
where a is the left-most bunch of bits, then b is the next bunch, and
so on. I was hoping that since I could use arithmetic operations
instead of list operations, and since I could use = instead of equal
for comparison, it would speed things up, but it didn't. Maybe I
didn't do it well. I don't see any advantage in using bit-vectors,
but I haven't tried, and you could try to persuade me if you feel
differently...)
I'm also using a data type I'll call a "polynomial": these are sets of
monomials. Almost always, I want them to be sorted (by lexicographic,
a.k.a. "dictionary," ordering). These could have thousands of monomials
in them. Right now, I'm using lists for these, as well -- probably a
bad choice, but what should I use instead? (For example, should I use
something which lends itself well to sorting?)
I'm also using a data type I'll call a "matrix": these are alists of
polynomials, where the key is a positive integer, and for large parts
of the computation, I want them sorted by key. They could have
hundreds, or maybe thousands, of terms in them. Right now, I'm using
alists for these (and using (sort matrix #'< :key #'car) somewhat
frequently).
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? I could try to
rewrite using nconc, but it might be annoying.) Then check each of
these new monomials for admissibility, and continue until done.
Because of the nature of the formula, this process does in fact
terminate.
(I haven't told you the formula, but here's an example: (1 2 8) is
inadmissible, and (2 8) equals ((5 5) (4 6)). This turns (1 2 8)
into ((1 5 5) (1 4 6)). (1 5 5) and (1 4 6) are both
inadmissible, but (1 5) equals (3 3), and (3 3 5) is admissible;
also, (1 4) equals (2 3), and (2 3 6) is admissible. So (1 2 8)
equals ((3 3 5) (2 3 6)).)
The sorts of things I need to do with polynomials:
- add two polynomials, mod 2. That is, do (set-exclusive-or POLY1 POLY2).
- given a polynomial P, find all monomials in P which end in an odd
number.
- given a polynomial P, find all monomials in P which don't consist
entirely of odd numbers.
The sorts of things I need to do with matrices:
- add a pair (a.k.a., a "row") (key . poly) to a matrix
- find a row with a given key
- switch rows: that is, given a matrix containing (I . P) and (J . Q),
return a matrix which is equal except it has (I . Q) and (J . P).
- add rows. That is, if a matrix has rows (I . P) and (J . Q),
return a matrix which has rows (I . P) and (J . (add-poly P Q)).
- loop through the rows in increasing order of their key.
--
J. H. Palmieri
Dept of Mathematics, Box 354350 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
"John H Palmieri" <········@math.washington.edu> wrote in message
····················@zeno1.math.washington.edu...
> 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. I'll explain what
> sort of things I'm working with, and I'm wondering about good ways to
> deal with them. I think my main question is, how should I represent
> each sort of structure? For each data type, should I use defstruct
> or defclass, or just represent it as a list, or an alist, or a hash
> table?
A lot of these questions are generic algorithm questions, and not
necessarily at this stage Lisp specific.
You mention that you have a lot of ordered collections.
Are these dynamic collections, or static? Basically, if you're sorting
things over and over again, it may be faster to simply keep your structures
in an ordered data structure, that way they're always sorted.
Also, it's not clear whether you're doing much random, or keyed access to
your data versus simply iterating it.
I'm guessing as a complete swag that switching to more of a generic tree
structure rather than a unsorted list structure may be a hot tip and give
you a noticable performance boost. A tree structure will give you the
ability to iterate through the elements in a sorted order, as well as the
ability to pick elements out efficiently by key if that's necessary. Also,
adding data to the tree can be more efficient that something like append
which needs to scan the entire structure. Plus by reusing the tree
structures in place, you'll probably save consing of memory as well.
It also shouldn't have a draconian effect on your current code structure, so
ideally should drop in pretty painlessly.
There's a Red-Black tree library up on cliki.net
(http://www.cliki.net/Red-Black-trees) you might want to try for inspiration
(I've never used it). This tree algorithm is one of several that has the
advantage of keeping access times of data basically constant once the tree
is populated compared to an unbalanced tree.
I didn't want to go in to the hows and why of tree algorithms et al guessing
that you'd rather have a more black box approach to the problem than the
gritty details.
Regards,
Will Hartung
(·····@msoft.com)
On Feb 18 2004, "Will Hartung" <·····@msoft.com> wrote:
> "John H Palmieri" <········@math.washington.edu> wrote in message
> ····················@zeno1.math.washington.edu...
>> 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. I'll explain what
>> sort of things I'm working with, and I'm wondering about good ways to
>> deal with them. I think my main question is, how should I represent
>> each sort of structure? For each data type, should I use defstruct
>> or defclass, or just represent it as a list, or an alist, or a hash
>> table?
>
> A lot of these questions are generic algorithm questions, and not
> necessarily at this stage Lisp specific.
(Except that I've written lisp code for it.)
> You mention that you have a lot of ordered collections.
>
> Are these dynamic collections, or static? Basically, if you're sorting
> things over and over again, it may be faster to simply keep your structures
> in an ordered data structure, that way they're always sorted.
I agree, I think that it might be faster to have them in an ordered
data structure of some kind.
> Also, it's not clear whether you're doing much random, or keyed access to
> your data versus simply iterating it.
With polynomials, it's pretty much all iterating.
With matrices, some of each, but probably more iterating than random
access. (I'll do something like loop through the list until I find an
entry satisfying some condition, and then I'll want to switch it with
another entry. That is, assuming it's a sorted alist with some entry
(40 POLY1), I may iterate until I find the element (100 POLY2), and I
may then want to return a new sorted alist in which POLY1 and POLY2
have been switched.)
> I'm guessing as a complete swag that switching to more of a generic tree
> structure rather than a unsorted list structure may be a hot tip and give
> you a noticable performance boost. A tree structure will give you the
> ability to iterate through the elements in a sorted order, as well as the
> ability to pick elements out efficiently by key if that's necessary. Also,
> adding data to the tree can be more efficient that something like append
> which needs to scan the entire structure. Plus by reusing the tree
> structures in place, you'll probably save consing of memory as well.
>
> It also shouldn't have a draconian effect on your current code structure, so
> ideally should drop in pretty painlessly.
>
> There's a Red-Black tree library up on cliki.net
> (http://www.cliki.net/Red-Black-trees) you might want to try for inspiration
> (I've never used it). This tree algorithm is one of several that has the
> advantage of keeping access times of data basically constant once the tree
> is populated compared to an unbalanced tree.
>
> I didn't want to go in to the hows and why of tree algorithms et al guessing
> that you'd rather have a more black box approach to the problem than the
> gritty details.
I'll look at it. I may want to know the gritty details, but I can
look into it later, if the basic idea appeals to me.
> Regards,
>
> Will Hartung
> (·····@msoft.com)
--
J. H. Palmieri
Dept of Mathematics, Box 354350 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
"John H Palmieri" <········@math.washington.edu> wrote in message
····················@zeno3.math.washington.edu...
> On Feb 18 2004, "Will Hartung" <·····@msoft.com> wrote:
>
> > A lot of these questions are generic algorithm questions, and not
> > necessarily at this stage Lisp specific.
>
> (Except that I've written lisp code for it.)
My point is that I didn't think the classic declaims and declares typical of
"speeding up" Lisp code was going to actually help you here, that's all,
that the problem was more within the program structure itself.
> > You mention that you have a lot of ordered collections.
> >
> > Are these dynamic collections, or static? Basically, if you're sorting
> > things over and over again, it may be faster to simply keep your
structures
> > in an ordered data structure, that way they're always sorted.
> With matrices, some of each, but probably more iterating than random
> access. (I'll do something like loop through the list until I find an
> entry satisfying some condition, and then I'll want to switch it with
> another entry. That is, assuming it's a sorted alist with some entry
> (40 POLY1), I may iterate until I find the element (100 POLY2), and I
> may then want to return a new sorted alist in which POLY1 and POLY2
> have been switched.)
Do you want a NEW list or can you alter the list in place and reuse it
instead? I'm sure you can see that there's a big difference. Deleting and
inserting elements into a tree are potentially the most expensive operations
on the tree, but for large trees those operations are far cheaper than
copying the tree wholesale. But if you need a full copy, then, well, you
need a full copy.
As you can imagine, these are important details. For example, if you
routinely copy the structure (rather than modify it in place), it may be
cheaper to simply load your data in a linear structure (a list), sort it
(once), and then create a new copy routine that will insert an element into
the new ordered structure while it is copying it (and perhaps deleting the
other element).
> > I didn't want to go in to the hows and why of tree algorithms et al
guessing
> > that you'd rather have a more black box approach to the problem than the
> > gritty details.
>
> I'll look at it. I may want to know the gritty details, but I can
> look into it later, if the basic idea appeals to me.
Any generic modern data structures text will have the RB Tree algorithm in
it (as well as a host of others) and will let you get as nitty and gritty as
you want.
Regards,
Will Hartung
(·····@msoft.com)
In article <···············@zeno1.math.washington.edu>,
John H Palmieri <········@math.washington.edu> wrote:
> I'm using a data type I'll call a "monomial": these are sorted lists
> of non-negative integers. So far, the lists have length at most 7 or
> 8, but if I can speed things up, I'll want to go up to 20, or more.
> The integers in the lists are small: less then 200. Right now, I'm
> representing these as lists. (I played around with representing them
> as integers: the list (a b c ...) gets translated into an integer
> where a is the left-most bunch of bits, then b is the next bunch, and
> so on. I was hoping that since I could use arithmetic operations
> instead of list operations, and since I could use = instead of equal
> for comparison, it would speed things up, but it didn't. Maybe I
> didn't do it well. I don't see any advantage in using bit-vectors,
> but I haven't tried, and you could try to persuade me if you feel
> differently...)
The important thing is declaring the types of your variables. Since all
the integers are small, declare the variables to be FIXNUM. Otherwise,
even arithmetic operations have to be generic, because they might have
to deal with floats, bignums, rationals, or complex numbers.
Make sure you declare all the temporary variables as well. Remember,
even if the arguments to a function are FIXNUM, the result might
overflow, and without declarations to the contrary the implementation
has to handle this. E.g. if A and B are declared to be FIXNUM, it can't
assume that (+ A B) will also be FIXNUM; consider the result of (+
MOST-POSITIVE-FIXNUM 1).
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
On Feb 18 2004, Barry Margolin <······@alum.mit.edu> wrote:
> In article <···············@zeno1.math.washington.edu>,
> John H Palmieri <········@math.washington.edu> wrote:
>
>> I'm using a data type I'll call a "monomial": these are sorted lists
>> of non-negative integers. So far, the lists have length at most 7 or
>> 8, but if I can speed things up, I'll want to go up to 20, or more.
>> The integers in the lists are small: less then 200. Right now, I'm
>> representing these as lists. (I played around with representing them
>> as integers: the list (a b c ...) gets translated into an integer
>> where a is the left-most bunch of bits, then b is the next bunch, and
>> so on. I was hoping that since I could use arithmetic operations
>> instead of list operations, and since I could use = instead of equal
>> for comparison, it would speed things up, but it didn't. Maybe I
>> didn't do it well. I don't see any advantage in using bit-vectors,
>> but I haven't tried, and you could try to persuade me if you feel
>> differently...)
>
> The important thing is declaring the types of your variables. Since all
> the integers are small, declare the variables to be FIXNUM. Otherwise,
> even arithmetic operations have to be generic, because they might have
> to deal with floats, bignums, rationals, or complex numbers.
To: Barry Margolin <······@alum.mit.edu>
Subject: Re: how to speed up some lisp code?
Bcc: ········@math.washington.edu
X-Face: 'mv.B*Lk2HZf}(gQV6`,nM|p,xpL&···@(Y'*f3:)M"g$~24P{a{\Zs<Y>Sy%(Bl([?i"VA
··@odDT:Q0Cw.f,:':PKOZw{bs0v2+)'`ulAVF{w,jDp(@OOZe2Mc5i'^S/^?NKn)`f#NnzHezZ_c7
]{xSxM[NOral_[\^YN)%rM|&······················@·@j<ZDgIije
X-Draft-From: ("comp.lang.lisp" 140551)
References: <···············@zeno1.math.washington.edu>
<····························@comcast.ash.giganews.com>
From: John H Palmieri <········@math.washington.edu>
--text follows this line--
On Feb 18 2004, Barry Margolin <······@alum.mit.edu> wrote:
> In article <···············@zeno1.math.washington.edu>,
> John H Palmieri <········@math.washington.edu> wrote:
>
>> I'm using a data type I'll call a "monomial": these are sorted lists
>> of non-negative integers. So far, the lists have length at most 7 or
>> 8, but if I can speed things up, I'll want to go up to 20, or more.
>> The integers in the lists are small: less then 200. Right now, I'm
>> representing these as lists. (I played around with representing them
>> as integers: the list (a b c ...) gets translated into an integer
>> where a is the left-most bunch of bits, then b is the next bunch, and
>> so on. I was hoping that since I could use arithmetic operations
>> instead of list operations, and since I could use = instead of equal
>> for comparison, it would speed things up, but it didn't. Maybe I
>> didn't do it well. I don't see any advantage in using bit-vectors,
>> but I haven't tried, and you could try to persuade me if you feel
>> differently...)
>
> The important thing is declaring the types of your variables. Since all
> the integers are small, declare the variables to be FIXNUM. Otherwise,
> even arithmetic operations have to be generic, because they might have
> to deal with floats, bignums, rationals, or complex numbers.
I tried that with fixnums, but it didn't seem to help much. That was
a while ago, and I've sped up some other parts of the code, so I'll
try again -- maybe now it will make more of a difference. (I think
I'm doing a lot more list operations than arithmetic, which is why it
wasn't much help.) Does it help to declare something as a list, or a
list of fixnums?
> Make sure you declare all the temporary variables as well. Remember,
> even if the arguments to a function are FIXNUM, the result might
> overflow, and without declarations to the contrary the implementation
> has to handle this. E.g. if A and B are declared to be FIXNUM, it can't
> assume that (+ A B) will also be FIXNUM; consider the result of (+
> MOST-POSITIVE-FIXNUM 1).
I think that the Allegro compiler has a setting which lets me avoid
this. I'm away from the documentation now, but I think if I set
various flags the right way (which I try to do), it assumes that sums
of fixnums are fixnums, etc.
> --
> Barry Margolin, ······@alum.mit.edu
> Arlington, MA
> *** PLEASE post questions in newsgroups, not directly to me ***
--
J. H. Palmieri
Dept of Mathematics, Box 354350 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
I have a package, rsm.mpoly, at the site
http://sourceforge.net/projects/com-lisp-utils
that models multivariate polynomials.One can compute with polynomials with
coefficients over the Reals, Complex, or Z mod n. They can be ordered with
lex or deglex ordering. Operations currently supported are addition,
multiplication, raising a polynomial to an integer power - which will be
fast if it is over Z mod n. There are functions for returning the leading
power, term, and coefficient under the current ordering. Multivariate
polynomials are represented as a defstruct with a field that contains the
non zero coefficients and powers.
Example:
3 x1^2 x2 x3^4 + x1 x2^2 x3
becomes
((3 #(2 1 4)) (1 (1 2 1)))
This is probably not what you need but it might be useful to look at the
code for ideas. Two interesting features used are: a BOA-constructor and the
use of dynamics variables for efficiency.
-R. Scott McIntire
"John H Palmieri" <········@math.washington.edu> wrote in message
····················@zeno1.math.washington.edu...
> 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. I'll explain what
> sort of things I'm working with, and I'm wondering about good ways to
> deal with them. I think my main question is, how should I represent
> each sort of structure? For each data type, should I use defstruct
> or defclass, or just represent it as a list, or an alist, or a hash
> table?
>
> (By the way, I know some lisp, mainly from emacs lisp hacking, but I
> am almost a beginner. When it comes to writing fast code, I am
> certainly a beginner. Please keep this in mind when giving advice:
> any suggestion, no matter how simple, might be helpful, because I
> might have missed it.)
>
> I'm using a data type I'll call a "monomial": these are sorted lists
> of non-negative integers. So far, the lists have length at most 7 or
> 8, but if I can speed things up, I'll want to go up to 20, or more.
> The integers in the lists are small: less then 200. Right now, I'm
> representing these as lists. (I played around with representing them
> as integers: the list (a b c ...) gets translated into an integer
> where a is the left-most bunch of bits, then b is the next bunch, and
> so on. I was hoping that since I could use arithmetic operations
> instead of list operations, and since I could use = instead of equal
> for comparison, it would speed things up, but it didn't. Maybe I
> didn't do it well. I don't see any advantage in using bit-vectors,
> but I haven't tried, and you could try to persuade me if you feel
> differently...)
>
> I'm also using a data type I'll call a "polynomial": these are sets of
> monomials. Almost always, I want them to be sorted (by lexicographic,
> a.k.a. "dictionary," ordering). These could have thousands of monomials
> in them. Right now, I'm using lists for these, as well -- probably a
> bad choice, but what should I use instead? (For example, should I use
> something which lends itself well to sorting?)
>
> I'm also using a data type I'll call a "matrix": these are alists of
> polynomials, where the key is a positive integer, and for large parts
> of the computation, I want them sorted by key. They could have
> hundreds, or maybe thousands, of terms in them. Right now, I'm using
> alists for these (and using (sort matrix #'< :key #'car) somewhat
> frequently).
>
> 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? I could try to
> rewrite using nconc, but it might be annoying.) Then check each of
> these new monomials for admissibility, and continue until done.
> Because of the nature of the formula, this process does in fact
> terminate.
>
> (I haven't told you the formula, but here's an example: (1 2 8) is
> inadmissible, and (2 8) equals ((5 5) (4 6)). This turns (1 2 8)
> into ((1 5 5) (1 4 6)). (1 5 5) and (1 4 6) are both
> inadmissible, but (1 5) equals (3 3), and (3 3 5) is admissible;
> also, (1 4) equals (2 3), and (2 3 6) is admissible. So (1 2 8)
> equals ((3 3 5) (2 3 6)).)
>
> The sorts of things I need to do with polynomials:
> - add two polynomials, mod 2. That is, do (set-exclusive-or POLY1
POLY2).
> - given a polynomial P, find all monomials in P which end in an odd
> number.
> - given a polynomial P, find all monomials in P which don't consist
> entirely of odd numbers.
>
> The sorts of things I need to do with matrices:
> - add a pair (a.k.a., a "row") (key . poly) to a matrix
> - find a row with a given key
> - switch rows: that is, given a matrix containing (I . P) and (J . Q),
> return a matrix which is equal except it has (I . Q) and (J . P).
> - add rows. That is, if a matrix has rows (I . P) and (J . Q),
> return a matrix which has rows (I . P) and (J . (add-poly P Q)).
> - loop through the rows in increasing order of their key.
>
> --
> J. H. Palmieri
> Dept of Mathematics, Box 354350 ···············@math.washington.edu
> University of Washington
http://www.math.washington.edu/~palmieri/
> Seattle, WA 98195-4350
On Feb 18 2004, "R. Scott McIntire" <····················@comcast.net> wrote:
> I have a package, rsm.mpoly, at the site
> http://sourceforge.net/projects/com-lisp-utils
> that models multivariate polynomials.One can compute with polynomials with
> coefficients over the Reals, Complex, or Z mod n. They can be ordered with
> lex or deglex ordering. Operations currently supported are addition,
> multiplication, raising a polynomial to an integer power - which will be
> fast if it is over Z mod n. There are functions for returning the leading
> power, term, and coefficient under the current ordering. Multivariate
> polynomials are represented as a defstruct with a field that contains the
> non zero coefficients and powers.
>
> Example:
>
> 3 x1^2 x2 x3^4 + x1 x2^2 x3
>
> becomes
> ((3 #(2 1 4)) (1 (1 2 1)))
>
> This is probably not what you need but it might be useful to look at the
> code for ideas. Two interesting features used are: a BOA-constructor and the
> use of dynamics variables for efficiency.
>
> -R. Scott McIntire
I'll take a look at it to see if it has helpful ideas for me; thanks.
--
J. H. Palmieri
Dept of Mathematics, Box 354350 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
From: Joe Marshall
Subject: Re: how to speed up some lisp code?
Date:
Message-ID: <k72kkl25.fsf@comcast.net>
John H 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.
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.
--
~jrm
Joe Marshall wrote:
> Profile the code! This is the quickest and easiest way to find the
> bottlenecks.
DISASSEMBLE is also useful, for example for finding arithmetic
operations that remain generic. Some implementations also provide
ways for the compiler to offer advice.
Paul
On Feb 18 2004, Joe Marshall <·············@comcast.net> wrote:
> John H 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 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
John H Palmieri wrote:
> 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.
Have you considered using Macsyma?
--
Jens Axel S�gaard
There is nothing in Macsyma to do these operations.
Although you call them polynomials, the polynomials
in Macsyma are not the same.
.....
After profiling, you should have an idea where the
most time is being used. The bottlenecks should be
considered carefully...
Are you compiling for highest speed, least checking?
My guess is that you should not be using alists which
are of length in the thousands, for
anything, but sorting, probably in vectors.
unsorted collections, if you can use them instead,
can be stored very neatly in hashtables.
Good luck.
Jens Axel S�gaard wrote:
> John H Palmieri wrote:
>
>> 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.
>
>
> Have you considered using Macsyma?
>
On Feb 19 2004, Richard Fateman <········@sbcglobal.net> wrote:
> There is nothing in Macsyma to do these operations.
> Although you call them polynomials, the polynomials
> in Macsyma are not the same.
> .....
>
> After profiling, you should have an idea where the
> most time is being used. The bottlenecks should be
> considered carefully...
I'll look into profiling the code.
> Are you compiling for highest speed, least checking?
Yes.
> My guess is that you should not be using alists which
> are of length in the thousands, for
> anything, but sorting, probably in vectors.
>
> unsorted collections, if you can use them instead,
> can be stored very neatly in hashtables.
I'll think about whether I can get away with this. My initial
response is that I probably do need things to be sorted.
> Good luck.
--
J. H. Palmieri
Dept of Mathematics, Box 354350 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
From: Rahul Jain
Subject: Re: how to speed up some lisp code?
Date:
Message-ID: <87smh4cpcl.fsf@nyct.net>
Richard Fateman <········@sbcglobal.net> writes:
> There is nothing in Macsyma to do these operations.
> Although you call them polynomials, the polynomials
> in Macsyma are not the same.
What about weyl in simlab? It seems to allow one to define custom
domains for custom operators, providing a framework for getting the
basic features of mathematical systems in place.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Jeff Sandys
Subject: Re: how to speed up some lisp code?
Date:
Message-ID: <4034EF5F.4F94010@juno.com>
Macsyma is no longer available.
I would upgrade my Macsyma Lite
if they were still in business.
Thanks,
Jeff Sandys
Jens Axel S�gaard wrote:
...
>
> Have you considered using Macsyma?
>
> --
> Jens Axel S�gaard
From: Christopher C. Stacy
Subject: Re: how to speed up some lisp code?
Date:
Message-ID: <u8yiy4v64.fsf@news.dtpq.com>
>>>>> On Thu, 19 Feb 2004 17:16:15 GMT, Jeff Sandys ("Jeff") writes:
Jeff> Macsyma is no longer available.
Jeff> I would upgrade my Macsyma Lite
Jeff> if they were still in business.
Jeff> Thanks,
Jeff> Jeff Sandys
Call them at 703-455-0430 and order the upgrade.
John Palmieri wrote:
> I'm using a data type I'll call a "monomial": these are sorted lists
> of non-negative integers.
The Lisp type system can express "array of elements of such-and-such
a type" but not "list of elements of such-and-such a type". You may
find that switching to arrays and declaring them as arrays of fixnum
is helpful.
You mentioned representing them as integers or bit-vectors,
but the integer representation you mentioned seems suboptimal
to me. How about using a bit-vector, or an integer, which has
bit N set iff N is in the list you're currently using? Doing
that with integers, you get colexicographic ordering for free,
so perhaps you should actually use bit M-N to represent the
number N, where M is an upper bound on the values of N you'll
use. Then the usual ordering on integers is the same as lexicographic
ordering on monomials. The downside is that if most of the
numbers appearing in your monomials are small then this
reversal turns small integers into large ones :-).
> I'm also using a data type I'll call a "polynomial": these are sets of
> monomials. Almost always, I want them to be sorted (by lexicographic,
> a.k.a. "dictionary," ordering). These could have thousands of monomials
> in them. Right now, I'm using lists for these, as well -- probably a
> bad choice, but what should I use instead? (For example, should I use
> something which lends itself well to sorting?)
The things you mention doing with polynomials don't seem to
depend on having their constituents in lexicographic order,
so how about representing a polynomial as a hash-table whose
keys are the monomials in it and whose values are all (say) T?
> I'm also using a data type I'll call a "matrix": these are alists of
> polynomials, where the key is a positive integer, and for large parts
> of the computation, I want them sorted by key. They could have
> hundreds, or maybe thousands, of terms in them. Right now, I'm using
> alists for these (and using (sort matrix #'< :key #'car) somewhat
> frequently).
Probably not the best choice of data structure. How big are the
keys? For instance, could you use an array with the key as index?
Some kind of tree structure might work well, but then you'd have
to implement it yourself rather than letting the nice folks who
made your Lisp implementation do it :-).
> 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? I could try to
> rewrite using nconc, but it might be annoying.) Then check each of
> these new monomials for admissibility, and continue until done.
> Because of the nature of the formula, this process does in fact
> terminate.
Hmm. I'm not sure what you mean by constructing them with APPEND
or with NCONC, but provided you're sharing the tails in the obvious
way you're probably OK here.
I conjecture, with no evidence, that you often get the same
monomial appearing for admissibility testing and correction.
If so, then you might want to consider memoizing the operation:
(defvar *admissibility-hash* (make-hash-table :test #'equal))
(defun ensure-admissible (monomial)
(or (gethash monomial *admissibility-hash*)
(setf (gethash monomial *admissibility-hash*)
... actual calculation goes here ...)))
If you adopt my suggestion of using integers to represent
monomials, this all becomes a bit more painful. Here's how
to make it less so. I'm going to assume for simplicity that
you can cope with colexicographic ordering, so that bit N
represents the number N. So, do something like this:
- A monomial is inadmissible iff, for some i, bit i is set
and bits (i,2i] are clear and some bit in (2i,oo) is set.
You can check this with one LOGBITP and two LOGANDs.
- Having found that the above condition holds, you can
find the next 1-bit after bit i by looping or by the
x&-x trick. (The x&-x trick doesn't work if you reverse
the monomials to get lexicographic order.) Say it's bit j.
- Then look up i,j in a table to find a list of x,y.
But actually that should be a list of numbers each of
which has bits i,j,x,y set.
- Build the new monomials by exclusive-or-ing the
original monomial with the numbers from your table.
You can still memoize if it helps.
> The sorts of things I need to do with polynomials:
> - add two polynomials, mod 2. That is, do (set-exclusive-or POLY1 POLY2).
> - given a polynomial P, find all monomials in P which end in an odd
> number.
> - given a polynomial P, find all monomials in P which don't consist
> entirely of odd numbers.
I remark that those last two conditions on monomials are easy
to check when the monomials are represented as numbers. "Don't
consist entirely of odd numbers" is (not (zerop (logand m even-mask)))
where EVEN-MASK has all bits corresponding to even numbers set.
"End in an odd number" is (< (logand m even-mask) (logand m odd-mask))
with the odd definition of ODD-MASK. This is another one that gets
a bit fiddlier if you really require lexicographic rather than colex
ordering :-), but it's not too bad even then.
--
Gareth McCaughan
.sig under construc
On Feb 19 2004, Gareth McCaughan <················@pobox.com> wrote:
> John Palmieri wrote:
>
>> I'm using a data type I'll call a "monomial": these are sorted lists
>> of non-negative integers.
>
> The Lisp type system can express "array of elements of such-and-such
> a type" but not "list of elements of such-and-such a type". You may
> find that switching to arrays and declaring them as arrays of fixnum
> is helpful.
Interesting idea. I'll think about it.
> You mentioned representing them as integers or bit-vectors,
> but the integer representation you mentioned seems suboptimal
> to me. How about using a bit-vector, or an integer, which has
> bit N set iff N is in the list you're currently using?
With "monomials", the order is important, so the list (1 2 4) is
different from (4 1 2). I also want to allow repetitions: (1 1 1 1)
is a perfectly good list for me. Unless I'm misunderstanding you, I
can't do this with your idea. That's why I was using that particular
integer representation.
> Doing
> that with integers, you get colexicographic ordering for free,
> so perhaps you should actually use bit M-N to represent the
> number N, where M is an upper bound on the values of N you'll
> use. Then the usual ordering on integers is the same as lexicographic
> ordering on monomials. The downside is that if most of the
> numbers appearing in your monomials are small then this
> reversal turns small integers into large ones :-).
That may have been one of the problems with my representation, too --
I can use fixnums if I represent monomials as lists of integers, but
when I turned them into integers, they would have 30 or more bits,
which is not a fixnum here.
>> I'm also using a data type I'll call a "polynomial": these are sets of
>> monomials. Almost always, I want them to be sorted (by lexicographic,
>> a.k.a. "dictionary," ordering). These could have thousands of monomials
>> in them. Right now, I'm using lists for these, as well -- probably a
>> bad choice, but what should I use instead? (For example, should I use
>> something which lends itself well to sorting?)
>
> The things you mention doing with polynomials don't seem to
> depend on having their constituents in lexicographic order,
> so how about representing a polynomial as a hash-table whose
> keys are the monomials in it and whose values are all (say) T?
The lexicographic order is more important with the matrix
manipulations; I need to be able to look at all rows of the matrix
with key bigger than some number, and see which of those polynomials
has the smallest first term.
>> I'm also using a data type I'll call a "matrix": these are alists of
>> polynomials, where the key is a positive integer, and for large parts
>> of the computation, I want them sorted by key. They could have
>> hundreds, or maybe thousands, of terms in them. Right now, I'm using
>> alists for these (and using (sort matrix #'< :key #'car) somewhat
>> frequently).
>
> Probably not the best choice of data structure. How big are the
> keys? For instance, could you use an array with the key as index?
> Some kind of tree structure might work well, but then you'd have
> to implement it yourself rather than letting the nice folks who
> made your Lisp implementation do it :-).
The keys are positive integers from 1 to 2000, roughly.
>> 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? I could try to
>> rewrite using nconc, but it might be annoying.) Then check each of
>> these new monomials for admissibility, and continue until done.
>> Because of the nature of the formula, this process does in fact
>> terminate.
>
> Hmm. I'm not sure what you mean by constructing them with APPEND
> or with NCONC, but provided you're sharing the tails in the obvious
> way you're probably OK here.
I mean that I call a function with arguments b and c, and it returns
the list LIST=((x1 y1) (x2 y2) ...). Then I loop on LIST, collecting
terms of the form
(append (head of original list) (element of LIST) (tail of original list))
> I conjecture, with no evidence, that you often get the same
> monomial appearing for admissibility testing and correction.
> If so, then you might want to consider memoizing the operation:
>
> (defvar *admissibility-hash* (make-hash-table :test #'equal))
> (defun ensure-admissible (monomial)
> (or (gethash monomial *admissibility-hash*)
> (setf (gethash monomial *admissibility-hash*)
> ... actual calculation goes here ...)))
I've actually already done this, and it helps a little bit, but not a
huge amount. Actually, I've done it slightly differently:
(defvar *admissibility-hash* (make-hash-table :test #'eql))
(defun convert-mono-to-symbol (mono)
"convert MONO to a symbol (for lookup in *relations*)"
(intern (write-to-string mono)))
Then I use
(gethash (convert-mono-to-symbol mono) *admissibility-hash*)
I can certainly switch to using #'equal instead of #'eql for the hash
table and see if it makes any difference.
> If you adopt my suggestion of using integers to represent
> monomials, this all becomes a bit more painful. Here's how
> to make it less so. I'm going to assume for simplicity that
> you can cope with colexicographic ordering, so that bit N
> represents the number N. So, do something like this:
> - A monomial is inadmissible iff, for some i, bit i is set
> and bits (i,2i] are clear and some bit in (2i,oo) is set.
> You can check this with one LOGBITP and two LOGANDs.
> - Having found that the above condition holds, you can
> find the next 1-bit after bit i by looping or by the
> x&-x trick. (The x&-x trick doesn't work if you reverse
> the monomials to get lexicographic order.) Say it's bit j.
> - Then look up i,j in a table to find a list of x,y.
> But actually that should be a list of numbers each of
> which has bits i,j,x,y set.
> - Build the new monomials by exclusive-or-ing the
> original monomial with the numbers from your table.
> You can still memoize if it helps.
I don't know what "memoize" means.
>> The sorts of things I need to do with polynomials:
>> - add two polynomials, mod 2. That is, do (set-exclusive-or POLY1 POLY2).
>> - given a polynomial P, find all monomials in P which end in an odd
>> number.
>> - given a polynomial P, find all monomials in P which don't consist
>> entirely of odd numbers.
>
> I remark that those last two conditions on monomials are easy
> to check when the monomials are represented as numbers. "Don't
> consist entirely of odd numbers" is (not (zerop (logand m even-mask)))
> where EVEN-MASK has all bits corresponding to even numbers set.
> "End in an odd number" is (< (logand m even-mask) (logand m odd-mask))
> with the odd definition of ODD-MASK. This is another one that gets
> a bit fiddlier if you really require lexicographic rather than colex
> ordering :-), but it's not too bad even then.
(As I said earlier, I don't think your suggested encoding of
monomials works for me, but maybe I misunderstood. Correct me if I'm
wrong.)
--
J. H. Palmieri
Dept of Mathematics, Box 354350 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
On Feb 19 2004, John H Palmieri <········@math.washington.edu> wrote:
> On Feb 19 2004, Gareth McCaughan <················@pobox.com> wrote:
[snip]
>> I conjecture, with no evidence, that you often get the same
>> monomial appearing for admissibility testing and correction.
>> If so, then you might want to consider memoizing the operation:
>>
>> (defvar *admissibility-hash* (make-hash-table :test #'equal))
>> (defun ensure-admissible (monomial)
>> (or (gethash monomial *admissibility-hash*)
>> (setf (gethash monomial *admissibility-hash*)
>> ... actual calculation goes here ...)))
>
> I've actually already done this, and it helps a little bit, but not a
> huge amount. Actually, I've done it slightly differently:
>
> (defvar *admissibility-hash* (make-hash-table :test #'eql))
>
> (defun convert-mono-to-symbol (mono)
> "convert MONO to a symbol (for lookup in *relations*)"
> (intern (write-to-string mono)))
>
> Then I use
>
> (gethash (convert-mono-to-symbol mono) *admissibility-hash*)
>
> I can certainly switch to using #'equal instead of #'eql for the hash
> table and see if it makes any difference.
In case anyone is interested: I just tried using #'equal instead of
#'eql (and omitting convert-mono-to-symbol), and #'equal was much
slower -- slower even than without using the hash table at all.
--
J. H. Palmieri
Dept of Mathematics, Box 354350 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
From: Joe Marshall
Subject: Re: how to speed up some lisp code?
Date:
Message-ID: <1xopmrqy.fsf@ccs.neu.edu>
John H Palmieri <········@math.washington.edu> writes:
>
> In case anyone is interested: I just tried using #'equal instead of
> #'eql (and omitting convert-mono-to-symbol), and #'equal was much
> slower -- slower even than without using the hash table at all.
Which lisp? I tried it with lispworks and got better performance with
the equal hash table than with stringifying and interning.
On Feb 20 2004, Joe Marshall <···@ccs.neu.edu> wrote:
> John H Palmieri <········@math.washington.edu> writes:
>
>>
>> In case anyone is interested: I just tried using #'equal instead of
>> #'eql (and omitting convert-mono-to-symbol), and #'equal was much
>> slower -- slower even than without using the hash table at all.
>
> Which lisp? I tried it with lispworks and got better performance with
> the equal hash table than with stringifying and interning.
This is with allegro. Actually, something else must have been going
on earlier; right now I'm getting better performance with the #'equal
hash table than with nothing at all, and similar performances with
#'equal vs. #'eql. The #'equal table seems to be better by less than
one percent:
(time (bss 4 4 4 40)) gives me
with #'eql:
; real time 101,060 msec (00:01:41.060)
with #'equal:
; real time 100,784 msec (00:01:40.784)
--
J. H. Palmieri
Dept of Mathematics, Box 354350 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
John H Palmieri <········@math.washington.edu> writes:
[...]
> This is with allegro. Actually, something else must have been going
> on earlier; right now I'm getting better performance with the #'equal
> hash table than with nothing at all, and similar performances with
> #'equal vs. #'eql. The #'equal table seems to be better by less than
> one percent:
>
> (time (bss 4 4 4 40)) gives me
>
> with #'eql:
> ; real time 101,060 msec (00:01:41.060)
>
> with #'equal:
> ; real time 100,784 msec (00:01:40.784)
I suspect the hypothesis was that some of the time, you'd end up
comparing monomials which actually were eq. (Much as it apparently
turns out to be important to optimize multiplying by 1 and
things---programs end up doing that a lot.)
Anyway, have you considered using vectors rather than lists? That
feels like it ought to be better to me: you'll end up consing less,
and some lisp implementations claim to have very good performance with
typed vectors.
Bruce Stephens <············@cenderis.demon.co.uk> writes:
> Anyway, have you considered using vectors rather than lists?
The big improvement would seem to come from replacing the matrix
implementation. About half the runtime is taken up in sort-vector.
The next largest chunk comes from row-reduce.
There's lots and lots of consing, but that doesn't seem to be the
immediate problem. The fact that these lists are tossed around,
recreated, and sorted all the time is probably the biggest potential
gain. But it would be a bit of work factoring things out so it could
be replaced.
--
Alan Shutko <···@acm.org> - I am the rocks.
We grow because we struggle, learn and overcome.
From: Joe Marshall
Subject: Re: how to speed up some lisp code?
Date:
Message-ID: <ad3dn03n.fsf@ccs.neu.edu>
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. 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:
(defun lex-less-than (mono1 mono2)
(let ((answer t)
(not-done t))
(loop for x in mono1
for y in mono2
if not-done do
(unless (= x y)
(setf answer (< x y)
not-done nil)))
(if not-done ;; reached end of at least one list with all elements equal
(< (length mono1) (length mono2))
answer)))
The first rule, avoid unnecessary list traversal, fails if you call
lex-less-than on the same (eq) list: you walk the entire list just to
find that the elements are all the same.
You are processing the list sequentially up to the point that both
lists have elements, but if one runs out, you compare the length of
each. LENGTH is a *very* expensive function to use on lists: it
traverses the entire list. You really don't care *how much* longer
one is than the other, so there is no point in traversing the whole
list to find out. Also, there is no point from starting at the
beginning of each list because you have already traversed down to the
different point.
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))))))
This function modifies a matrix by replacing or inserting a new row:
(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))
(temp mat)) ;; was (temp (copy-alist mat)))
(if old-vec
(setf temp (delete old-vec temp :test #'equal)))
(acons n vec temp)))
The ASSOC traverses the list up to the index N, but once the row is
found, you use DELETE to remove it. This again traverses the list
looking for the row to delete, *but you already know which one it is*!
Now if you can guarantee that there are no duplicate rows, it is a
simple matter of replacing the contents of the row you found:
(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))))
if there are duplicate rows, you can use the built-in functions to
remove them in one traversal:
(defun insert-vector-in-matrix (vec mat n)
"replace row[N] of MAT with VEC, and return resulting matrix"
(acons n vec
(delete n mat :key #'car)))
The function inadmissible-p is this:
(defun inadmissible-p (mono)
"nil if MONO is admissible, otherwise index where first inadmissible."
(if (null mono)
nil
(let (inadmissible)
(loop for tail on mono
count tail into counter
unless inadmissible
unless (< (length tail) 2) do
(unless (>= (* 2 (car tail)) (cadr tail))
(setf inadmissible (1- counter))))
inadmissible)))
We traverse the list looking for a bad mono. The last element of the
list cannot be bad by definition, so we only go to the penultimate
element. But we do that by measuring the length of the remaining list
in each iteration. In other words, we traverse the entire list on
each iteration just to find out if there is one more element.
(defun inadmissible-p (mono)
(do ((i 0 (1+ i))
(tail mono (cdr tail))
(next (cdr mono) (cdr next)))
((null tail) nil)
(unless (>= (* 2 (car tail)) (car next))
(return-from inadmissible-p
(values i (car tail) (car next))))))
In make-mono-admissible, there is this subform:
(mapcar
(lambda (x)
(append (butlast mono (- (length mono) bad))
x
(last mono (- (length mono) bad 2)))))
(adem (nth bad mono)
(nth (1+ bad) mono)))
This is innocent enough looking, but let us suppose that the bad
element is the 5th element of a 10-element mono....
Remember that we found the bad element via inadmissible-p, so we have
traversed the list entire 5 times. Now we need to call ADEM on that
element and the next. We traverse the list once again to find element
N, and yet again to find element N+1, but we were just in that region
of the list. The mod to inadmissible-p above returns the necessary
elements as extra values.
ADEM returns some list, and we mapcar over that list. Let us assume
that ADEM returns a three-element list. Now for each element, we
substitute that element in the bad spot. To find the prefix, we do
this: (butlast mono (- (length mono) bad))
We traverse the entire list to find its length (again), subtract out
the bad index, then use BUTLAST to compute the prefix. But in order
for BUTLAST to work, it has to traverse the entire list (yet again) to
find the end and copy the elements that it returns (because the list
will be shorter).
To find the suffix, we call this: (last mono (- (length mono) bad 2))
We traverse the entire list (again) to find its length (which we
already computed). We use LAST to compute the suffix, but LAST has to
traverse the entire list to find the end. Fortunately it doesn't copy
the elements...
But now we have to append the prefix, x, and the suffix. APPEND
copies every one of its arguments but the last one, so we once again
traverse the prefix.
And we do this for each of the elements returned by ADEM.
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.
(defun split-list (n list)
(do ((count 0 (1+ count))
(tail list (cdr tail))
(rev-head '() (cons (car tail) rev-head)))
((= count n) (values rev-head (cdr tail)))))
Note that I am accumulating the prefix in reverse order. This is
important. Also note that although I must traverse down to the nth
element, I don't need to traverse further.
(multiple-value-bind (bad-index bad-value next-value) (inadmissible-p mono)
(when bad-index
(multiple-value-bind (rev-prefix suffix) (split-list bad-index mono)
(mapcar (lambda (x)
(revappend rev-prefix (append x suffix)))
(adem bad-value next-value)))))
So I traverse the head of the list to determine if it is admissible or
not, and if so, I get the bad value and the next value in the same
operation. Then I traverse the head of the list to accumulate a
prefix and find the suffix. Once ADEM computes a value for me, I
paste it in place via REVAPPEND. Now REVAPPEND copies its arguments
just as APPEND does, but it reverses them as it goes (esoteric, but it
is more efficient to work in this manner).
In this example, the original code traverses the entire list sixteen
times, but the rewritten code traverses only the prefix and as few
times as possible.
>>> 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?).
>>> - 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.
On Feb 20 2004, Joe Marshall <···@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 ···············@math.washington.edu
University of Washington http://www.math.washington.edu/~palmieri/
Seattle, WA 98195-4350
From: Joe Marshall
Subject: Re: how to speed up some lisp code?
Date:
Message-ID: <65e1mrs7.fsf@ccs.neu.edu>
John H Palmieri <········@math.washington.edu> writes:
>> (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.
(eq '(1 2 3) '(1 2 3)) may be nil, but you use this function in many
places, not just for user input.
> Does equal traverse the lists, or is it efficient enough to use as a
> replacement here?
EQUAL will traverse the entire list, you definitely don't want that
here.
John Palmieri wrote:
[I said:]
> > You mentioned representing them as integers or bit-vectors,
> > but the integer representation you mentioned seems suboptimal
> > to me. How about using a bit-vector, or an integer, which has
> > bit N set iff N is in the list you're currently using?
>
> With "monomials", the order is important, so the list (1 2 4) is
> different from (4 1 2). I also want to allow repetitions: (1 1 1 1)
> is a perfectly good list for me. Unless I'm misunderstanding you, I
> can't do this with your idea. That's why I was using that particular
> integer representation.
Oh, OK; I misunderstood.
> The lexicographic order is more important with the matrix
> manipulations; I need to be able to look at all rows of the matrix
> with key bigger than some number, and see which of those polynomials
> has the smallest first term.
Right.
> > Probably not the best choice of data structure. How big are the
> > keys? For instance, could you use an array with the key as index?
> > Some kind of tree structure might work well, but then you'd have
> > to implement it yourself rather than letting the nice folks who
> > made your Lisp implementation do it :-).
>
> The keys are positive integers from 1 to 2000, roughly.
Hmm. How sparsely populated are your matrices? That is,
what fraction of the possible keys are actually used in
general? If the answer is, say, "at least half", then
an array representation will probably be pretty good.
> > Hmm. I'm not sure what you mean by constructing them with APPEND
> > or with NCONC, but provided you're sharing the tails in the obvious
> > way you're probably OK here.
>
> I mean that I call a function with arguments b and c, and it returns
> the list LIST=((x1 y1) (x2 y2) ...). Then I loop on LIST, collecting
> terms of the form
>
> (append (head of original list) (element of LIST) (tail of original list))
Oh, I see. NCONC would certainly be better than APPEND
for this, provided those pairs are freshly allocated
and therefore safe to mutate.
> > I conjecture, with no evidence, that you often get the same
> > monomial appearing for admissibility testing and correction.
> > If so, then you might want to consider memoizing the operation:
> >
> > (defvar *admissibility-hash* (make-hash-table :test #'equal))
> > (defun ensure-admissible (monomial)
> > (or (gethash monomial *admissibility-hash*)
> > (setf (gethash monomial *admissibility-hash*)
> > ... actual calculation goes here ...)))
>
> I've actually already done this, and it helps a little bit, but not a
> huge amount. Actually, I've done it slightly differently:
>
> (defvar *admissibility-hash* (make-hash-table :test #'eql))
>
> (defun convert-mono-to-symbol (mono)
> "convert MONO to a symbol (for lookup in *relations*)"
> (intern (write-to-string mono)))
>
> Then I use
>
> (gethash (convert-mono-to-symbol mono) *admissibility-hash*)
>
> I can certainly switch to using #'equal instead of #'eql for the hash
> table and see if it makes any difference.
That would let you avoid all the conversions -- but whether
it's worth doing so is a question for the profiler to answer :-).
> > If you adopt my suggestion of using integers to represent
> > monomials, this all becomes a bit more painful.
...
> > You can still memoize if it helps.
>
> I don't know what "memoize" means.
The hash-table thing we already discussed. Anyway, none of this
is relevant because you can't represent monomials as integers in
the way I was proposing.
> > I remark that those last two conditions on monomials are easy
> > to check when the monomials are represented as numbers. "Don't
> > consist entirely of odd numbers" is (not (zerop (logand m even-mask)))
> > where EVEN-MASK has all bits corresponding to even numbers set.
> > "End in an odd number" is (< (logand m even-mask) (logand m odd-mask))
> > with the odd definition of ODD-MASK. This is another one that gets
> > a bit fiddlier if you really require lexicographic rather than colex
> > ordering :-), but it's not too bad even then.
>
> (As I said earlier, I don't think your suggested encoding of
> monomials works for me, but maybe I misunderstood. Correct me if I'm
> wrong.)
Nope, I'm wrong.
--
Gareth McCaughan
.sig under construc
John H Palmieri <········@math.washington.edu> wrote in message news:<···············@zeno1.math.washington.edu>...
> 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. I'll explain what
> sort of things I'm working with, and I'm wondering about good ways to
> deal with them. I think my main question is, how should I represent
> each sort of structure? For each data type, should I use defstruct
> or defclass, or just represent it as a list, or an alist, or a hash
> table?
>
I think the only important thing to do is to profile your code. Don't
waste time declaring types or fiddling with algorithms or
representations until you *know what is slow*. It may be that you
already know what is slow, but I'd guess you don't or you wouldn't be
asking here, you'd be fixing it (:-). In general, it is very
difficult for human beings to predict what it slow in programs of any
significant size, so you really must be empirical about it and measure
what takes the time, then fix that. It's important to iterate this
process - profile, fix, profile, fix &c, becasue each fix will alter
the profiling, possibly in surprising ways. Finally make sure you
profile on realistic data.
Allegro has a very good profiler I think.
--tim
On 19 Feb 2004 07:34:06 -0800, ··········@tfeb.org (Tim Bradshaw)
wrote:
>
>I think the only important thing to do is to profile your code.
I agree. It is a critical step. The only caveat is that profiling
isn't going to tell you have an O(n**2) algorithm which you can
reduce to O(n log(n)). You have to think about what you are doing.
>
>Allegro has a very good profiler I think.
Yes, easy to use, easy to interpret the results.
James P. Massar <······@alum.mit.edu> wrote in message news:<··································@4ax.com>...
> On 19 Feb 2004 07:34:06 -0800, ··········@tfeb.org (Tim Bradshaw)
> wrote:
>
> >
> >I think the only important thing to do is to profile your code.
>
> I agree. It is a critical step. The only caveat is that profiling
> isn't going to tell you have an O(n**2) algorithm which you can
> reduce to O(n log(n)). You have to think about what you are doing.
I agree: I didn't mean to imply that profiling solved all problems!
What it will do though (and this has happened suprisingly often to me)
is to tell me that my O(n^2) algorithm was so far off the critical
path that time spent converting it to an O(n log n) one was entirely
wasted. I've often found this with things like alists used for
associative arrays: I spent a bunch of time stressing about them, only
to discover that (a) they weren't actually being used that often and
(b) the mean length was 2 or something, and searching a 2 elt list is
actually quite fast.
--tim
From: Joe Marshall
Subject: Re: how to speed up some lisp code?
Date:
Message-ID: <4qtlon7z.fsf@ccs.neu.edu>
··········@tfeb.org (Tim Bradshaw) writes:
> James P. Massar <······@alum.mit.edu> wrote in message news:<··································@4ax.com>...
>> On 19 Feb 2004 07:34:06 -0800, ··········@tfeb.org (Tim Bradshaw)
>> wrote:
>>
>> >
>> >I think the only important thing to do is to profile your code.
>>
>> I agree. It is a critical step. The only caveat is that profiling
>> isn't going to tell you have an O(n**2) algorithm which you can
>> reduce to O(n log(n)). You have to think about what you are doing.
It can help pinpoint those O(n^2) algorithms, though. If you run a
profile on some small data structure and find that there are more than
10^8 calls to FOO when you were expecting something like 10^4, it is a
good indication that something is *really* wrong.
> I agree: I didn't mean to imply that profiling solved all problems!
> What it will do though (and this has happened suprisingly often to me)
> is to tell me that my O(n^2) algorithm was so far off the critical
> path that time spent converting it to an O(n log n) one was entirely
> wasted. I've often found this with things like alists used for
> associative arrays: I spent a bunch of time stressing about them, only
> to discover that (a) they weren't actually being used that often and
> (b) the mean length was 2 or something, and searching a 2 elt list is
> actually quite fast.
Profiling can optimize programmer time as well.