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