reserving memory for an array

[vfunc]

The amortized term is still a bullshit term. Just because someone
coined a term does not mean we should all use it.

 

[vfunc]

Where on this page does it mention amortized ?

http://en.wikipedia.org/wiki/Big-O_notation

"Amortized" is a misleading and non standard term.

 

[vfunc]

<snip>

If you disagree with that then you must agree with the converse which
is that

copying elements is <= O(1) non-amortized.

That is last statement is cleary false.

You agree with false statement, so you are wrong.

Not to put too fine a point on it, the posts I've seen you make thus far
do not make this claim particularly believable.

I've just shown that I have a better understanding than you, by proving
you wrong.


I refer to cheaters, being people that confuse others by conveniently
dropping terms like "amortized" to make things look better than they
really are, for their own personal gain. Imagine how preposterous it
would be if some athletes went around saying "my time for the 100m is
0.1", then when someone said that is impossible they conveniently
turned around and changed their tune to "my amortized time for the 100m
is 0.1, you are wrong."

Please post the exact errors you're receiving, and identify the compiler
you're using. If you can't get that to compile, I'm reasonably certain
there's a fairly serious problem either with your compiler, or with how
you're using it.

--

I will look elsewhere in future.

 

[Kai-Uwe Bux]

Where on this page does it mention amortized ?

http://en.wikipedia.org/wiki/Big-O_notation

Why should a page on O-notation mention amortized time? The notion of
amortized time is completely independent from O-notation, which is a purely
mathematical concept: given two real-valued functions f and g defined on
positive integers (or positive reals), one says f = O(g) if there is are
constants C and K such that f(x) <= C*g(x) + K for all x sufficiently
large. As such, this does not, in any way relate to some meanings that f an
g may or may not have outside mathematics. In particular, you can use
O-notations to describe relate all sorts of cost functions that occur in
computer science to all sorts of complexity functions for inputs

* worst case runtime as O( f( input-length ) )
* expected/average runtime
* amortized runtime
* worst case space consumption
* ...

In particular, it makes sense to describe the amortized run-time of
push_back() in std::vector and the worst-case run-time for operator[] in
std::vector as O(1).

"Amortized" is a misleading and non standard term.

It is a standard term in computer science (not in math). Also, it is not
misleading since it is a purely technical term that has a precise
definition and lacks any connotations. You may prefer constant time
algorithms to amortized constant time algorithms for whichever reasons, but
that does not mean that amortized constant time is false advertising.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

I refer to cheaters, being people that confuse others by conveniently
dropping terms like "amortized" to make things look better than they
really are, for their own personal gain. Imagine how preposterous it
would be if some athletes went around saying "my time for the 100m is
0.1", then when someone said that is impossible they conveniently
turned around and changed their tune to "my amortized time for the 100m
is 0.1, you are wrong."

This impression on your part is due to the fact that you first asked very
specifically about *access* in std::vector. That is constant time (not
amortized!). Then the discussion went on to other operations and there we
find amortized complexity bounds. It's not like you have been cheated by
someone who at a later point told you: "oh, did I forget to mention that it
was amortized". Access to elements in std::vector is constant time --
indepentend of the length of the vector. Always and not amortized!


Best

Kai-Uwe Bux

 

[Jerry Coffin]

Where on this page does it mention amortized ?

http://en.wikipedia.org/wiki/Big-O_notation

In the references. This page refers to _Introduction to Algorithms
(Second Edition)_ by Cormen, Leiserson, Rivest and Stein. Chapter 17 of
that book is titled "Amortized Analysis", and is devoted (surprise,
surprise) to amortized analysis of algorithms. Of course, amortized
analysis is used elsewhere in the book as well (the index entry of
"amortized analysis" has 19 sub-entries in addition to the reference to
chapter 17).

The authoritative reference for C++ is the ISO 14882, 2003 (second
edition). It uses the term in about a half dozen places, some of which
(e.g. section 23.1.1/12) apply to a rather large number of containers.

"Amortized" is a misleading and non standard term.

Nonsense!

It is a well-known term of art among computer scientists, and used in
leading references on the subject. With respect specifically to C++ it
is not only well-known, but officially and formally standardized as a
requirement in the C++ standard.

 

[Jerry Coffin]

[ ... ]

You agree with false statement, so you are wrong.

You're putting words in my mouth. Your previous statements were wrong,
and now you've descended to outright lies to try to cover them up.

I've just shown that I have a better understanding than you, by proving
you wrong.

Still more nonsense!

I refer to cheaters, being people that confuse others by conveniently
dropping terms like "amortized" to make things look better than they
really are, for their own personal gain. Imagine how preposterous it
would be if some athletes went around saying "my time for the 100m is
0.1", then when someone said that is impossible they conveniently
turned around and changed their tune to "my amortized time for the 100m
is 0.1, you are wrong."

First of all, people have been very careful to state that insertion into
a vector has amortized constant complexity from the beginning. You are
simply badly confused: you originally asked about _access_ to the array,
which has constant complexity -- NOT amortized constant, but simply
constant.

You then went on to confuse the two, and don't seem to have sorted
things out yet.

I will look elsewhere in future.

Just for grins, I'll even suggest on place elsewhere that you can look.
Comeau C++ is widely regarded as having the best conformance of any
compiler available. Nicely enough, Greg Comeau is kind enough to make a
version of it available via his web site. Running it over the code I
posted gives the following results:

-----------snip--------------------
Your Comeau C/C++ test results are as follows:

Comeau C/C++ 4.3.8 (Aug 19 2006 13:36:48) for ONLINE_EVALUATION_Alpha1
Copyright 1988-2006 Comeau Computing. All rights reserved.
MODE:strict errors C++


In strict mode, with -tused, Compile succeeded (but remember, the Comeau
online compiler does not link).
-----------end snip------------------

The URL for the test compiler is:

http://www.comeaucomputing.com/tryitout/

So anybody who cares to verify the code I posted can do so. Of course,
the compiler has far more uses than that. Since you claim to have had
difficulty getting your compiler to work with my code, after you try it
out, you should send Greg $50 and get a copy of his compiler, which
obviously works a lot better than whatever you've been using.

 

[Default User]

[ ... ]

You agree with false statement, so you are wrong.

You're putting words in my mouth. Your previous statements were
wrong, and now you've descended to outright lies to try to cover them
up.

He's a troll, plonk him or ignore him.




Brian

 

[Mark P]

Where on this page does it mention amortized ?

http://en.wikipedia.org/wiki/Big-O_notation

"Amortized" is a misleading and non standard term.

It's also not on this page:

http://en.wikipedia.org/wiki/Moron

Nor any of billions of other pages, but what has that to do with anything?

Perhaps check out this page:

http://en.wikipedia.org/wiki/Amortized_analysis

That you believe it to be a non-standard term and don't understand the
concept only betrays your ignorance on this subject.

 

[Dave Steffen]

[ ... ]

You agree with false statement, so you are wrong.

You're putting words in my mouth. Your previous statements were
wrong, and now you've descended to outright lies to try to cover them
up.

He's a troll, plonk him or ignore him.

Furthermore, he tends to respond to this kind of post (I posted a
similar comment over on one of the GCC help forums) with an
extraordinarily profane and insulting email. I'll probably get
another from this post. Gents, he really isn't worth the time.