Hello,
I am writing an application in Common Lisp which requires me
to get some elements of a list.
And it should also truncate the original list.
e.g.
(defun return-plist-from-net-name (net-name hash-table)
(let* ((temp-struc (gethash net-name hash-table))
(ret-list (net-record-value temp-struc)))
(if (> (length ret-list) 6)
;(error "Too long plist here for Net: ~S" net-name)
(progn
(rplacd (nthcdr 5 ret-list) nil)
(format t "~% Doing polynomial compaction..~S" (length ret-list))
(setf (net-record-value temp-struc) ret-list))
ret-list)))
Will the "rplacd"ed portion of the list which is not
pointed by anything be GCed.
Is there some alternative method to "return" the first N
element of a list, and destroy (GC)
the original list.
TIA
Sandeep
From: ········@hotmail.com
Subject: Re: [Q] How to return "some" elements of a list
Date:
Message-ID: <874gvp$r95$1@nnrp1.deja.com>
In article <···············@natlab.research.philips.com>,
Sandeep Koranne <·······@natlab.research.philips.com> wrote:
> Hello,
> I am writing an application in Common Lisp which requires me
> to get some elements of a list.
> And it should also truncate the original list.
>
Dear Sandeep,
MUST you destroy the original list? Not very functional in programming
style, but here we go:
<lisp code>
(defvar *notes* '(do re mi fa so la ti))
*notes*
=> (DO RE MI FA SO LA TI)
(nbutlast *notes* (- (length *notes*) 5)) ; ugh!
=> (DO RE MI FA SO)
*notes*
=> (DO RE MI FA SO)
</lisp code>
(n.b. this actually modifies the original list, so you aren't
/completely/ destroying your original list (as you asked for later in
your email), but I think that fn NBUTLAST is the one you're looking for
-- it works on actual lists as well as (in the example above) global
variables.)
(n.b. this isn't a super-duper efficient algorithm. Paul Graham points
out that fn LENGTH walks the whole list to find its length (that's why
I have "; ugh" in the code). If you know the length of the incoming
lists before-hand, change NBUTLAST to the number, and not the call to
LENGTH.)
Sincerely,
Doug Auclair
Sent via Deja.com http://www.deja.com/
Before you buy.
Thanx to all those who replied:
I now have some pointers to proceed forward.
Doug Auclair wrote : "Not very functional in programming style "
I know that modifying the argument of the function
is not "functional programming" per se:
But look at this :
(defun my-functional-function (input-list)
;; Copy in-list to COPY
;; do some operations on the COPY
;; return COPY and forget the in-list
)
This would be functional : but sice I know that the original
"in-list" will not be used any more,
I am modifying it in place.
Any comments : on bending-a-little-functional-programming vs efficiency
And the function "nbutlast" looks very in-efficient for my purpose.
what do you think of my RPLACD approach, just NILLIFY the CDR of the N-1 cell.....
regards
sandeep
Sandeep Koranne <·······@natlab.research.philips.com> wrote in message
····················@natlab.research.philips.com...
> This would be functional : but sice I know that the original
> "in-list" will not be used any more,
> I am modifying it in place.
>
> Any comments : on bending-a-little-functional-programming vs efficiency
Yeah. Don't do it until profiling shows that it's necessary. You may find
that you might need to use the function in a place where you can't destroy
the list. Or you might find that you are sharing the copied structure
somewhere and destroying it inadvertently, introducing subtle and
hard-to-find buds. In any case, it makes the code less clear. Again,
unless it's necessary by proof of profiling, don't do it.
faa
Frank A. Adrian wrote among other things :
"By proof of profiling" :
The onl;y way I think you can PROVE things like this are
1. writing the code yourelf => to understand it better
2. analyzing the control flow carefully
3. have some analytical estimate like O(n^3) etc
Profiling : by definition : at best can be described as sampling
at discrete time so cannot match in accuracy with analytical techniques.
b.t.w I KNOW that that part of the code is used O(n^2) times (there are
no control flow statements outside the loop)
II) The question was "bending-a-liitle-functional-programming" not
leaving it all together as you have thought.
Regards,
Sandeep.
From: Tim Bradshaw
Subject: Re: [Q] How to return "some" elements of a list
Date:
Message-ID: <ey3r9ev98lw.fsf@cley.com>
* Sandeep Koranne wrote:
> Profiling : by definition : at best can be described as sampling
> at discrete time so cannot match in accuracy with analytical
> techniques.
Yes, but doing exhaustive analysis on a 100,000 line program which is
known to be factor of 2 too slow is kind of a pain, especially as
analysis is typically pretty vague about those big factors that are
killing you.
--tim
Tim wrote :
>Yes, but doing exhaustive analysis on a
>100,000 line program which is
>known to be factor of 2 too slow is kind of a pain
Not if you have written it yourself..
come on now..
sandeep
From: Tim Bradshaw
Subject: Re: [Q] How to return "some" elements of a list
Date:
Message-ID: <ey3emavraxi.fsf@cley.com>
* Sandeep Koranne wrote:
> Tim wrote :
>> Yes, but doing exhaustive analysis on a
>> 100,000 line program which is
>> known to be factor of 2 too slow is kind of a pain
> Not if you have written it yourself..
> come on now..
Are you *serious*?
From: His Holiness the Reverend Doktor Xenophon Fenderson, the Carbon(d)ated
Subject: Re: [Q] How to return "some" elements of a list
Date:
Message-ID: <w4ovh4912ty.fsf@nemesis.irtnog.org>
>>>>> "SK" == Sandeep Koranne <·······@natlab.research.philips.com> writes:
SK> This would be functional : but sice I know that the original
SK> "in-list" will not be used any more, I am modifying it in
SK> place.
I am not so sure that mutating a copy of an input is functional in
style. A functional program might recurse through a input list (for
example), and build up a NEW LIST AS IT GOES based on each element of
the input list. There is no mutation, and the copying happens in
place. Functional programs (as I understand the term) do not use
mutations or side effects to get things done.
SK> Any comments : on bending-a-little-functional-programming vs
SK> efficiency
Well, one can optimize certain programs written in the functional
style. For example, if a recursive subroutine is tail recursive, the
compiler doesn't need to cons up a new stack for each recursion,
i.e. it becomes a loop. There's all sort of tricks to make hairy
recursive programs tail recursive; look up the term "continuation
passing style" for some examples there.
HTH.
--
JOHN CAGE (strapped to table): Do you really expect me to conduct this
antiquated tonal system?
LEONARD BERNSTEIN: No, Mr. Cage, I expect you to die!
Sandeep Koranne <·······@natlab.research.philips.com> wrote in message
····················@natlab.research.philips.com...
> Thanx to all those who replied:
> I now have some pointers to proceed forward.
>
> Any comments : on bending-a-little-functional-programming vs efficiency
>
Before looking at performance, measure it. You don't want to `optimize'
code
that rarely runs, and you don't want your `optimizations' to degrade
performance.
There are a lot of non-obvious factors that might affect the performance:
A generational GC requires a write barrier, so RPLACD might be more
expensive
than you think. But maybe the write barrier uses the paging hardware, so it
is cheap after the first trap if the cells are all on the same page.
But CONS can never allocate an `oldspace' cell, so it doesn't need the write
barrier. But the implementation may not optimize this.
A copying GC runs in time proportional to the live cells. Rapidly CONSing
and
discarding storage with a generational gc that is tuned correctly is
virtually
cost free in terms of performance. Your newest generation will most
certainly
be in memory.
On the other hand, rapidly CONSing and *retaining* storage for longer than a
GC cycle will seriously degrade the performance. But then again, you may be
able to tune the GC around this.
It is important to measure a quantity before you attempt to change it.
From: Barry Margolin
Subject: Re: [Q} How to return "some" elements of a list
Date:
Message-ID: <s7jl4.46$qd1.774@burlma1-snr2>
In article <···············@natlab.research.philips.com>,
Sandeep Koranne <·······@natlab.research.philips.com> wrote:
>Will the "rplacd"ed portion of the list which is not
>pointed by anything be GCed.
Yes. By definition, something that isn't pointed to by anything is
garbage, and the GC is supposed to clean up all garbage.
>Is there some alternative method to "return" the first N
>element of a list, and destroy (GC)
>the original list.
I don't think so. There are standard functions for returning a sublist,
but they copy rather than modifying the original.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.