On Tue, 2011-02-22 at 14:00 -0600, iwanttokeepanon wrote:
On Tue, Feb 22, 2011 at 8:32 AM, Michael Kay <mike(_at_)saxonica(_dot_)com>
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/
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--