Re: deques, deques, and dequeues

On May 9, 7:28 pm, Ray Dillinger <b...@xxxxxxxxx> wrote:
tyreciu...@xxxxxxxxx wrote:

Depending on the re-allocation strategy, it is actually an amortized
constant time operation. I'd have to look it up to recall the exact
math behind it, but if you double the size of an array each time re-
allocation is necessary, then is is O(1) on average over all of the
insertions into the array.

O() notation is, by definition, worst case. Not average case.
Amortized time is not what we're talking about. Not that it
will make a difference in most cases to a player...

I was speaking imprecisely. When I said average, I meant 'mean' as
opposed to 'typical'. Amortized analysis is a well-developed field of
algorithmic analysis. See for instance "Introduction To Algorithms" by
Corman, Leiserson, Rivest, Stein where in the second edition, chapter
17 is devoted to amortized analysis.

I'll try to outline my intuitive understanding, though you should look
in the literature for the precise mathematical proofs. Suppose you
have an array which you dynamically resize and copy when it is full.
Suppose it takes one operation to insert if you don't have to
dynamically size it. And that it takes n operations to insert if you
are inserting the nth time and a copy/allocation is required. I'm
thinking of inserts and deletes only at the end, but it is equivalent
if you consider it to be a ring buffer.

Now, the worst case here is that you have many inserts with no
deletes, because when you get a delete that allows an extra insert
before the next copy-allocation phase. So lets just consider what
happens with n inserts. Lets say that the initial size of the buffer
is k.

Re-allocation strategy 1 (success), double the array size when re-
allocating:
Insert k items: Cost = k
Insert 2k items: Cost = k (From first k inserts) + k + 1 (re-allocate
buffer on k+1'th insert) + k - 1 (next k-1 inserts) = 3k
Insert 4k items: Cost = 3k (From first 2k inserts) + 2k + 1 (re-
allocate buffer on 2k+1'th insert) + 2k - 1 (next 2k-1 inserts) = 7k
Insert 8k items: Cost = 7k (From first 4k inserts) + 4k + 1 (re-
allocate buffer on 4k+1'th insert) + 4k - 1 (next 4k-1 inserts) = 15k
etc.

There is a mathematical induction that must be done here, but as the
number of items inserted approaches infinity, the mean cost of each
insert approaches 2. This is in the worst case. That is the idea
behind amortized analysis. So it has an amortized cost of O(1). Now
let us compare with another strategy.

Re-allocation strategy 2 (failure), add k to array size when re-
allocating:
Insert k items: Cost = k (same as before up to now)
Insert 2k items: Cost = 3k (same as before up to now)
Insert 3k items: Cost = 3k (from first 2k inserts) + 2k + 1 (re-
allocate buffer on 2k+1'th insert) + k - 1 (next k - 1 inserts) = 6k
Insert 4k items: Cost = 6k (from first 3k inserts) + 3k + 1 (re-
allocate buffer on 3k+1'th insert) + k - 1 (next k - 1 inserts) = 10k

Notice that there is a difference in number of operations even at 4k.
Rather than converging at at constant number, the mean operations per
insert converges at O(n) (at a quick guess. It is definitely bigger
than O(1)). This means that this strategy in the worst case performs
at O(n) in amortized cost.

This is, of course, a non-rigorous demonstration.

The point is that in the worst case, you still only end up with a
couple of operations per insert if you allocate wisely. Now this isn't
as 'good' as a standard O(1) case. This is because while the mean
operations per second is constant, there is greater variance in how
much processing time a particular insert will cost. However, it is
usually 'good enough'. You are right when you say that in most cases
it doesn't matter to a user.

I hope this clears up the ambiguity of my previous post. And thanks
again for the nifty idea about deque<> iterators. That is something
that I haven't seen before.

-D

.

Relevant Pages

  • Re: Solar Systems, Entry level--- More
    ... a 50K solar PV array. ... cost much more to install/re-install a PV array than it does to re- ... MUCH MUCH less than the PV installation), it is typical that the PV ...
    (alt.home.repair)
  • Re: passing a string to a dll
    ... Part of the reason I wasn't certain about the cost of std::map is that it is a balanced ... array sounds suspect as a strategy. ... bool IsValidCode(string codeToCheck) ... Putting them in a DLL has effectly zero impact. ...
    (microsoft.public.vc.mfc)
  • Solar Systems, Entry level--- More
    ... in the value on their house, on the market today, will be if they ... a 50K solar PV array. ... cost much more to install/re-install a PV array than it does to re- ... MUCH MUCH less than the PV installation), it is typical that the PV ...
    (alt.home.repair)
  • Re: Germanys solar panels produce more than Japans entire nuclear facilities did.
    ... Kilowatt solar energy system. ... A two Kilowatt solar array would cost ...
    (soc.retirement)