[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
Re: [xsl] Cheaper to prepend or append an item to a sequence?
Subject: Re: [xsl] Cheaper to prepend or append an item to a sequence? From: iwanttokeepanon <iwanttokeepanon@xxxxxxxxx> Date: Wed, 23 Feb 2011 10:21:28 -0600 |
>> 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. On Tue, Feb 22, 2011 at 4:15 PM, Liam R E Quin <liam@xxxxxx> wrote: > 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. Thanks Michael and Liam, that makes sense. Having an end pointer or scope information that let's you actually mutate an irrelevant list would be great optimizations in the implementation. -- Rod
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Cheaper to prepend or app, Liam R E Quin | Thread | [xsl] template never matches, Merrilees, David |
Re: Re: [xsl] Thought i knew this b, Brandon Ibach | Date | [xsl] Relpath_utils.xsl and UTF-8 D, Eliot Kimber |
Month |