Thread overview | ||||||
---|---|---|---|---|---|---|
|
July 23, 2010 Ropes | ||||
---|---|---|---|---|
| ||||
Not sure if this is what's used by an Appender, but this seems like a cool data structure: http://ahmadsoft.org/ropes/ http://en.wikipedia.org/wiki/Rope_%28computer_science%29 It's not good for indexing, but concatenation is an O(1) operation, so using it when you have to do a lot of appending seems to make a lot of sense. And, if I understand appender correctly, it's meant only for appending data and that you need to convert it to a range/array before you work with it. Casey |
July 23, 2010 Re: Ropes | ||||
---|---|---|---|---|
| ||||
Posted in reply to sybrandy | == Quote from sybrandy (sybrandy@gmail.com)'s article
> Not sure if this is what's used by an Appender, but this seems like a
> cool data structure:
> http://ahmadsoft.org/ropes/
> http://en.wikipedia.org/wiki/Rope_%28computer_science%29
> It's not good for indexing, but concatenation is an O(1) operation, so
> using it when you have to do a lot of appending seems to make a lot of
> sense. And, if I understand appender correctly, it's meant only for
> appending data and that you need to convert it to a range/array before
> you work with it.
> Casey
Appender is just a wrapper over the builtin array that caches the capacity instead of having to look it up in the bowels of the GC implementation. Appending to a regular array is amortized O(1) provided that the array implementation isn't absolutely asinine. (Most cases of concatenation, at least in my experience, are appending.)
|
July 23, 2010 Re: Ropes | ||||
---|---|---|---|---|
| ||||
Posted in reply to sybrandy | On 23/07/2010 23:43, sybrandy wrote:
> Not sure if this is what's used by an Appender, but this seems like a
> cool data structure:
>
> http://ahmadsoft.org/ropes/
>
> http://en.wikipedia.org/wiki/Rope_%28computer_science%29
>
> It's not good for indexing, but concatenation is an O(1) operation, so
> using it when you have to do a lot of appending seems to make a lot of
> sense. And, if I understand appender correctly, it's meant only for
> appending data and that you need to convert it to a range/array before
> you work with it.
>
> Casey
AFAIK ropes are implemented by using AVL or RB Trees. So every operation is similar to what you expect from the underlaying data structure.
Bjoern Lietz
Beside, some new IDE SourceCode-Editors are using Ropes as their workhorse.
|
July 24, 2010 Re: Ropes | ||||
---|---|---|---|---|
| ||||
Posted in reply to sybrandy | sybrandy Wrote: > Not sure if this is what's used by an Appender, but this seems like a cool data structure: > > http://ahmadsoft.org/ropes/ > > http://en.wikipedia.org/wiki/Rope_%28computer_science%29 > > It's not good for indexing, but concatenation is an O(1) operation, so using it when you have to do a lot of appending seems to make a lot of sense. And, if I understand appender correctly, it's meant only for appending data and that you need to convert it to a range/array before you work with it. > > Casey Also see http://www.ibm.com/developerworks/java/library/j-ropes/ for a lengthy cover of ropes. SGI has an implementation of ropes in it's STL lib http://www.sgi.com/tech/stl/Rope.html . |
Copyright © 1999-2021 by the D Language Foundation