Re: how to speed up some lisp code?

From: Will Hartung (willh_at_msoft.com)
Date: 02/19/04 

Date: Wed, 18 Feb 2004 15:53:08 -0800

"John H Palmieri" <palmieri@math.washington.edu> wrote in message
news:s5twu6k12gw.fsf@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
(willh@msoft.com)

Relevant Pages

  • Re: how to speed up some lisp code?
    ... >> A lot of these questions are generic algorithm questions, ... >> necessarily at this stage Lisp specific. ... inserting elements into a tree are potentially the most expensive operations ... I may want to know the gritty details, ...
    (comp.lang.lisp)
  • Re: When is Xah going to ease up on Emacs...
    ... One part of the cons problem in lisp is that it forces programer to ... extracts the leafs of a tree. ... has abstracted low-level access to lists with functions, e.g. get-children, ...
    (comp.lang.lisp)
  • Re: List destruction?
    ... I loose the first cons cell and ... thus I loose the identity of the list. ... tree represented by a list. ... Doesn't this reveal somehow 'a weak point' of Lisp? ...
    (comp.lang.lisp)
  • Re: how to speed up some lisp code?
    ... >> I'm a mathematician, and I want to do some computations (using lisp, ... > necessarily at this stage Lisp specific. ... it's pretty much all iterating. ... A tree structure will give you the ...
    (comp.lang.lisp)
  • Re: querying runtime data structures
    ... debugger or program slicer for Lisp would be a great first step. ... execution itself. ... tree of structs for all of the intermediate variables such that at the ... You could also traverse the tree ...
    (comp.lang.lisp)