![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/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 23:14:05
Message: <4aefae0d$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/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: 3 Nov 2009 00:22:55
Message: <4aefbe2f$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/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: 3 Nov 2009 09:53:22
Message: <4af043e2@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka <ano### [at] anonymous org> wrote:
> 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".
Which is O(n) because you have to get there first.
--
- Warp
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: 3 Nov 2009 09:56:47
Message: <4af044af@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> 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
|
![](/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: 3 Nov 2009 11:35:50
Message: <4af05be6$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/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: 3 Nov 2009 11:39:27
Message: <4af05cbf$1@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Darren New <dne### [at] san rr com> 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
|
![](/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: 3 Nov 2009 11:47:40
Message: <4af05eac@news.povray.org>
|
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |