![](/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) |
<Jer### [at] enst fr> wrote:
> Moreover your implication goes the wrong way (ie the second inequation
> implies the first, not the other way round).
Hmm, maybe you are forgetting some fundamental things here...
2n lg n > 2n + n lg n | : n lg n
=>
n lg n > lim 2n
because n lg n can never be 0 in this case (so the division is legal). Of
course I am just silently dropping the + 1 here and some other changes to
the function because of the division.
> This doesn't make any mathematical sense since all four limits are
> infinity and therefore can't be compared. What can be said is that for a
> big enough n, you have:
> 2n lg(n) > 2n + n lg(n)
> and
> n lg(n) > 2n
Nope, you can do the following (as what I am up to is not a result, but only
a relative comparison of the growth rate):
lim 2n lg n > lim 2n + n lg n
n->oo n->oo
<=>
lim 2n lg n - 2n + n lg n > 0
n->oo
<=>
lim n lg n - 2n > 0
n->oo
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trf de
Visit POV-Ray on the web: http://mac.povray.org
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) |
In article <39bcdb54$1@news.povray.org> , Warp <war### [at] tag povray org> wrote:
> This code causes it. Can you see what is the mistake?
>
> #include <string>
> using namespace std;
>
> int main()
> {
> string x();
> x.clear();
> }
Oh yes, that is one of the classics that don't give any useful compiler
error message. At least now I know what it looks like in gcc, neither
Visual C++ nor CodeWarrior give a better error message <sigh>
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trf de
Visit POV-Ray on the web: http://mac.povray.org
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) |
Thorsten Froehlich wrote:
>
> <Jer### [at] enst fr> wrote:
>
> > Moreover your implication goes the wrong way (ie the second inequation
> > implies the first, not the other way round).
>
> Hmm, maybe you are forgetting some fundamental things here...
>
> 2n lg n > 2n + n lg n | : n lg n
>
> =>
>
> n lg n > lim 2n
>
> because n lg n can never be 0 in this case (so the division is legal). Of
> course I am just silently dropping the + 1 here and some other changes to
> the function because of the division.
>
All right, then how do you justify the first inequation? The valid
demonstration is:
lg(n) > 2 (for n > 3) | * n
=>
n lg(n) > 2n | + n lg(n)
=>
2n lg(n) > 2n + n lg(n)
> > This doesn't make any mathematical sense since all four limits are
> > infinity and therefore can't be compared. What can be said is that for a
> > big enough n, you have:
> > 2n lg(n) > 2n + n lg(n)
> > and
> > n lg(n) > 2n
>
> Nope, you can do the following (as what I am up to is not a result, but only
> a relative comparison of the growth rate):
>
> lim 2n lg n > lim 2n + n lg n
> n->oo n->oo
>
> ...
I wasn't really speaking about the reasoning. My point is that you
can't compare two infinite limits. The valid reasoning is to say that
for n big enough (in this case "big enough" means greater than 3) you
have those equations (without the limits). Or else redefine clearly what
you mean by:
lim ...
n->oo
since you're not using the standard definition.
Again it's more a complaint about the form of your reasoning (which is
wrong) than with the content (which for this part is right, I haven't
looked into the rest so I can't speak about the whole)
--
* Doctor Jekyll had something * mailto:ber### [at] iname com
* to Hyde... * http://www.enst.fr/~jberger
*******************************
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) |
On Sat, 09 Sep 2000 18:46:59 -0500, Thorsten Froehlich wrote:
>In article <39bab424@news.povray.org> , Warp <war### [at] tag povray org> wrote:
>
>> : No, it is a clear which one is faster, just my notation for the total was
>> : incorrect: See my later posts explaining it in more detail.
>>
>> You had another mistake (which I mentioned in another response).
>>
>> The total retrieval time in my case is O(n), not O(n*log(n)).
>
>No, it is O(log(n)) for each ++ operator, see my other post!
This depends on implementation. My favorite map (the one I use here) is
O(1) for each ++ operator, at the expense of a bit more bookkeeping at
insertion and deletion time. The bookkeeping is also O(1), though, so
it's dwarfed by the O(log n) the insert or delete already takes.
Whether implementation is prescribed by STL is something I don't know; I
haven't bothered to learn about STL yet as the compiler I'm forced to use
doesn't implement it (MSVC 1.52, the last 16-bit compiler MS made. Low-level
programming on Win9x is pretty much required to be 16-bit.)
--
Ron Parker http://www2.fwi.com/~parkerr/traces.html
My opinions. Mine. Not anyone else's.
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) |
On 11 Sep 2000 09:40:08 -0400, Warp wrote:
>Thorsten Froehlich <tho### [at] trf de> wrote:
>: Now set a breakpoint at i++ and step into the function. Go down until you
>: find a loop. If you can't find a loop, I would really like to know which
>: data structure your library uses to store maps (I assume it is a tree
>: structure).
>
> It's true that the operator++ has to make several steps in some cases but
>only when it has to go backwards in the tree. When going forward it has to
>make just one step. It has to make log(n) steps backwards only once (when
>going from the largest item which is smaller than the root item to the
>root item). It has to make log(n)/2 steps two times. And so on.
> What is the amortized O()-time for ++ then?
amortized time is still O(log(n)) in that case, unless I missed something.
> Btw, using some extra memory it could be possible to avoid all extra steps:
>By putting a pointer to the next item in the walk in each item.
This is precisely what my implementation does. The only thing I find lacking
in my implementation is the interface; the iterator is not separate and the
usage is confusing at best. Neither of those two flaws are my doing, however;
I was writing a more robust and efficient implementation of a class that was
designed by a drooling moron on crack (spelled consultant) before I started
here. The exact depth of the consultant's stupidity is unplumbed, but suffice
to say that they thought the best implementation was an unsorted array, with
O(1) insertion, O(n) deletion, and O(n) lookup per element. When this proved
to be too slow for the purpose, they "fixed" the problem by adding a cache to
keep the five (no, the cache size was not configurable) most recent results.
--
Ron Parker http://www2.fwi.com/~parkerr/traces.html
My opinions. Mine. Not anyone else's.
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) |
On 11 Sep 2000 16:39:05 -0400, Ron Parker wrote:
>On 11 Sep 2000 09:40:08 -0400, Warp wrote:
>> What is the amortized O()-time for ++ then?
>
>amortized time is still O(log(n)) in that case, unless I missed something.
You are missing something: The iterator doesn't have to start at the
root of the tree (assuming the map is implemented as a tree)
to find the next item, so the the search time is generally much
faster than log(n).
In fact, for a splay tree, it only has to follow one pointer.
For a binary tree where each node has a pointer to its parent, it is
a bit more complicated: In 50% of the cases, the current node will be
the left leaf, so two pointer operations (up, right down) are needed.
In 25 % it is the right leaf of a node on the left of its parent, so 4
operations (up, up, right, left) are needed, etc:
1/2 *2 + 1/4 * 4 + 1/8 * 6 + 1/16 * 8 ...
works out to exactly 4, which is also O(1).
Oops, I just noticed that only my leave nodes have data, but I'm too
lazy to calculate this now for a normal binary tree, and it should even
be better, anyway.
Note that a binary tree without "up" pointers doesn't have any way
to get from one node to the next, so the iterator will have to do
additional bookkeeping in this case.
hp
--
_ | Peter J. Holzer | Nicht an Tueren mangelt es,
|_|_) | Sysadmin WSR | sondern an der Einrichtung (aka Content).
| | | hjp### [at] wsr ac at | -- Ale### [at] univie ac at
__/ | http://www.hjp.at/ | zum Thema Portale in at.linux
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) |
: (except that I'm surprised that this works inside another
: function
The C standard says that a function definition can be done inside another
function. If done so, the scope of that function definition is only inside
that other function (it has a clear modular reason).
Thus, the C++ standard supports it as well.
--
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- 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 wrote:
>
> : (except that I'm surprised that this works inside another
> : function
>
> The C standard says that a function definition can be done inside another
> function. If done so, the scope of that function definition is only inside
> that other function (it has a clear modular reason).
> Thus, the C++ standard supports it as well.
>
One of the big differences between C and Pascal is precisely that the
Pascal standard allows definitions of function inside another while the
C standard doesn't (or so I always thought). Something to do with the
ability to return a function as the result of a function call. I don't
know the exact position of C++ in this respect but I assumed it followed
the C standard.
--
* Doctor Jekyll had something * mailto:ber### [at] iname com
* to Hyde... * http://www.enst.fr/~jberger
*******************************
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) |
On 12 Sep 2000 05:17:32 -0400, Warp wrote:
>: (except that I'm surprised that this works inside another
>: function
>
> The C standard says that a function definition can be done inside another
>function. If done so, the scope of that function definition is only inside
>that other function
No, only function *declarations* inside other functions are permitted,
but not function *definitions*.
Thus:
int main(void) {
extern void foo(void);
void();
return 0;
}
is allowed, but:
int main(void) {
void foo(void) {
printf("hello\n");
}
void();
return 0;
}
is not.
>(it has a clear modular reason).
There is a good technical reason why it is not allowed. It makes
function pointers very difficult to implement and unintuitive to use.
Nevertheless, gcc implements it as an extension.
hp
--
_ | Peter J. Holzer | Nicht an Tueren mangelt es,
|_|_) | Sysadmin WSR | sondern an der Einrichtung (aka Content).
| | | hjp### [at] wsr ac at | -- Ale### [at] univie ac at
__/ | http://www.hjp.at/ | zum Thema Portale in at.linux
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) |
Peter J. Holzer <hjp### [at] sikitu wsr ac at> wrote:
: No, only function *declarations* inside other functions are permitted,
: but not function *definitions*.
I meant what you are saying, ie. declaration. I know that you can't put
the body of the function inside another function.
I really don't know the difference between the words "declaration" and
"definition".
Usually when I have to refer to the body of the function I use
the word "implementation". It may be wrong, though.
--
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- 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) |