Functions on generic sequences

From: Dave Roberts (ldave-re-move_at_re-move.droberts.com)
Date: 10/26/04 

Date: Tue, 26 Oct 2004 06:00:40 GMT

So I wanted to write a function that would average the numbers in a
sequence: either a list or an array. My first attempt was quite lame, but
functional:

(defun average (sequence &key (key #'identity))
;;; WARNING: Sloppy code. Could compute len and sum at same time
  (let ((len (length sequence))
        (sum (reduce #'+ sequence :key key)))
    (/ sum len)))

This is obviously slower than need be for a number of reasons. The most
obvious is that for lists, it traverses things twice, once to find the
length and then again to create the sum.

I then decided to specialize things a bit and arrived at:

(defun fast-average (sequence &key (key #'identity))
  (etypecase sequence
    (list (loop for x in sequence
                count x into length
                sum (funcall key x) into sum
                finally (return (/ sum length))))
    (vector (loop for x across sequence
                  sum (funcall key x) into sum
                  finally (return (/ sum (length sequence)))))))

Now, this works well: the runtime on a long list is about half that of the
first version, which is what you would expect if you only traverse the list
once, not twice.

The main problem is that it seems so bifurcated. By that I mean that the
first version seems to really operate on sequences while the second is
obviously two routines, each specialized on a data type.

Is there anyway to sort of harmonize these two, giving some that has better
runtime but yet doesn't get totally data-type specific? 

-- 
Dave Roberts, ldave-re-move@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog/

Relevant Pages

  • Re: abundance of irrationals!)
    ... No such "sum" exists except as, and only as, the limit of the infinite ... If an infinite sequence does not have to "achieve" its limit, ... > It is only for lists not initially known not to be surjective that ...
    (sci.math)
  • TOC of Python Cookbook now online (was Re: author index for Python Cookbook 2?)
    ... Processing a String One Character at a Time ... Finding a File on the Python Search Path ... Constructing Lists with List Comprehensions ... Looping over Items and Their Indices in a Sequence ...
    (comp.lang.python)
  • Re: Subclassing list the right way?
    ... about how overriding methods on them will affect other method calls. ... special interpretation of negative indexes (if the class wishes to ... outside the set of indexes for the sequence (after any special ... either write a lot of code or restrict the way you use lists to a ...
    (comp.lang.python)
  • Re: Newbie-Question concerning list and inheritance
    ... > OK, I'm hopefully a little less of a Lisp newbie these days, but Lisp's ... lists are simply built from cons cells. ... > list, sequence, t" ... > either, really, but I can kind of see why one might want to subclass ...
    (comp.lang.lisp)
  • Re: tuple.index()
    ... You can put any combination of things into both tuples and lists. ... tuple rather than a mutable sequence like a list. ... element is no real substitute for knowing its position. ... presence of an element is as good as knowing its position (since the ...
    (comp.lang.python)