Re: How can "cons per call" be so different for these two very similar functions?

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.

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.

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.

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).

.

Relevant Pages

  • Re: Equality, Assignment and The Emperors New Clothes
    ... In the case of copy-cons, only one new cons is allocated. ... In the case of copy-tree, a new cons for all the conses of the tree ... show lists: ... don't clone the class of account, neither the classes of account or of ...
    (comp.lang.scheme)
  • Re: delete command weirdness
    ... A appears only in the car of the first cons). ... Now delete is forced to do some work, and makes the cdr of the first ... always just (setq testing (remove 'a testing)). ... If you've got lists millions of items long, ...
    (comp.lang.lisp)
  • Re: Newbie question about "cons"?
    ... cons structure is just a list of conses jointed by cdr pointers, ... can substitute an array consisting entirely of "car" pointers. ... CDR-coding ALLOWS lists to have cells allocated ...
    (comp.lang.lisp)
  • Re: Changing value of a list variable passed as argument to function
    ... that variable changed in a way 'push' macro would change it? ... the type LIST is a hack: (OR CONS NULL) ... You can also use arrays, symbols, cons cells, clos objects, etc ...
    (comp.lang.lisp)
  • Re: Basic List processing
    ... Is there a Lisp function which is callable something like: ... Technically, the lang does not support list as a primitive, only cons, ... Lisp at core is based on functional programing on lists. ...
    (comp.lang.lisp)