Re: deques, deques, and dequeues

Ray Dillinger wrote:
For what it's worth, I get it about amortized analysis.
But to me what it usually means is, "You can and should
rewrite this so that the upperbound time is guaranteed
to be on this order."

That view is simply to narrow and in practice fails to yield
the "best" solutions. For example, there are dynamic array
algorithms that yield worst-case (note this is the correct
term for what you keep calling "upperboound") O(1) insert.
However, in practice they result in slower overall array
performance (most importantly random access) due to larger
constants (ie the constant multipliers typically left out
of o-notations).

As has been pointed out elsewhere, balancing asymptotic
with pragmatic behavior is key.

In this case, rewriting for O(1) would involve having
two parallel structures internally, and doing a small
number of pointer copies on each and every insert.
That way you can guarantee a bounded return time no
matter how big the dequeue gets, as long as your "new"
structure is a constant factor larger than your "old"
one.

I guess I've been bitten by too many "Green threading"
systems where if *any* return time is unbounded it leads
to unacceptable system behavior, even if "amortized time"
is constant.

I fail to see what you are on about with "guarantee a
bounded return time" and "unbounded [time] leads to
unacceptable system behavior". None of the algorithms so
far discussed are "unbounded". For example insertion time
for any of the algorithms discussed so far is certainly
worst-case O(n) for a single insert and O(n^2) total.

Further, I doubt you would ever have cause to deal with
algorithms that are not worst-case o(exp(n)) (note that is
little-oh meaning asymptotically dominated). So what is the
relevance of this "unbounded" behavior you speak of? Which
algorithms are you thinking of that are "unbounded"? (Not
including infinite loop bugs and such obviously ;-)

The General

.

Relevant Pages

  • Re: Cantors diagonal proof wrong?
    ... >about how some important things are formally defined in mathematics. ... algorithms and procedures in a context where they don't exist. ... and it's able to guarantee that everything your function ... Unsolicited bulk E-mail subject to legal action. ...
    (sci.math)
  • Re: double with precision
    ... approximates, troubles start cropping up. ... If you compute the same number with different algorithms, ... guarantee the results will be bang on. ...
    (comp.lang.java.help)