 |
 |
|
 |
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
Thorsten Froehlich <tho### [at] trf de> 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] trf de> 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] trf de> 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] tag povray org>
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] mac com, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tag povray org, http://tag.povray.org/
<><
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
Chris Huff <chr### [at] mac com> 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] tag povray org> wrote:
> Thorsten Froehlich <tho### [at] trf de> 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] trf de
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] 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!
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
|
 |
|  |
|  |
|
 |
|
 |
|  |
|  |
|
 |
In article <39bab334@news.povray.org> , Warp <war### [at] tag povray org> 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] trf de
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] tag povray org> 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] trf de
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
 |
|  |
|  |
|
 |
|
 |
|  |
|
 |