Re: How can "cons per call" be so different for these two very similar functions?
- From: Pascal Bourguignon <pjb@xxxxxxxxxxxxxxxxx>
- Date: Thu, 31 Aug 2006 22:00:43 +0200
"dpapathanasiou" <denis.papathanasiou@xxxxxxxxx> writes:
Hi Pascal,
I understand that both implementations are O( length()*length() ), but
what confuses me is why metering shows a huge difference in consing,
when the two functions are essentially the same.
Because one conses the elements of atoms that are in corpus, and the
other conses the elements of atoms that are not in corpus.
So if you have in atoms 1000 elements that are in corpus and 10 that
are not, obviously the first one will cons 100 times more than the
other.
As I said, I thought initially that the extra (not) statement in the
second function may be the culprit, but as you said, that should have
no bearing on it.
Well, when you profile the consing of the lisp functions you usually
discard the consing done on purpose, to find implicit inherencies. In
that aspect, a NOT won't cons at all (unless we're running with some
special debugging option or something like that).
The point is that for example, a mere numerical function, like:
(defun isquare (x) (cond ((minusp x) (- (isquare (- x))))
((zerop x) 0)
(t (+ (isquare (1- x)) (* -2 (1- x)) 1))))
will cons, to allocate the bignum values generated. You might want to
optimize such a function to avoid consing.
On the otherhand, a function such as:
(defun explode (str) (loop :for ch :across str :collect ch))
will cons O(length(str)) cons cell, and this is not something you want
to avoid, since it's the purpose of the function. But then, you
cannot complain that:
(explode "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
conses more than:
(explode "y")
Is it something wrong with the metering package or my use of it? I
tried it several times, and in each case the cons per call ratios were
the same, i.e. about 110 cons per call for the first function, and over
7,100 for the second.
Check the documentation of this metering package. The column is
entitled "Cons per call", not "Cons cell per call". Consing includes
both the consing of cons cells, and the consing of other lisp objects.
This may be misleading, since a function that explicitely conses a
resulting list will increment this counter the same way as a function
that inadvertently conses discarted intermediate objects.
P.S. Thanks for the idea of pre-processing one of the lists: the first
of the two lists gets run through both functions over and over again
(i.e. we are checking sets of candidate lists versus a target list, so
preprocessing the target list would save us processing cycles).
Well if you alway use these two functions together, it would be more
efficient to generate both the results at once:
(defun split-on-corpus (atoms preprocessed-corpus)
(loop :for atom :in atoms
:if (gethash atom preprocessed-corpus)
:collect atom :into present
:else :collect atom :into absent
:finally (return (list present absent))))
(split-on-corpus '(a b c d e f) (preprocess-corpus '(a c e)))
--> ((A C E) (B D F))
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You cannot really appreciate Dilbert unless you read it in the
original Klingon"
.
- References:
- How can "cons per call" be so different for these two very similar functions?
- From: dpapathanasiou
- Re: How can "cons per call" be so different for these two very similar functions?
- From: Pascal Bourguignon
- Re: How can "cons per call" be so different for these two very similar functions?
- From: dpapathanasiou
- How can "cons per call" be so different for these two very similar functions?
- Prev by Date: Re: LISP V APL?
- Next by Date: Re: LISP V APL?
- Previous by thread: Re: How can "cons per call" be so different for these two very similar functions?
- Next by thread: Re: How can "cons per call" be so different for these two very similar functions?
- Index(es):
Relevant Pages
|
