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

Darren New wrote:
> 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.

I think what I've liked about Qt is that I rarely find myself in a 
position where I *think* I know how to do something, but I'm wrong. 
With the other GUI toolkits I've used (there aren't very many 
unfortunately) I often found situations where there seemed to be many 
ways to solve a problem, many of which ended up not doing what I wanted. 
  With Qt, if I don't know how to do something, I find that I generally 
*know* that I don't know how to do it.

Post a reply to this message

Kevin Wampler wrote:
> I think what I've liked about Qt is that I rarely find myself in a 
> position where I *think* I know how to do something, but I'm wrong. 

That's always a bonus, yes. The "one right way to do it" approach.

How do you make the background transparent? Not obvious. How do you get rid 
of the mouse cursor? Several ways you could do that. The obvious way of 
showing a single web page in an application needs extra levels of 
complication it shouldn't. None of them are too hard to figure out, but none 
of them were "right" on the first try.

How do you get the underlying DirectFB object? No good way. How do you get 
the javascript interpreter pointer (i.e., the QScriptEngine)? No good way. 
How do you pass extra CFLAGS recursively thru qmake? No idea. What keycodes 
mean what to webkit? Can't tell. How do you add a plug-in without 
recompiling? Not really clear.

I think a lot of the confusing stuff involves webkit, which is a 
bag-on-the-side.  Otherwise it's really pretty straightforward. 
Unfortunately for me, guess what I'm working with?

> I find that I generally *know* that I 
> don't know how to do it.

It's still hard to know whether it's possible or not, sometimes.

But yeah, it's definitely high quality software. It's mostly just the 
complexity (and the fact that I'm probably doing something relatively 
unusual with it).

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> 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".

  Which is O(n) because you have to get there first.

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Amortized O(1) append is only O(1) if you double the size of the array each 
> time you insert something.

  There are two errors in that sentence:

1) You don't double the size of the array each time you insert something. You
   do so each time the array gets full.

2) AFAIK it's not necessary to precisely *double* the size of the array in
   order to get amortized constant time insertion. It's enough to multiply
   the size of the array by a constant factor (eg. 1.5).
   (Although don't quote me on that, as I haven't done the math.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   Which is O(n) because you have to get there first.

I think that the insert happens after you already decide where to insert it. 
  What if the insert is always performed after the third element of the 
list? You're back to O(1).

That's like saying appending to the end of an array with enough space is 
O(n) because you first have to search thru the array to ensure the value you 
want to insert isn't already there.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Amortized O(1) append is only O(1) if you double the size of the array each 
>> time you insert something.
> 
>   There are two errors in that sentence:
> 
> 1) You don't double the size of the array each time you insert something. You
>    do so each time the array gets full.

Yes. Brain-o.

> 2) AFAIK it's not necessary to precisely *double* the size of the array in
>    order to get amortized constant time insertion. It's enough to multiply
>    the size of the array by a constant factor (eg. 1.5).
>    (Although don't quote me on that, as I haven't done the math.)

The amortization is the sum of one over the number of elements you move. And 
yes, I'm pretty sure you're right. Basically, it needs to be a geometric 
progression of expansions that converges, rather than bumping up to (say) 
the next prime number or adding a constant or something.

-- 
   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:
> geometric progression of expansions that converges, rather than bumping 
> up to (say) the next prime number or adding a constant or something.

In other words, "bump the size by 4096" doesn't give you O(1) behavior 
unless you decide that remapping memory blocks is "free". If you assume 
remapping memory blocks takes a fixed amount of time per remap (even if it's 
a fixed amount of time regardless of how many blocks you remap) I think 
you're back to O(1).

Of course, by the time you're talking about that sort of thing, order 
statistics fall apart, because you have a limited amount of address space in 
C and C++ (as in, sizeof(void*) is fixed and finite), so you're going to run 
out of memory before it really makes a difference.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message