Re: What is expensive about consing

On Wed, 10 Sep 2008 08:12:12 +0200, Pascal J. Bourguignon wrote:

[non-guaranteed CL:APPLY for arbitrarily sized lists]

Because of call-arguments-list. The portable form is:

(if (< (length number-list) call-arguments-limit)
(apply (function +) number-list)
(reduce (function +) number-list))

Ah, thanks. That sucks for execution speed, though! O(N) for the CL:LENGTH
operation on a list, when (depending on domain, of course), you're very
unlikely to exceed call-arguments-limit (4096 on my local CLISP) in a
single list.

But even if you take Rob's good suggestion of a :max-args keyword, is
there an efficient way of splitting variable-length lists into chunks?
You still need to traverse each cons (via ELT or similar) to chop them up.

Either way of doing it (CL:REDUCE vs split-into-c-a-l-sizes and then
CL:APPLY on each list) still seems like O(N2) performance either way.

Adam
.

Relevant Pages

  • Re: Did anyone else get a mass e mail from this kid?
    ... the Katrina fund is a different link. ... And, depending on the content of the email Rob received, that may very ... I wouldn't mind being a teenage girl. ... post wish lists, up to and including things like cars and college tuition. ...
    (rec.music.makers.percussion)
  • Re: choosing off various lists
    ... See Debra Dalgleish's site for instructions on creating dependent lists. ... Gord Dibben MS Excel MVP ... then gives a different clist to choose off in colujmn two depending on what I ... and the same for the third column? ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Another vlookup question
    ... Frank Kabel ... > worksheet which has the exact same tables for the exact same part ... > the lists populating A16 and B16 are the ones I need to have change ... > columns of prices are different depending on the size of the part. ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Did anyone else get a mass e mail from this kid?
    ... the Katrina fund is a different link. ... And, depending on the content of the email Rob received, that may very well ... I wouldn't mind being a teenage girl. ... post wish lists, up to and including things like cars and college tuition. ...
    (rec.music.makers.percussion)
  • Re: Another vlookup question
    ... "Frank Kabel" schrieb im Newsbeitrag ... > different prices (depending on style) in the remaining columns. ... > I have a drop down list that lists the part numbers, ...
    (microsoft.public.excel.worksheet.functions)