Subject: Re: [xsl] Cheaper to prepend or append an item to a sequence? From: Liam R E Quin <liam@xxxxxx> Date: Tue, 22 Feb 2011 17:15:17 -0500 |
On Tue, 2011-02-22 at 14:00 -0600, iwanttokeepanon wrote: > On Tue, Feb 22, 2011 at 8:32 AM, Michael Kay <mike@xxxxxxxxxxxx> wrote: > > > Even with a forward-chained list, you can implement append without copying > > if you choose, at least for the first append operation to a given list > > (which 9 times out of 10 will be the only append operation). > > How is that? If I have X=[1,2,3] ; Y=X ; Z=Y++[4] > > How can Z append Y without copying it first? You of course cannot > modify Y in FP at all (which you know), much less w/o changing X. Saxon is not itself written in a functional language. Suppose that X is not used again, but only Z is used, in your example. So, we have at the start: X [1, 2, 3] Y undefined Z undefined and then at the end we have X irrelevant Y irrelevant Z [1,2,3,4] The underlying implementation could write, procedurally, Z.listStart := X; tmp := [4]; /* make a new list */ X.lastItem.next = tmp; /* append */ X.lastItem = tmp; /* save the end pointer */ This is an O(1) list append, and no copy was used. It's also a case that's worth optimising in a lot of languages. Of course, keeping a pointer to the last item in a list as well as the first increases memory overhead; it's a tradeoff. And good code would abstract that operation of appens-without-copy, obviously. Liam -- Liam Quin - XML Activity Lead, W3C, http://www.w3.org/People/Quin/ Pictures from old books: http://fromoldbooks.org/ Somtimes blog - http://barefootliam.org/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Cheaper to prepend or app, Michael Kay | Thread | Re: [xsl] Cheaper to prepend or app, iwanttokeepanon |
Re: [xsl] Thought i knew this but i, Michael Kay | Date | Re: Re: [xsl] Thought i knew this b, russurquhart1 |
Month |