Subject: Re: [xsl] Cheaper to prepend or append an item to a sequence? From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Tue, 22 Feb 2011 06:40:43 -0800 |
> 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). What people want is to be able to append one list to another in O(N) time, not in O(N^2). This is why people chose to pre-pend the elements of the second list (starting from the last) to the first list. Cheers, Dimitre Novatchev --------------------------------------- Truly great madness cannot be achieved without significant intelligence. --------------------------------------- To invent, you need a good imagination and a pile of junk ------------------------------------- Never fight an inanimate object ------------------------------------- You've achieved success in your field when you don't know whether what you're doing is work or play ------------------------------------- Facts do not cease to exist because they are ignored. On Tue, Feb 22, 2011 at 6:32 AM, Michael Kay <mike@xxxxxxxxxxxx> wrote: > On 22/02/2011 13:58, Dimitre Novatchev wrote: >> >> The accepted term in most functional programming languages is "a list". >> >> A list is a functional data structure (immutable). Appending to a list >> causes the whole list to be copied and is O(N). Prepending a list is >> making just the "next pointer" of an item point to the list -- an O(1) >> operation. >> > > 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). > > Michael Kay > Saxonica > > --
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Cheaper to prepend or app, Michael Kay | Thread | Re: [xsl] Cheaper to prepend or app, Вячеслав Седов |
Re: [xsl] Cheaper to prepend or app, Michael Kay | Date | AW: [xsl] tricky problem filtering , Szabo, Patrick \(LNG |
Month |