From: Eric Mahurin <eric.mahurin@...>
Date: 2007-11-07T04:39:14+09:00
Subject: Re: [QUIZ] Editing Text (#145)

On 11/5/07, Matthew Moss <matthew.moss.coder@gmail.com> wrote:
> My solution is a deque... The text before the cursor is kept
> left-to-right, while the part after the cursor is reversed. This makes
> for some very simple code for the basic operations, using mostly
> push/pop.

I'm glad to see someone try an Arrays instead of a Strings.  You'd
think the run-time would be similar between the two since the number
of method calls should be the same (#<< and #slice(-1) instead of
#push and #pop).  But, the memory should be about 4X-8X though since
each array slot takes 32/64-bit object pointer/handle instead of an
8-bit character.

> It might be worthwhile to not reverse the data, and make the
> code slightly more assymetric by combining the push/pop with
> unshift/shift. (Didn't try that, though...)

Don't expect very much performance since unshift is usually O(n).

> Initially, the "left" method was @post.push(@prev.pop), with the
> "right" method similar. This proved to be terribly slow, so I kept a
> "temporary" cursor that would collapse multiple left/right operations
> into a single "sift" (i.e. moving n chars from one to the other). The
> "sync" calls ensure that we do that sift before other operations.

Odd.  I tried both ways with String and it was faster to do @post <<
@prev.slice(-1).  Since the operations I used were O(1), I think it
boiled down to minimizing the number of method calls.  Using deferred
"sifting" resulted in more complexity and method calls.  I wouldn't be
surprised if there is some performance bug with @post.push(@prev.pop
or return).

> The most complex methods (and slowest) here are "up" and "down".
> Breaking the internals down into multiple lines rather than just the
> @prev/@post pair, or somehow keeping track of the newlines would help
> with the speed of up/down, but I got lazy.  =)

These are way too slow.  It looks O(n**2).  You should look to see
what happens when you double the size.  I think you might have hit an
Array COW (copy-on-write) performance/memory bug(/leak?).  I've seen
plenty of them.

Why not use the deferred "sifting" like you do for left/right instead?
 This would avoid the problem.

Eric