 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 08 Sep 2000 13:36:17 -0500, Thorsten Froehlich wrote:
>For inserting: O(n * log(n))
>For retrieval: O(n * log(n))
>Total: O(n * log(n) + n * log(n))
>
>
>I can get:
>
>For inserting: O(n)
>For sorting *: O(n * log(n))
>For retrieval: O(n)
>Total: O(2 * n + n * log(n))
>
>* No fancy algorithm, just quicksort.
You seem to have a misconception about how O() notation works. The total
for the first case is O(n*log(n)) and the total for the second case is...
O(n*log(n)). They might have different constant factors, but the determination
of which is faster is entirely a matter of determining those constant factors
(which depend on the constant factors in the component parts of the algorithm.)
BTW, if this comparison method worked, I could beat you both. I have a
balanced, fully-threaded 2-3 tree implementation with O(n log n) insertion
and O(n) traversal.
--
Ron Parker http://www2.fwi.com/~parkerr/traces.html
My opinions. Mine. Not anyone else's.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39b9050f@news.povray.org>, Warp <war### [at] tag povrayorg>
wrote:
> So instead of spending 1/2 hour once to learn how to use the STL you
> spend 2 hours every time you want to use a weighted binary tree?
No, I want to spend 2-5 hours learning how to implement it myself. Then
I can spend 1.5 hours figuring out the STL(or fighting with the STL) to
do the same thing.
> : And because I don't want to be
> : separated from what my program is doing?
>
> Sorry, I didn't understand at all what are you talking about here.
If I use the STL, I don't know exactly what is happening in my program.
If something goes wrong with a program using something I implemented, I
know the code, and can figure out the problem quickly. If something goes
wrong and I am using the STL, I end up trying to figure out why STL
files are producing errors, whether or not the problem is actually *in*
the STL.
> : And because when I was *trying*
> : to learn the STL, I often got errors and couldn't figure out why?
>
> Get a proper compiler and try again. You can get one by free.
I have an excellent compiler and good libraries. That doesn't help
understanding the reasons I get errors.
> And read documentation and tutorials.
I have been collecting links to various STL tutorials/overviews on the
web. I also plan to buy some books, when I can. I have a book with a lot
of detailed information on the STL, but it seems more reference oriented
than tutorial oriented.
--
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/
<><
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39b91926@news.povray.org>, "Thorsten Froehlich"
<tho### [at] trfde> wrote:
> Hmm, sounds like reinventing the wheel to me ;-)
Exactly.
> The thing is once you have done it two or three times it gets really
> boring writing the same code over and over again and it distracts
> from the fun part of programming and especially it distracts from the
> actual problem you want to solve.
That is fine, but at the moment, I want to have a grasp of how they
work. I can imagine programmers taught to always use the STL
encountering a simple doubly linked list in someone else's code and
being completely baffled by it...I want to understand the tools I use,
and how to implement them myself if necessary. For example: a game
project with extremely severe speed requirements, developing for
platforms where the STL isn't useable, writing in other languages which
I may learn in the future, etc. Especially that last one...I don't
expect C++ and STL to last forever, knowledge of algorithms is portable,
knowledge of the STL is not.
--
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/
<><
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <01c019ce$7da07900$917889d0@daysix>, "H. E. Day"
<Pov### [at] aolcom> wrote:
> Yo, Chris, when can we expect the fixed version of the +.3? The memory
> leak has sorta crippled my IRTC anim...
Real Soon Now. I have a couple more things to work out, and a couple
small features I want to add.
--
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/
<><
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <slr### [at] fwicom> , ron### [at] povrayorg (Ron
Parker) wrote:
> You seem to have a misconception about how O() notation works. The total for
> the first case is O(n*log(n)) and the total for the second case is...
I know, but I don't care enough (especially as a full "prove" is rather
long) as all I want to point out is that a map will not perform better than
a slightly different and in plain C easier to write algorithm than the
RB-tree most likely used for the map. As for the total, you are right that
I shouldn't just have copy and pasted it together assuming anybody would get
the idea I wanted to show.
> O(n*log(n)). They might have different constant factors, but the
> determination of which is faster is entirely a matter of determining those
> constant factors (which depend on the constant factors in the component parts
> of the algorithm.)
Yes, I am aware the constants matter here when using a simple sorting method
(merge sort) as I suggested.
To make you happy, I could have written (for the worst cases):
Numbers following variables should be read as subscripts!
T1(n) = (c1 * n * log n + c2) + (c3 * n * log n + c4) =
(c1 + c3) * n * log n + (c2 + c4)
T2(n) = (c5 * n + c6) + (c7 * n + c8) + (c9 * n * log n + c10) =
(c5 + c7) * n + (c9 * n * log n) + (c6 + c8 + c10)
For a large enough n this will hold:
c2 + c4 < (c5 + c7) * log n
and
c6 + c8 + c10 < (c5 + c7) * log n
So, I simply eliminate c2, c4, c6, c8 and c10 (set them to one) and can get:
T1(n) = (c1 + c3) * n * log n
T2(n) = (c5 + c7) * n + (c9 * n * log n)
Lets further assume that c1 = c3:
T1(n) = 2 * c1 * n * log n
T2(n) = (c5 + c7) * n + (c9 * n * log n)
And now comes the tricky part because I have to show that (c1 + c3) > c9. I
do not need to assume anything about c5 and c7 as n * log n > n for a big
enough n. this leaves:
T1(n) = 2 * c1 * n * log n
T2(n) = c9 * n * log n
I assume that for map a RB-tree is used and for list.sort a merge sort that
just flips the pointers of two strings. In both cases the algorithms need
to perform n * log n string comparisons, so we can just not count those.
This leaves the recursive calls and the swap operation for the merge sort,
and the walking through the tree (twice).
I assume that the merge sort will be faster*, but if anybody is not happy
with this, for string sorting there are plenty of other algorithms out
there...
In conclusion it is without problems possible to outperform the map used in
this case, and this is all I wanted to point out.
Thorsten
* I don't want to spend the time to show this now.
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <slr### [at] fwicom> , ron### [at] povrayorg (Ron
Parker) wrote:
>>For inserting: O(n * log(n))
>>For retrieval: O(n * log(n))
>>Total: O(n * log(n) + n * log(n))
>>
>>
>>I can get:
>>
>>For inserting: O(n)
>>For sorting *: O(n * log(n))
>>For retrieval: O(n)
>>Total: O(2 * n + n * log(n))
>>
>>* No fancy algorithm, just quicksort.
>
> You seem to have a misconception about how O() notation works. The total for
> the first case is O(n*log(n)) and the total for the second case is...
> O(n*log(n)). They might have different constant factors, but the
> determination of which is faster is entirely a matter of determining those
> constant factors (which depend on the constant factors in the component parts
> of the algorithm.)
>
> BTW, if this comparison method worked, I could beat you both. I have a
> balanced, fully-threaded 2-3 tree implementation with O(n log n) insertion
> and O(n) traversal.
(Referring to my previous reply):
Or, I could just prove that
lim 2n lg n > lim 2n + n lg n
n->oo n->oo
=>
lim n lg n > lim 2n
n->oo n->oo
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Fri, 08 Sep 2000 13:36:17 -0500, Thorsten Froehlich wrote:
>Total: O(n * log(n) + n * log(n))
which is O(n * log(n)
>Total: O(2 * n + n * log(n))
which is also O(n * log(n)
No difference there.
Which one of the two algorithms is really faster depends on the
implementation and the input data.
hp
--
_ | Peter J. Holzer | Nicht an Tueren mangelt es,
|_|_) | Sysadmin WSR | sondern an der Einrichtung (aka Content).
| | | hjp### [at] wsracat | -- Ale### [at] univieacat
__/ | http://www.hjp.at/ | zum Thema Portale in at.linux
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <slr### [at] tealhhjpat> ,
hjp### [at] SiKituwsracat (Peter J. Holzer) wrote:
>>Total: O(n * log(n) + n * log(n))
>
> which is O(n * log(n)
>
>>Total: O(2 * n + n * log(n))
>
> which is also O(n * log(n)
>
> No difference there.
Yes, because I was lazy and just did a copy and paste. In big-O notation
this will be the result, but this is not the whole issue (just eliminate the
big-O in the total!).
> Which one of the two algorithms is really faster depends on the
> implementation and the input data.
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.
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <slr### [at] tealhhjpat> ,
hjp### [at] SiKituwsracat (Peter J. Holzer) wrote:
> Which one of the two algorithms is really faster depends on the
> implementation and the input data.
No, it does not depend on the input data too much. The reason being that
the tree used for the map will be balanced so you should always have about
log n access time. And for the merge sort it also does not matter, it will
always take n log n time.
I fell for the trap of the big-O notation at first, too, when replying to
Ron, but I was simply implying the wrong thing at first by using big-O
notation for the totals, especially because you can't compare big-Os of
functions anyway ...
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Chris Huff wrote:
> > you will have to get most of them sooner or later anyway ;-)
>
> ...and I know I will. :-)
> Especially graphics and algorithms books, all I have are "introduction
> to C/C++/Java" books and one good C++ intro/reference book(C++ Primer
> Plus, which does cover the STL, just in a somewhat incomprehensible way
> for someone who doesn't already use it).
> Hmm, maybe I can get my parents to pay for them...probably not.
Have you got
"Code Complete" - Steve McConnell
"The Mythical Man-Month" - Frederick P. Brooks Jr. (anniversry edition)
"Peopleware" - Demarco & Lister
"Rapid Development" - Steve McConnell
"Extreme Programming Explained" - Kent Beck
Of those, I'd say the first two are a must for you for now, and the others
are for as you get time.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>Real Soon Now... and a couple
> small features I want to add.
famous last words of all programmers.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> and how to implement them myself if necessary. For example: a game
> project with extremely severe speed requirements, developing for
> platforms where the STL isn't useable,
read "Game Architecture and Design" by Rollings and Morris and you'll
realize these notions are very outdated. programs are getting too big,
and computers too fast for any one person or team to develop all the
code in-house or worry about speed optimization. libraries are the
future. just look at the quake engines. those are libraries. other
developers are starting to make other specific libraries, like physics,
installation, or interface libraries. the book i mentioned talks about
this and has application for all fields of software development; it just
goes in to games a little more.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39B9D82F.9D3E3C56@yahoo.com>, ryan constantine
<rco### [at] yahoocom> wrote:
> read "Game Architecture and Design" by Rollings and Morris and you'll
> realize these notions are very outdated. programs are getting too big,
> and computers too fast for any one person or team to develop all the
> code in-house or worry about speed optimization.
This is true for most applications, but only gets rid of one of my
arguments, and isn't applicable to all situations.
What about my other arguments? Platforms where the STL doesn't exist or
is too bulky, new languages, etc.
> libraries are the future. just look at the quake engines. those are
> libraries. other developers are starting to make other specific
> libraries, like physics, installation, or interface libraries.
This has very little to do with the reason I want to learn those
algorithms. Besides, I might end up programming one of those libraries!
They don't just come out of nowhere, they are written by programmers who
know how to do that stuff.
--
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/
<><
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39B9D612.294DF35E@yahoo.com>, ryan constantine
<rco### [at] yahoocom> wrote:
> >Real Soon Now... and a couple
> > small features I want to add.
>
> famous last words of all programmers.
Specifically, there are two features I want to add:
A small optimization in case of "turbulence 0", maybe for all places
that can use turbulence.
Glow transformations.
I have added two new glow types, but they are unfinished(they don't work
right when the glow is covered by or partly embedded in an object). I
don't plan to finish them before releasing a new version, though.
--
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/
<><
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
| I have added two new glow types, but they are unfinished(they don't work
| right when the glow is covered by or partly embedded in an object). I
| don't plan to finish them before releasing a new version, though.
What two new glow types? Enlighten me!
H.E. Day
<><
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <01c01a81$c5b12c40$697889d0@daysix>, "H. E. Day"
<Pov### [at] aolcom> wrote:
> What two new glow types? Enlighten me!
A sphere glow with constant density(sort of like a transparent sphere
with fade_color, but a bit faster and doesn't require intersection
calculations), and a glow using the exp() function.
I added a keyword to scale the size, and added another keyword to limit
the glow to a spherical area(this might speed some scenes up). The
keywords are "size" and "radius".
I added a falloff exponent feature, to adjust the rate at which the glow
dims with distance.
I have removed the turbulence feature, but you can now specify any
warps. It will be slightly slower with turbulence and the same speed
without it, but you will have more flexibility now, with black holes,
displace warps, etc.
I added the ability to transform the glow. Scaling only affects the
position, though, since there are currently only point sources.
And here are some features which won't be in the next version, but which
I am planning:
A pigment to control the color(definitely not realistic, but potentially
useful).
Different rendering modes: emission/additive, like it does now,
multiplicative, a mode which imitates scattering media, with constant
density(or some density functions which can be calculated directly), etc.
And I still haven't added that optimization for "turbulence 0", it isn't
a very high priority, since there is an obvious workaround.
I am also thinking of a similar lens flare feature. A separate patch,
not part of the glow feature, but based on the same rendering methods,
and with additional stuff to make it more flare-like.
--
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/
<><
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich <tho### [at] trfde> wrote:
: If you get an error message you end up having to analyse error messages and
: try to figure out what is wrong.
This is a very common problem with templates (specially ones that have
many parameters).
I don't think there's any bullet-proof solution to the problem. When I really
want to analyze an error message which mentions some STL template, I filter
it (with sed or perl) to get rid of the template parameters. The error message
gets a lot clearer.
Usually I don't need to decipher the error message. I only look at the
line of code (ie. in my code) that caused the problem and usually see what
it was. Some times it's more difficult, however. Some error types you just have
to know to see them (eg. trying to use a class without copy constructor with
STL).
: Now, this isn't even an example with an STL problem and it can still be hard
: to understand the problem. Try making a simple mistake just like declaring
: a nested template with '>>' at the end. How useful is the error message you
: get from _your_ compiler?
Believe me, the error messages of gcc are MYSTICAL! :)
For example, can you say what causes this error message?
request for member `clear' in `x', which is of non-aggregate type `string ()()'
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Chris Huff <chr### [at] maccom> wrote:
: If I use the STL, I don't know exactly what is happening in my program.
: If something goes wrong with a program using something I implemented, I
: know the code, and can figure out the problem quickly. If something goes
: wrong and I am using the STL, I end up trying to figure out why STL
: files are producing errors, whether or not the problem is actually *in*
: the STL.
Do you use the string class? Do you use streams? Do you use any standard
function?
Do you know exactly what does each one of them do?
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich <tho### [at] trfde> wrote:
: Is this by any chance the only example you have? ;-)
Yes. And why not? I could write more similar examples, but what would
be the point? I think one is enough.
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich <tho### [at] trfde> wrote:
: The return is missing...
The standard says that the return is optional (don't ask me why).
: Total: O(n * log(n) + n * log(n))
This is equal to O(n * log(n))
: I can get:
: Total: O(2 * n + n * log(n))
This is also equal to O(n * log(n))
So in terms of O both ways are equally fast.
: How? That is simple: I read in the words. Then sort them and then just
: count when retrieving.
But it uses more memory (specially if there are many repetitions).
: Of course I can do this using the STL (see below)! But your example shows
: something dangerous you forgot: the STL can trick you into thinking you
: have found a good algorithm, but in fact yours is nearly log(n) times slower
: than mine for most cases (for log(n) > 2)!
The O-notation doesn't know the term "log(n) times slower" if the speed
is already at least O(log(n)).
My version and your version have both the same O value and there's a good
reason for this in this case: Your version can be a lot slower when the
input is very big and there's a lot of repetition (imagine that the input
is "word1 word2 word1 word2..." millions of times). The speed is still
O(n*log(n)) in relation with the size of the input, but the speed factor can
vary a lot.
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich <tho### [at] trfde> wrote:
: Hmm, lets see, you need (runtimes from the C++ Prog. Lang 3rd Ed. page
: 464)...
: For inserting: O(n * log(n))
: For retrieval: O(n * log(n))
By the way, you are wrong here.
It's true that retrieval is O(n*log(n)), but an operator++() of the
iterator is O(1), so the retrieval of the whole tree is O(n) in my case.
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich <tho### [at] trfde> 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)).
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39baafd0@news.povray.org>, Warp <war### [at] tagpovrayorg>
wrote:
> Do you use the string class? Do you use streams? Do you use any
> standard function?
I actually use strings so rarely that I haven't bothered to learn more
than the very basics of the string class...I do plan on learning it
though.
I do use streams, and other standard functions.
> Do you know exactly what does each one of them do?
Not all of them, but I try to find out if I can. And none of them have
the learning curve the STL does, and some(streams and/or some of the
standard functions) are almost completely necessary for writing useful
platform-independant programs...the STL isn't. I don't think this is a
valid comparison.
And why such a strong reaction to my wanting to know the data structures
and algorithms behind the STL before learning the STL itself? The STL
can make life easier *for those who already know it*, and for those who
plan on programming only in C++, but it is definitely not necessary. I
do plan on learning it eventually, I never said it wasn't useful, I just
don't need to use it right now.
--
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/
<><
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Chris Huff <chr### [at] maccom> wrote:
: And why such a strong reaction to my wanting to know the data structures
: and algorithms behind the STL before learning the STL itself?
I'm sorry.
My strong reaction was not to that. Of course it's important to know how
does a class work before using it. For example, I myself didn't use the
deque class in my programs until someone told me exactly how does it work,
although people had recommended me to use it for a specific task. After
I was aware of how it works I realized that it really is perfect for that
specific task and I started using it.
My strong reaction was to the negative attitude against the STL which you
showed (or at least I got that impression). Nothing personal :)
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Btw, the good think about the STL classes is that they are all very
similar. Once you learn how to use one of them you'll probably be able to
immediately use almost any of the others as well.
And iterators are just brilliant.
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39bab3c5@news.povray.org> , Warp <war### [at] tagpovrayorg> wrote:
> Thorsten Froehlich <tho### [at] trfde> wrote:
> : Hmm, lets see, you need (runtimes from the C++ Prog. Lang 3rd Ed. page
> : 464)...
>
> : For inserting: O(n * log(n))
> : For retrieval: O(n * log(n))
>
> By the way, you are wrong here.
>
> It's true that retrieval is O(n*log(n)), but an operator++() of the
> iterator is O(1), so the retrieval of the whole tree is O(n) in my case.
OK, so Stroustrup is wrong? Maybe you found try finding out that he is
right for yourself. Just change your loop to:
for(wlist_t::iterator i=words.begin();
i!=words.end();)
{
cout << i->first << ": " << i->second << endl;
i++;
}
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).
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39bab424@news.povray.org> , Warp <war### [at] tagpovrayorg> 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!
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39bab334@news.povray.org> , Warp <war### [at] tagpovrayorg> wrote:
> : How? That is simple: I read in the words. Then sort them and then just
> : count when retrieving.
>
> But it uses more memory (specially if there are many repetitions).
Yes, it uses more memory, but in case you overlooked it, in one of my posts
I prove (using limits) that the worst case of your method will be slower for
a big enough n.
In case you start mentioning memory allocation time is not constant,
consider that I know the size of memory needed in advance, so I just need
one allocation for loading everything into memory!
> : Of course I can do this using the STL (see below)! But your example shows
> : something dangerous you forgot: the STL can trick you into thinking you
> : have found a good algorithm, but in fact yours is nearly log(n) times slower
> : than mine for most cases (for log(n) > 2)!
>
> The O-notation doesn't know the term "log(n) times slower" if the speed
> is already at least O(log(n)).
Did I use big-O notation here? I can't see it. To repeat my other post
(also mentioned above):
lim 2n lg n > lim 2n + n lg n
n->oo n->oo
=>
lim n lg n > lim 2n
n->oo n->oo
I agree that my language is not very good at explaining the speed
difference, but I think "nearly log(n) times slower" describes the above
very well!
> My version and your version have both the same O value and there's a good
> reason for this in this case: Your version can be a lot slower when the
> input is very big and there's a lot of repetition (imagine that the input
> is "word1 word2 word1 word2..." millions of times). The speed is still
> O(n*log(n)) in relation with the size of the input, but the speed factor can
> vary a lot.
Yes, but as I mentioned before, my only mistake was adding them up in the
total and leaving the big-O around it. I never said "O(n * log(n) + n *
log(n)) < O(2 * n + n * log(n))" or even "O(n * log(n)) < O(n * log(n))".
Just remove the big-O around the totals, and everything is correct!
I really should have cared more and we wouldn't have this argument about the
total big-O which has nothing to do with your implementation being slower
for a big enough n, which is all I wanted to show!!!
In fact you are falling in the same trap I fell at first when replying to
Ron: Trying to compare these two functions based on big-O notation! But
you simply cannot compare two functions with the same big-O with each other
using big-O. Other methods are needed, i.e. limits will solve the problem
for the worst case very well.
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39bab87c@news.povray.org> , Warp <war### [at] tagpovrayorg> wrote:
> And iterators are just brilliant.
It is easy to make the wrong assumptions about them, i.e. how fast they
really are for some data structures. Nevertheless, they are really useful!
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39baaf56@news.povray.org> , Warp <war### [at] tagpovrayorg> wrote:
> Believe me, the error messages of gcc are MYSTICAL! :)
>
> For example, can you say what causes this error message?
>
> request for member `clear' in `x', which is of non-aggregate type
> `string ()()'
Hmm, this is a funny error message. What is the cause? I am curious!
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39bab071@news.povray.org> , Warp <war### [at] tagpovrayorg> wrote:
> Thorsten Froehlich <tho### [at] trfde> wrote:
> : Is this by any chance the only example you have? ;-)
>
> Yes. And why not? I could write more similar examples, but what would
> be the point? I think one is enough.
I think this example is very abstract in what it does is a typical "demo
application", and the map data type is rather hard to understand without any
explanation. Some example showing a more "common" known data type like a
list and some string operations would probably be more impressive.
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39bab7db@news.povray.org>, Warp <war### [at] tagpovrayorg>
wrote:
> My strong reaction was to the negative attitude against the STL which
> you showed (or at least I got that impression). Nothing personal :)
You mean what I was saying about using other languages? Sorry that it
wasn't clear what I meant...at least I know not to take up writing as a
profession. :-)
--
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/
<><
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich wrote:
>
> In article <39baaf56@news.povray.org> , Warp <war### [at] tagpovrayorg> wrote:
>
> > Believe me, the error messages of gcc are MYSTICAL! :)
> >
> > For example, can you say what causes this error message?
> >
> > request for member `clear' in `x', which is of non-aggregate type
> > `string ()()'
>
> Hmm, this is a funny error message. What is the cause? I am curious!
>
My bet is: forgotten parenthesis (ie: "x.clear;" instead of
"x.clear();")
Jérôme
--
******************************* Jérôme M. BERGER
* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde... * http://www.enst.fr/~jberger
*******************************
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich wrote:
>
> lim 2n lg n > lim 2n + n lg n
> n->oo n->oo
>
> =>
>
> lim n lg n > lim 2n
> n->oo n->oo
>
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
Moreover your implication goes the wrong way (ie the second inequation
implies the first, not the other way round).
> In fact you are falling in the same trap I fell at first when replying to
> Ron: Trying to compare these two functions based on big-O notation! But
> you simply cannot compare two functions with the same big-O with each other
> using big-O. Other methods are needed, i.e. limits will solve the problem
> for the worst case very well.
>
Limits won't solve the problem at all since they can't be compared.
OTOH you can probably get away with saying "for a big enough n..."
I'm not trying to say that one is better than the other, I haven't
computed it and I don't intend to. I'm just pointing out that this
particular argument doesn't work (at least in the way it is presented).
Jérôme
--
******************************* Jérôme M. BERGER
* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde... * http://www.enst.fr/~jberger
*******************************
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich wrote:
>
> In article <39bab3c5@news.povray.org> , Warp <war### [at] tagpovrayorg> wrote:
>
> > Thorsten Froehlich <tho### [at] trfde> wrote:
> > : Hmm, lets see, you need (runtimes from the C++ Prog. Lang 3rd Ed. page
> > : 464)...
> >
> > : For inserting: O(n * log(n))
> > : For retrieval: O(n * log(n))
> >
> > By the way, you are wrong here.
> >
> > It's true that retrieval is O(n*log(n)), but an operator++() of the
> > iterator is O(1), so the retrieval of the whole tree is O(n) in my case.
>
> OK, so Stroustrup is wrong?
I don't know what Stroustrup said, but according to the STL
documentation here: http://www.sgi.com/Technology/STL/trivial.html
> The complexity of operations on trivial iterators is guaranteed to be amortized
constant time.
Jérôme
--
******************************* Jérôme M. BERGER
* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde... * http://www.enst.fr/~jberger
*******************************
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich <tho### [at] trfde> wrote:
:> request for member `clear' in `x', which is of non-aggregate type
:> `string ()()'
: Hmm, this is a funny error message. What is the cause? I am curious!
This code causes it. Can you see what is the mistake?
#include <string>
using namespace std;
int main()
{
string x();
x.clear();
}
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich <tho### [at] trfde> wrote:
:> And iterators are just brilliant.
: It is easy to make the wrong assumptions about them, i.e. how fast they
: really are for some data structures. Nevertheless, they are really useful!
It's the idea behind the iterators that make them so brilliant.
They work like pointers (but are of course much safer). This means that
you can read the same data container from different places using different
iterators without them interfering each other.
A mistake made often by people is to create a data container and then
add some methods like "getFirst()" and "getNext()". This has the serious
problem that you can't read the container from different places without
each of them interfering the others. But as iterators work like pointers,
they can be used independently.
Also iterators are very independent of the data container they are
associated to. This means that you don't have worry how to get to the next
item; you just make a ++ and you are in the next item, no matter if the
container is a list, a vector, a tree or whatever.
This means that general algorithms that work for most STL containers can
be made (and they have been made in the <algorithm> include file).
For example if you want to sort your items you just call:
sort(myCont.begin(), myCont.end());
It doesn't matter if myCont is a vector, a list, a deque or whatever (for
binary trees it makes no sense since they are already sorted; also the STL
list has an inner sort which is more efficient since it only changes
pointers and doesn't need to copy the items, but the above command should
work for lists as well).
If you want to sort your container in reverse order, it's easy:
sort(myCont.rbegin(), myCont.rend());
(Btw, the fact that rbegin() returns an iterator to the same item as end()
and that rend() returns an iterator to the same item as begin() is very
confusing until you understand how they really work.)
Also copying data from one container to other is very easy. For example:
vector<int> myVector(myCont.begin(), myCont.end());
It doesn't matter what myCont is, as long as its iterator supports
operator++().
This last thing is specially useful in this case:
int main(int argc, char* argv[])
{ vector<string> CommandLine(argv, argv+argc);
This is so because regular pointers work as iterators as well (not a
big surprise).
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich <tho### [at] trfde> 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?
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.
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
>
> This code causes it. Can you see what is the mistake?
>
> #include <string>
> using namespace std;
>
> int main()
> {
> string x();
This line doesn't define a variable of type string but a function with
no arguments that return a string and whose code is assumed to be given
elsewhere (except that I'm surprised that this works inside another
function, I would have understood better if "string x();" was before
"int main()").
> x.clear();
But this should work: "x().clear();" (assuming you've got the function
x defined elsewhere). Hey, I wasn't that far off! :))
> }
>
Jérôme
--
******************************* Jérôme M. BERGER
* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde... * http://www.enst.fr/~jberger
*******************************
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39BCACF2.FEB14C46@enst.fr> , Jérôme Berger
<Jer### [at] enstfr> 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] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
In article <39bcdb54$1@news.povray.org> , Warp <war### [at] tagpovrayorg> 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] trfde
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Thorsten Froehlich wrote:
>
> In article <39BCACF2.FEB14C46@enst.fr> , Jérôme Berger
> <Jer### [at] enstfr> 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)
Jérôme
--
******************************* Jérôme M. BERGER
* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde... * http://www.enst.fr/~jberger
*******************************
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Sat, 09 Sep 2000 18:46:59 -0500, Thorsten Froehlich wrote:
>In article <39bab424@news.povray.org> , Warp <war### [at] tagpovrayorg> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 11 Sep 2000 09:40:08 -0400, Warp wrote:
>Thorsten Froehlich <tho### [at] trfde> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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] wsracat | -- Ale### [at] univieacat
__/ | http://www.hjp.at/ | zum Thema Portale in at.linux
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Jérôme Berger <Jer### [at] enstfr> 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.
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
>
> Jérôme Berger <Jer### [at] enstfr> 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.
Jérôme
--
******************************* Jérôme M. BERGER
* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde... * http://www.enst.fr/~jberger
*******************************
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 12 Sep 2000 05:17:32 -0400, Warp wrote:
>Jérôme Berger <Jer### [at] enstfr> 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] wsracat | -- Ale### [at] univieacat
__/ | http://www.hjp.at/ | zum Thema Portale in at.linux
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Peter J. Holzer <hjp### [at] sikituwsracat> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 15 Sep 2000 02:46:13 -0400, Warp wrote:
>Peter J. Holzer <hjp### [at] sikituwsracat> 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".
In C, a declaration tells the compiler what a "thing" (an object[1] or a
function) looks like, while a definition creates it. Every definition
is also a declaration, but not vice versa.
> Usually when I have to refer to the body of the function I use
>the word "implementation". It may be wrong, though.
No it isn't wrong. It just isn't the word used when one talks about the
C programming language. Modula-2 for example has "definition modules"
and "implementation modules". Obviously when someone talks about a
"definition" in a modula program, he means something else than someone
talking about a "definition" in a C program.
Unfortunately, often a single word is used for different concepts, and
different words are used for the same concepts. What is meant has to be
guessed from context.
hp
[1] Just as another example: An "object" in C is just a place to store
values (either a variable or a malloced area). It has nothing to do with
object-oriented programming.
--
_ | Peter J. Holzer | access ist als datenbankserver fraglos noch
|_|_) | Sysadmin WSR | ungeeigneter als beispielsweise EDIT.COM,
| | | hjp### [at] wsracat | und das primaer aufgrund der erzeugung
__/ | http://www.hjp.at/ | falscher erwartungshaltungen. frank paulsen
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
