Peter Norvig, in his book "Case Studies in Common Lisp" has an
interesting example of writing efficient functions.
He starts with a functionally correct, but inefficient, function:
(defun flatten (input)
"Return a flat list of the atoms in the input."
(cond ((null input) acc)
((atom input) (list input))
(t (append (flatten (first input)
(flatten (rest input) acc))))))
He explains that using append this way is inefficient, since append
copies the first argument, resulting in consing on the scale of O(n^2).
He goes on to say that using nconc, as the destructive version of
append, would help a bit, but a better way would be to use an
accumulator value like this:
(defun flatten (input &optional acc)
"Return a flat list of the atoms in the input."
(cond ((null input) acc)
((atom input) (cons input acc))
(t (flatten (first input)
(flatten (rest input) acc)))))
Both produce the same results, and by running them under (time), I can
see that the second version is indeed more efficient, taking less time,
using less bytes of memory, etc.
So that got me thinking: other than running functions through (time),
what tools/methods are available in Lisp for determining relative
efficiency of code?
Norvig appears to have used logic and reasoning.
It is important to measure things if you want to improve them: how
would you know if you were succeeding? But you should have a good
grasp of how to analyze the order of growth of your programs and be
comfortable with `Big O'. O(n^2) means that `moderate problems' you'd
throw at the computer (n ~ 10^3 - 10^5) turn into
`huge time sinks' (n^2 ~ 10^6 - 10^10). (Leading to the popular belief
that Lisp is slow.)
O(n^3) or O(n^4) means you better have a lot of horsepower at your
discretion or you better only use tiny
amounts of data.
O(x^n) means that you are in trouble.
O(log n) means that you get the answer fast, even for really big
problems.
O(log log n) means virtually instantaneous results, even if N is on the
order of the number of bits in memory.
Reducing the order of growth can yield *huge* benefits (and get you
praise, glory, and money depending on where the problem was fixed).
In article <························@o13g2000cwo.googlegroups.com>,
"dpapathanasiou" <···················@gmail.com> wrote:
> Peter Norvig, in his book "Case Studies in Common Lisp" has an
> interesting example of writing efficient functions.
>
> He starts with a functionally correct, but inefficient, function:
>
> (defun flatten (input)
> "Return a flat list of the atoms in the input."
> (cond ((null input) acc)
> ((atom input) (list input))
> (t (append (flatten (first input)
> (flatten (rest input) acc))))))
>
> He explains that using append this way is inefficient, since append
> copies the first argument, resulting in consing on the scale of O(n^2).
>
> He goes on to say that using nconc, as the destructive version of
> append, would help a bit, but a better way would be to use an
> accumulator value like this:
>
> (defun flatten (input &optional acc)
> "Return a flat list of the atoms in the input."
> (cond ((null input) acc)
> ((atom input) (cons input acc))
> (t (flatten (first input)
> (flatten (rest input) acc)))))
>
> Both produce the same results, and by running them under (time), I can
> see that the second version is indeed more efficient, taking less time,
> using less bytes of memory, etc.
>
> So that got me thinking: other than running functions through (time),
> what tools/methods are available in Lisp for determining relative
> efficiency of code?
look for 'metering' or 'profiling' tools.
Several Common Lisp implementation do support some kind of metering.
LispWorks has a profiling tool.
http://www.lispworks.com/documentation/lw445/LWUG/html/lwuser-122.htm#pgfId-885977
http://www.lispworks.com/documentation/lw445/CLWUG-M/html/clwuser-m-323.htm#pgfId-852601
This is another tool: 'metering'
http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/tools/metering/0.html
Some implementations have updated versions, IIRC.
--
http://lispm.dyndns.org/
I use Allegro's profiling tools often. I used 'metering' some years
ago with CMUCL and benefitted from it. Over on the other group, I
would be recommending JProbe. :-)