Subject: Re: Cheaper to prepend or append an item to a sequence?
From: Michael Kay <mike@xxxxxxxxxxxx>
Date: Tue, 22 Feb 2011 22:07:37 +0000
|
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?
When one list A is a sublist of another list B, A does not need separate
storage - it can be implemented by means of pointers to the first and
last items from B that are to be included in A. Therefore if A is not
already a sublist of another list, you can create B by making a longer
list and making A a sublist of the new list. Saxon does this using
arrays rather than linked lists, but the same principle would work
either way.
Michael Kay
Saxonica
|
Cart
