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

Darren New <dne### [at] sanrrcom> 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

Warp schrieb:
> Darren New <dne### [at] sanrrcom> 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

clipka <ano### [at] anonymousorg> 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

Warp schrieb:
> clipka <ano### [at] anonymousorg> 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

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

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

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

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

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