![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
http://doc.trolltech.com/4.2/containers.html#algorithmic-complexity
Their "growth strategies" give you an amortized time of O(n), not O(1) as
documented. :-)
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Warp
Subject: Re: Trolltech doesn't know how amortized time works
Date: 2 Nov 2009 14:47:30
Message: <4aef3752@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> wrote:
> http://doc.trolltech.com/4.2/containers.html#algorithmic-complexity
Everybody always says that "inserting in the middle of a linked list is
a constant-time operation". My response to that is: "Ok, if that is so, then
give me a function which takes a linked list and an element as parameters,
and make the function insert the element in the exact middle of the list in
constant time. I'll wait."
The claim is rather imprecise. You can't just magically insert an element
in the middle of a list in constant time. You have to get there somehow first.
Only if you happen to have, from some previous operation, an iterator pointing
to the place where you want to insert, *then* it will be a constant-time
operation.
A more precise wording would be: "Inserting an element in a linked list at
the location pointed by any given iterator is a constant-time operation."
Then the complexity of the thing is left to getting said iterator.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp schrieb:
> Darren New <dne### [at] san rr com> wrote:
>> http://doc.trolltech.com/4.2/containers.html#algorithmic-complexity
>
> Everybody always says that "inserting in the middle of a linked list is
> a constant-time operation". My response to that is: "Ok, if that is so, then
> give me a function which takes a linked list and an element as parameters,
> and make the function insert the element in the exact middle of the list in
> constant time. I'll wait."
>
> The claim is rather imprecise. You can't just magically insert an element
> in the middle of a list in constant time. You have to get there somehow first.
> Only if you happen to have, from some previous operation, an iterator pointing
> to the place where you want to insert, *then* it will be a constant-time
> operation.
The claim /is/ precise: Whenever you want to insert an element into
/any/ data structure, you /always/ need to first figure out /where/ to
insert, so the cost of an insertion operation is /always/ specified
presuming that the insertion is to happen at a /predetermined/ location.
Of course if someone only considers the cost of insertion, neglecting
any other costs his algorithm may incur, he's doin' it wrong...
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Warp
Subject: Re: Trolltech doesn't know how amortized time works
Date: 2 Nov 2009 15:28:14
Message: <4aef40de@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka <ano### [at] anonymous org> wrote:
> The claim /is/ precise: Whenever you want to insert an element into
> /any/ data structure, you /always/ need to first figure out /where/ to
> insert, so the cost of an insertion operation is /always/ specified
> presuming that the insertion is to happen at a /predetermined/ location.
"Inserting" and "inserting in the middle" are two slightly different
things. The latter is making a more concrete claim.
As said, if you really can "insert in the middle" of a linked list in
constant time, give me such a function.
If the claim is "insert at the location pointed by an iterator", then
the claim is true.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp schrieb:
> clipka <ano### [at] anonymous org> wrote:
>> The claim /is/ precise: Whenever you want to insert an element into
>> /any/ data structure, you /always/ need to first figure out /where/ to
>> insert, so the cost of an insertion operation is /always/ specified
>> presuming that the insertion is to happen at a /predetermined/ location.
>
> "Inserting" and "inserting in the middle" are two slightly different
> things. The latter is making a more concrete claim.
>
> As said, if you really can "insert in the middle" of a linked list in
> constant time, give me such a function.
It's not "in the middle" in the sense of "at the centroid", but in the
sense of "not at the beginning nor at the end, but at an arbitrary
position somewhere in between".
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Darren New
Subject: Re: Trolltech doesn't know how amortized time works
Date: 2 Nov 2009 18:01:36
Message: <4aef64d0@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka wrote:
> Of course if someone only considers the cost of insertion, neglecting
> any other costs his algorithm may incur, he's doin' it wrong...
Trolltech gets the numbers wrong even if you insert always at the end.
Amortized O(1) append is only O(1) if you double the size of the array each
time you insert something. It's not O(1) if you add a fixed size to the
array each time (assuming you're copying elements from the old array to the
new array each time, of course).
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Kevin Wampler
Subject: Re: Trolltech doesn't know how amortized time works
Date: 2 Nov 2009 18:21:47
Message: <4aef698b$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New wrote:
> (assuming you're copying elements from the old array
> to the new array each time, of course).
They do seem to actually address exactly this assumption with respect to
their resizing scheme:
"This makes sense because modern operating systems don't copy the entire
data when reallocating a buffer; the physical memory pages are simply
reordered, and only the data on the first and last pages actually needs
to be copied"
In fact, they explicitly address this difference with respect to QVector:
"Since the cost of reallocating is higher in that case, QVector<T>
reduces the number of reallocations by always doubling the memory when
running out of space."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Darren New
Subject: Re: Trolltech doesn't know how amortized time works
Date: 2 Nov 2009 20:37:53
Message: <4aef8971$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Kevin Wampler wrote:
> "This makes sense because modern operating systems don't copy the entire
> data when reallocating a buffer; the physical memory pages are simply
> reordered, and only the data on the first and last pages actually needs
> to be copied"
Well, yes, there is that. Hmmm... OK, it seems they do know what that's
about. I guess if you don't copy the pages in the middle of the string,
there's no need to double the size each time to get O(1) amortized growth.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Kevin Wampler
Subject: Re: Trolltech doesn't know how amortized time works
Date: 2 Nov 2009 22:29:38
Message: <4aefa3a2$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New wrote:
> Kevin Wampler wrote:
>> "This makes sense because modern operating systems don't copy the
>> entire data when reallocating a buffer; the physical memory pages are
>> simply reordered, and only the data on the first and last pages
>> actually needs to be copied"
>
> Well, yes, there is that. Hmmm... OK, it seems they do know what that's
> about. I guess if you don't copy the pages in the middle of the string,
> there's no need to double the size each time to get O(1) amortized growth.
In general my experience with using Qt has been extremely positive, so I
would have been surprised had they made a mistake of that magnitude.
Still, I certainly didn't anticipate that the algorithm they use would
actually be O(1), so it was quite cool to see that it was.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
From: Darren New
Subject: Re: Trolltech doesn't know how amortized time works
Date: 2 Nov 2009 22:50:06
Message: <4aefa86e@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Kevin Wampler wrote:
> In general my experience with using Qt has been extremely positive, so I
> would have been surprised had they made a mistake of that magnitude.
Well, lots of people think that (for example) growing a hash table by adding
a few thousand buckets each time it fills up amortizes out to O(1), but it
doesn't.
> Still, I certainly didn't anticipate that the algorithm they use would
> actually be O(1), so it was quite cool to see that it was.
Honestly, I'm rather impressed they documented it at all. Maybe I'm just
cynical, tho.
And yes, I'm finding Qt to be sort of "this is the bit that C++ forgot to
define." Sort of like how jQuery is "this is what javascript should have
been in the first place."
Altho I must admit, I occasionally smack my head against the wall repeatedly
trying to find how to make something work. You *know* it's a simple
question, but it's just not in the docs.
--
Darren New, San Diego CA, USA (PST)
I ordered stamps from Zazzle that read "Place Stamp Here".
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |