From: Eric Mahurin <eric_mahurin@...>
Date: 2005-07-02T22:31:15+09:00
Subject: Re: O(1) performance for insertions/deletions at the front of an Array/String

--- Mathieu Bouchard <matju@artengine.ca> wrote:

> On Fri, 1 Jul 2005, Eric Mahurin wrote:
> 
> > 3. unshift has O(1) performance when you unshift no more
> than
> > the amount you have shifted.  I'd assume it just
> decremented
> > the start of array pointer.  When you unshift more than you
> > shifted, it is O(n), physically moving the data to the
> right.
> 
> The O(n) problem happens because when unshift is physically
> moving the
> data to the right, it does it by a fixed number of elements.
> Instead, it
> should do it by a percentage of the current size, which is
> would make it
> an amortized O(1). The actual percentage used has influence
> on the time
> constant.
> 
> I agree that Ruby should do it in amortized O(1).

Not exactly what I was thinking.  I was thinking that when you
try to unshift and you have no free space available to the
left, you'd reallocate to a new area growing by a certain
percentage - just like you do when you run out of space on the
right.

But, what you say should work just as well.  As long as most of
the time all insertions/deletions at the ends of the
array/string are O(1) and only every O(n) operations do you
have an operation that takes O(n) time.  This way the average
is still O(1) as you say.

The exact O(1) average performance of pushes/pops vs.
unshifts/shifts should just be a matter of what percentage of
free space you choose to make when you run out of capacity on
the left and on the right.  I'd like to see these the same, but
you may want to give more space on the right since more people
probably use pushes over unshifts now because of the
performance.

> > c. if shifts/unshifts can be made just as fast as
> pushes/pops,
> > you could cut the average time in half for random
> insertions
> > and deletions.
> 
> This is a bright idea! I vote for it!

Glad you like it.  I wonder if any other high-level languages
do something like what I'm talking about with their standard
stretchable arrays and strings.

To designate this new performance of unshifts, maybe a new
method should be added to Array and String: ">>".  This would
prepend/unshift a single element just like << appends/pushes a
single element.

OT a little ... regarding insertion/deletion do you think we
can also make a few methods in String vs Array a little more
consistent:

a. String#insert - make it also take a list of characters like
Array#insert takes a list of elements.  Right now if you want
to insert a single character, you have to create a String
object with that single character.  I use [,0]= right now since
the interface is the same between Array/String.

b. provide a String#delete_at just like Array#delete_at.  Not a
big deal since slice! works fine, but delete_at would probably
be a little more efficient since it isn't so overloaded.

c. provide push, pop, shift, unshift to String.  Not a big deal
since you can use random insert/delete methods, but they may be
a little more efficient.

d. OT even more ... allow Array#index and Array#rindex to take
an optional start index like String#index and String#rindex.




		
____________________________________________________ 
Yahoo! Sports 
Rekindle the Rivalries. Sign up for Fantasy Football 
http://football.fantasysports.yahoo.com